[코딩테스트] Java 정리 - 0

코딩테스트에서 가장 중요한 시간 복잡도 별 알고리즘을 정리했습니다.

1. 시간 복잡도

• 대부분의 코딩테스트 환경은 1초에 약 1억 번(10⁸) 연산을 처리할 수 있다고 가정합니다.
  (자바는 C++보다 살짝 느려서, 5천만~7천만 연산 정도로 안전하게 계산)
• 따라서 대략 1억 번 이하의 연산은 1초 안에 돌아간다고 봅니다.

  1초 ≈ 1억 번 연산 → 자바에선 안전하게 5천만 번으로 잡기!

  • N이 작으면 완탐
  • N이 크면 정렬/이분탐색/DP
  • 100만 넘어가면 무조건 O(N)
  • 상수 계수 큰 연산 (문자열 처리, 객체 연산 등) 주의
  • PriorityQueue 많이 쓰면 힙 O(N log N)
  • ArrayDeque로 Stack/Queue 대체

제한 시간	최대 N (자바)	권장 복잡도	대표 알고리즘 예시	설명
0.5 ~ 1초	10 이하	O(N!), O(2^N)	순열, 조합, 백트래킹	완전탐색, 부분집합 전수조사
1초	500 이하	O(N³)	플로이드-워셜, 3중 for DP	내부 연산이 단순할 때만 가능
1초	1,000 이하	O(N²) ~ O(N³)	DP 테이블, 인접행렬 BFS	N²는 안전, N³은 구조에 따라 가능
1초	10,000 이하	O(N²)	이중 루프, 단순 DP, 간단 그리디
1초	100,000 이하	O(N log N)	정렬, 힙, 우선순위 큐, 세그먼트 트리, 이분 탐색
1초	1,000,000 이하	O(N)	투포인터, 누적합, 해시맵
1초	10⁷ 이상	O(1), O(log N)	수식 계산, 단일 이분 탐색
2 ~ 3초	+1 ~ 2배	그래프 탐색(BFS/DFS), 큰 DP	대용량 입력 제한 완화
5초 이상	더 큰 N	최적화 필요	대형 그래프, 느린 완전탐색

(참고) N이 1,000일 때, O(N³)..?

• O(N³)은 플로이드-워셜 수준만 괜찮음 (단순 연산)
• O(N³)이라도 N이 2,000이면 거의 불가능
• O(N²)도 10,000 넘으면 느려짐 → N log N 알고리즘으로 바꿔야 안전

2. 알고리즘 및 시간복잡도

복잡도	대표 알고리즘
O(1)	수식 계산, 간단한 값 비교
O(log N)	이분탐색, lower_bound, upper_bound
O(N)	선형 탐색, 단일 루프, 투포인터, 누적합
O(N log N)	정렬(퀵 평균, 머지, 힙), 우선순위 큐
O(N²)	이중 for문, 인접행렬 그래프, 정렬(퀵 최악, 버블, 선택)
O(N³)	플로이드-워셜
O(2ⁿ)	순열, 부분집합
O(N!)	모든 경우의 수 완전탐색

3. log 계산

• 밑이 2와 10은 약 3배 정도 차이남, 그러나 빅오에서 상수배는 무시되므로 영향 없음

N	log₂(N)	log₁₀(N)
10	3.3	1
100	6.6	2
1,024 (2¹⁰)	10
1,000 ≈ 2¹⁰	약 10	3
1,000,000 ≈ 2²⁰	약 20	6
1,000,000,000 ≈ 2³⁰	약 30	9

밑	의미	예시
2	반으로 쪼갬	이분탐색, 트리 높이
10	자리수 계산	자릿수, 문자열 처리
e	자연로그	거의 안 씀 (수학용)

4. 문제 예시

문제 예시	N	권장 알고리즘
모든 순열	8	O(N!)
플로이드-워셜	500	O(N³)
DP (배낭 문제)	1,000	O(N²)
배열 정렬	100,000	O(N log N)
큰 수에서 부분합	1,000,000	O(N)
소수 판별	10⁹	O(√N)
이분 탐색	10⁹	O(log N)

참고 블로그

• 시간 복잡도, 공간 복잡도, 빅오 이해하기