[Do it] 알코테 자바 1일차

01. 어떤 알고리즘으로 풀어야 할까?

01-1. 시간 복잡도 표기법 알아보기

알고리즘을 선택할 때 가장 먼저 고려해야 하는 것은 시간 복잡도(Time Complexity)이다.
입력 크기 N이 커졌을 때, 코드가 얼마나 빠르게 실행되는지를 수학적으로 표현한 것이다.n)

표기법의미설명

빅오메가 (Ω)	최선의 경우	최소 수행 시간
빅세타 (Θ)	평균(정확한 경계)	상한과 하한이 같은 경우
빅오 (O)	최악의 경우	최대 수행 시간

-> 코딩 테스트에서는 보통 최악의 경우인 빅오(Big-O) 를 기준으로 계산한다.

---

1. O(1) — 상수 시간

int a = 10;

입력 크기와 상관없이 1번 실행된다.

2. O(N) — 선형 시간

for(int i = 0; i < N; i++)

N번 실행된다.

3. O(N²) — 이중 반복문

for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)

N × N → N²

---

왜 빅오 기준으로 계산할까?

• 코딩 테스트는 입력 크기가 매우 클 수 있음
• 평균이 아니라 최악의 경우에도 시간 초과가 나지 않아야 함
• 그래서 보통 O(N log N) 이하로 설계해야 안전한 경우가 많음

01-2. 시간 복잡도 활용하기

문제 : 백준 2750 수 정렬하기

import java.util.*;
import java.lang.*;
import java.io.*;

// The main method must be in a class named "Main".
class Main {
	public static void main(String[] args) {
    
		Scanner in = new Scanner(System.in);
		
		int N = in.nextInt();
		int[] arr = new int[N];
		
		for(int i = 0; i < N; i++) {
			arr[i] = in.nextInt();
		}
 
		// Selection sort
		for(int i = 0; i < N - 1; i++) {
			for(int j = i + 1; j < N; j++) {
				if(arr[i] > arr[j]) {
					int temp = arr[j];
					arr[j] = arr[i];
					arr[i] = temp;
				}
			}
		}
		
		for(int val : arr) {
			System.out.println(val);
		}
 
	}
}

---

02. 코드의 논리 오류를 어떻게 잡을까?

02-1. 디버깅은 왜 중요할까? / 02-2. 디버깅 활용 사례 살펴보기

코딩 테스트에서 틀리는 이유는 대부분 두 가지다.

1. 시간 초과
2. 논리 오류 (WA)

특히 논리 오류는 컴파일이 정상적으로 되기 때문에 더 찾기 어렵다.

---

디버깅의 중요성

• 문제를 제대로 이해했는지 검증 가능
• 예외 케이스를 확인할 수 있음
• 작은 실수를 빠르게 수정 가능
• 면접에서 “에러를 어떻게 해결했는가” 설명 가능

---

디버깅하는 방법

1. 작은 입력값으로 직접 추적하기
2. System.out.println으로 중간 값 출력
3. 반복문 인덱스 확인
4. 경계 조건 체크 (0, 1, 최대값)
5. 자료형 범위 확인 (int vs long)

---

 

오늘의 핵심 정리

• 알고리즘 선택의 기준은 시간 복잡도
• 코딩 테스트는 빅오(O) 기준으로 계산
• 정렬 문제는 입력 크기에 따라 방법을 바꿔야 한다.
• 디버깅은 실수를 찾는 능력이며, 실력의 일부이다.