기준: C++ / 1–2초 시간제한 / 단순 연산 약 1~3억 회 기준
| 입력 크기(대략) | 허용 시간복잡도(대략) | 추천 알고리즘 / 패턴 | 비고 |
|---|---|---|---|
| N ≤ 10 | O(N!) | 순열, 백트래킹(완전탐색) | 10! = 360만, 완전탐색의 마지노선 |
| N ≤ 20 | O(2N) | 비트마스킹, 부분집합 DP, 백트래킹 | 220 ≈ 100만 (안전) |
| N ≤ 40 | O(2^(N/2)) | Meet-in-the-Middle | 반으로 나눠 각각 220개 생성 후 정렬+이분탐색으로 병합 |
| N ≤ 50 | O(N4) | 4중 루프, 4차원 DP(희귀) | 504 ≈ 625만 (안전). 1004 = 1억은 상수 크면 위험 |
| N ≤ 400~500 | O(N3) | 3중 루프, 행렬 DP, 가우스 소거 | 5003 ≈ 1.25억 → "턱걸이", 400 이하가 안정적 |
| N ≤ 5,000 | O(N2) | 2중 루프, 2D DP, 전처리 | 50002 = 2500만 (매우 안전) |
| N ≤ 10,000 | O(N2) (턱걸이) | 2중 루프 | 100002 = 1억 (C++에서 턱걸이) |
| N ≤ 100,000 | O(N log N) | 정렬, 이분 탐색, 우선순위큐, 그리디, 세그먼트 트리, 펜윅 트리 | N2은 거의 무조건 시간초과 |
| N ≤ 1,000,000 | O(N) ~ O(N log N) | 투 포인터, 슬라이딩 윈도우, 해시, 선형 DP, KMP/Z, 에라토스테네스의 체 | O(N log N)도 대부분 통과. 입출력/상수도 영향 큼 |
| N ≤ 10,000,000 | O(N) | 선형 체, 투 포인터, 단순 순회 | O(N log N)은 상수에 따라 위험 |
| N ≥ 109 | O(log N), O(√N), O(1) | 이분 탐색, 유클리드 호제법, 빠른 거듭제곱, 행렬 거듭제곱, 수학 공식 | 반복문으로 N만큼 순회 불가 |
| 상황 / 입력 크기(대략) | 허용 복잡도(대략) | 추천 알고리즘 | 비고 |
|---|---|---|---|
| V ≤ 1e5, E ≤ 1e6 | O(V + E) | BFS, DFS, 위상정렬 | 가장 기본이자 강력 |
| V ≤ 1e5, E ≤ 5e5 | O(E log V) | 다익스트라 (PQ + 인접리스트) | 가중치 양수일 때 표준 |
| V ≤ 1e5, E ≤ 5e5 | O(E log E) | 크루스칼 (정렬 + 유니온파인드) | MST 표준 |
| V ≤ 5,000~10,000 & E 적음 | O(V · E) | 벨만-포드 | 음수 간선 / 음수 사이클 체크용. O(N2) 아님에 주의 |
| V ≤ 400~500 | O(V3) | 플로이드-워셜 | 모든 쌍 최단거리 (APSP) |
| V ≤ 2,000 (밀집 그래프) | O(V2) | 다익스트라 (인접행렬), 프림 (인접행렬) | 간선이 많을 때 유리. 메모리 O(V2) 주의 |
| 입력 크기(대략) | 허용 복잡도(대략) | 추천 자료구조 / 패턴 | 비고 |
|---|---|---|---|
| N, Q ≤ 200,000 ~ 1,000,000 | O((N+Q) log N) | 세그먼트 트리, 펜윅 트리, 정렬+오프라인, 스위핑 | 구간합 / 최솟값 / 업데이트 |
| N, Q ≤ 100,000 | O((N+Q)√N) | Mo's Algorithm | 오프라인 구간 쿼리, 업데이트 없을 때 |
| N, Q ≤ 200,000 | O((N+Q) α(N)) | 유니온-파인드 | MST / 연결성 / 오프라인 쿼리. α(N)은 사실상 상수 |
| N, Q ≤ 1e6 | 평균 O(N + Q) | 해시 (unordered_map/set) | 최악 케이스 대비 리저브 / 커스텀 해시 고려 |
- 시간 제한이 2초 이상이면 한 단계 위 복잡도도 통과할 수 있음
- 상수(constant factor) 가 큰 알고리즘(예: 세그트리 with lazy)은 같은 복잡도라도 더 빡빡할 수 있음
- 입출력 최적화 (
ios::sync_with_stdio(false); cin.tie(nullptr);)는 N ≥ 10만일 때 거의 필수 - 그래프/쿼리 문제는 N만 보지 말고 V, E, Q를 함께 확인할 것
STL
(1) 성능 비교: List vs Queue
`std::list`와 `std::queue`는 시간 복잡도가 같아 보이지만, **메모리 구조** 때문에 실제 성능 차이가 크다.
-
std::queue(deque 기반): 데이터가 블록 단위로 연속 배치되어 Cache Hit 비율이 높고 빠르다. (권장) -
std::list: 노드가 힙 메모리에 흩어져 있어 Cache Miss가 잦아 느리다. 특별한 이유가 없다면 사용을 지양한다.
(2) 빈번한 삽입/삭제 처리
* 벡터(`vector`)나 큐(`queue`)는 중간 요소를 삽입/삭제할 때
그래프
1. 그래프 표현 방식 (Graph Representation)
-
희소 그래프 (Sparse Graph): 간선의 개수가 적은 경우 (
$E \ll V^2$ )$\rightarrow$ 인접 리스트 (vector<vector<int>>) 사용 (메모리 절약) -
밀집 그래프 (Dense Graph): 간선이 많거나 플로이드-워셜 알고리즘
$\rightarrow$ 인접 행렬 (int adj[N][N]) 사용 ($O(1)$ 접근 속도 활용)
2. 메모리 최적화 (Memory Optimization)
-
Visited 배열 생략: 2차원 그리드 탐색(BFS/DFS) 시 원본 배열 수정이 가능하다면, 방문한 위치의 값을 직접 변경(예:
'1'$\to$ '0')하여visited배열 메모리($O(NM)$)를 절약할 수 있다.
그래프 탐색 및 모델링 전략 (Graph Strategy)
1. 보이지 않는 그래프 (Implicit Graph)
| 핵심 | 내용 |
|---|---|
| 정의 | "상태(State)를 노드로, 변화(Transition)를 간선으로 정의하면 무엇이든 그래프로 만들 수 있다." |
| 적용 | 2차원 맵이 없어도 **현재 상황(숫자, 좌표)**을 정점으로, 규칙을 간선으로 보아 BFS로 변환 가능 |
2. 탐색 방식 선택 가이드
| 기준 | 추천 알고리즘 | 설명/이유 |
|---|---|---|
| 노드 수 ( |
DFS ( BFS ( |
DFS: 구현 간결성 BFS: 스택 오버플로우 방지 및 최단 거리 보장 |
| 목적 (Output) |
Union-Find BFS |
단순 영역/집합 구분 (가장 효율적) 최단 거리/경로 추적 |
| 메모리 효율 | DFS | 경로 끝까지 가는 완전 탐색 시 압도적으로 유리 (BFS는 큐에 |
3. Multi-source BFS (동시 시작)
| 구분 | 내용 |
|---|---|
| 상황 | 불, 바이러스 등 여러 지점에서 동시에 확산될 때 |
| 구현 | 시작점들을 초기에 모두 큐에 넣고(Push) BFS를 단 한 번 수행 |
| 효율성 | 각 시작점 반복 |
4. 단방향 그래프의 왕복 최단 거리 (Reverse Graph Strategy)
| 구분 | 내용 |
|---|---|
|
최적화 전략 (Insight) |
1. 정방향 그래프: 2. 역방향 그래프: |
| 효과 | 다익스트라 단 2회 수행. 시간 복잡도 |
5. 최소 신장 트리(MST) 조기 종료 (그래프 분할)
| 구분 | 내용 |
|---|---|
|
관점의 전환 (Insight) |
|
| 효과 | 전체 트리를 완성한 후 큰 간선을 다시 제거할 필요 없이, 크루스칼(Kruskal) 알고리즘 진행 중 조건 달성 시 즉시 종료(break)하여 연산 최적화 및 로직 간소화가 가능하다. |
|
🚨 주의사항 (Edge Case) |
반복문 안에서 종료 조건을 검사하면 if (N <= K) return 0;)를 해야 한다. |
완전 탐색 (Brute Force & Backtracking)
완전 탐색은 입력 크기(
1. 구현 방식
-
단순 반복문:
$N$ 중for/while문 사용. -
재귀 (Backtracking):
-
순열 (Permutation): 순서 중요 (
$A, B \ne B, A$ )$\to$ next_permutation또는visited배열 사용. -
조합 (Combination): 순서 무관 (
$A, B = B, A$ )$\to$ start인덱스를 인자로 넘겨 중복 방지.
-
순열 (Permutation): 순서 중요 (
-
비트마스킹 (Bitmasking): 집합의 포함 여부를 비트(
0,1)로 관리하여 메모리와 연산 속도 최적화.
시뮬레이션 및 수열 전략 (Simulation & Math)
1. 원형 순환 (Josephus Problem) 전략
-
제거되는 순서가 필요한 경우
$\rightarrow$ Simulation-
$N$ 이 작음 (5,000 이하): Queue 시뮬레이션. -
$K$ 가 매우 큼 (10억 이상): Vector + Modulo(%) 연산 (Queue 반복 시 시간 초과).
-
-
마지막 남는 하나만 필요한 경우
$\rightarrow$ DP / Math ($O(N)$ 점화식 활용).
백트래킹(Backtracking) 성능 최적화
백트래킹 알고리즘의 성능은 1. 탐색 공간의 최소화와 2. 유망성 검사(Pruning) 비용의 최적화에 의해 결정된다.
-
Space-Time Trade-off (N-Queen 예시)
- 반복문(
for)을 통해 유망성을 검사하면$O(N)$ 이 소요되어 비효율적이다. - 3가지 조건(열, 좌상향 대각선, 우상향 대각선)을 배열에 미리 매핑하여 검사 비용을 **$O(1)$**로 단축할 수 있다.
- 반복문(
-
비트마스킹 (Bitmasking)
-
bool배열 대신 비트(Bit)를 활용하면 메모리 사용량을 최소화할 수 있으며, 비트 연산을 통해 처리 속도를 더욱 높일 수 있다.
-
2차원 배열의 1차원화 테크닉 (Optimization)
2차원 좌표
-
변환 공식:
$M$ 은 2차원 배열의 가로 길이(열의 개수)-
1D to 2D:
$r = k / M$ ,$c = k % M$ -
2D to 1D:
$k = r \times M + c$
-
1D to 2D:
-
활용 (백트래킹 조합 최적화)
-
start인덱스를 인자로 받아for (int k = start; k < N*M; ++k)반복문 하나로 처리. - 이전 위치 재방문 방지 및 중복 검사 로직(
$visited$ ) 제거로 실행 속도 대폭 향상 (약3ドル! = 6$ 배).
-
모듈러(%) 연산 인덱스 처리
- 대부분의 모듈러 연산은 0부터 시작하는 인덱스(0-based Index)에서 예외 없이 깔끔하게 작동한다.
- 문제에서 대상이 1번부터 시작하더라도, 내부 로직에서는
0ドル \sim N-1$ 로 변환하여 처리하고, 최종 출력 시에만$+1$ 을 해주는 것이 인덱스 계산 실수를 줄이는 방법이다.
- BFS 방문 처리 시점: 방문 처리는 반드시 "큐에 넣을 때(Push)" 수행해야 한다.
- 큐에서 꺼낼 때(Pop) 처리할 경우, 동일한 노드가 큐에 중복되어 삽입될 수 있으며 이는 메모리 초과 및 시간 초과의 원인이 된다.
- 인덱스 오프셋 오류: "K번째"라는 말이 나올 때 arr[K]가 아니라 arr[K-1]인지, 혹은 입력을 1-based로 받고 0-based로 변환했는지 확인한다.
- 배열 크기 및 경계값 오류