시간, 공간 복잡도
Summary
입력 크기를 보고 가능한 풀이를 먼저 정한다.
Java에서는1억 번 = 1초를 너무 낙관하지 말고, 여유 있게 잡는다.
N 범위별 목표 복잡도
| N 범위 | 가능한 복잡도 | 대표 풀이 |
|---|---|---|
N <= 10 | O(N!) | 순열, 모든 순서 |
N <= 20 | O(2^N) | 부분집합, 비트마스크 |
N <= 30 | O(2^(N/2)) | meet-in-the-middle 후보 |
N <= 500 | O(N^3) | Floyd, 3중 for |
N <= 2,000 | O(N^2) | 2중 for, 2차원 DP |
N <= 100,000 | O(N log N) | 정렬, 이분탐색, PQ, Dijkstra |
N <= 1,000,000 | O(N) 또는 O(N log N) | BFS, 누적합, 해시 |
N <= 10,000,000 | O(N) | 단순 선형, 배열 1개 수준 |
그래프 / 격자 기준
| 입력 | 목표 |
|---|---|
격자 N * M <= 1,000,000 | BFS/DFS/시뮬레이션 가능 |
정점 V, 간선 E | BFS/DFS는 O(V + E) |
| 양수 최단거리 | Dijkstra O(E log V) |
| 모든 쌍 최단거리 | Floyd O(V^3), 보통 V <= 500 |
| MST Kruskal | O(E log E) |
| 위상정렬 | O(V + E) |
테스트케이스 포함 계산
Warning
T가 있으면T * 풀이 복잡도로 계산한다.
T = 50, N = 100,000
O(TN) = 5,000,000 가능
O(TN log N) = 대략 85,000,000 주의하지만 가능권
O(TN^2) = 500,000,000,000 불가능메모리 직감
| 자료형 | 크기 |
|---|---|
boolean | 대략 1 byte |
int | 4 byte |
long | 8 byte |
int[1_000_000] | 약 4MB |
long[1_000_000] | 약 8MB |
int[2000][2000] | 약 16MB + 배열 객체 오버헤드 |
long[2000][2000] | 약 32MB + 배열 객체 오버헤드 |
자료형 기준
| 상황 | 추천 |
|---|---|
| 입력값이 21억 이하 | int 가능 |
| 비용 합, 거리 합 | 기본 long 의심 |
| 경우의 수 | long 또는 mod 확인 |
| 20자리 이상 정수 | BigInteger 고려 |
p * p <= n | overflow 방지로 p <= n / p 권장 |
백지 복원
1. N <= 20이면 가장 먼저 떠올릴 수 있는 두 가지는?
2. V=100,000, E=300,000 최단거리에서 가능한 알고리즘은?
3. int[2000][2000]은 대략 몇 MB인가?
4. T가 있을 때 복잡도 계산을 어떻게 바꾸는가?
5. 비용 합이 나오는 문제에서 int를 바로 쓰면 안 되는 이유는?