2026-07-29 TIL (107일차)

Posted Jul 29, 2026 Updated Jul 29, 2026

By BAEK MUSONG(백무송)

29 min read

알고리즘 강의 총정리 — 복잡도부터 A*까지

강의 21개 주제를 기초 → 심화 순으로 재배열해 핵심만 압축했습니다. 각 주제는 개념 + 면접 포인트 + 게임 적용 관점으로 정리했습니다.

1. “1초에 1억 번” — 시간 복잡도

입력 크기 $n$이 커질 때 연산 횟수의 증가 추세를 나타내는 표기이며, 상수와 낮은 차수 항은 무시합니다($3n^2 + 5n + 10 \rightarrow O(n^2)$). Big-O(상한) / Θ(정확한 차수) / Ω(하한) 중 최악을 보장하는 Big-O를 주로 씁니다.

\[O(1) < O(\log n) < O(n) < O(n \log n) < O(n^2) < O(n^3) < O(2^n) < O(n!)\]

채점 환경에서 1초 ≈ 1억(10^8)회 단순 연산이 경험적 기준입니다. 이 표로 $n$을 보고 알고리즘을 역산합니다.

n의 크기	허용 복잡도	접근법
n ≤ 10	$O(n!)$	순열 전탐색
n ≤ 20~25	$O(2^n)$	비트마스크, 부분집합
n ≤ 100	$O(n^3)$	플로이드-워셜, 3중 루프
n ≤ 2,000	$O(n^2)$	이중 루프 DP
n ≤ 100,000	$O(n \log n)$	정렬, 우선순위 큐, 이분 탐색
n ≤ 1,000,000	$O(n)$	투 포인터, 슬라이딩 윈도우, 누적합
n ≥ 10^9	$O(\log n)$	이분 탐색, 수학적 접근

공간 복잡도: 게임에서는 메모리가 프레임 성능과 직결됩니다. 재귀는 콜 스택을 소비해 깊이가 크면 스택 오버플로우가 나고, DP 테이블은 $O(n^2)$ 메모리를 잡아먹습니다.
분할 상환(Amortized): vector::push_back은 재할당 순간만 $O(n)$이고 평균은 $O(1)$입니다. 다만 이 간헐적 $O(n)$이 게임에서는 프레임 스파이크로 나타나므로 reserve()로 최악을 제거해야 합니다.

2. 컨테이너 선택과 문자열

요구 사항	선택
인덱스 접근 + 순차 순회	`vector`
LIFO (DFS, 괄호, Undo)	`stack`
FIFO (BFS, 큐잉)	`queue`
양끝 삽입/삭제 (0-1 BFS, 윈도우 최대값)	`deque`
존재 여부 / 카운팅	`unordered_set` / `unordered_map`
정렬 유지 + 범위 질의	`map` / `set`
최소·최대 반복 추출	`priority_queue`

문자열 주의점: std::string은 짧으면 SSO로 스택, 길어지면 힙 할당이 발생합니다. 루프에서 +는 임시 객체를 만들므로 +=·ostringstream을 쓰고, 인자는 const std::string& 또는 std::string_view로 받습니다. substr은 새 문자열을 만들지만 string_view는 복사 없이 $O(1)$입니다.

패턴 매칭: 단순 비교 $O(nm)$ → KMP는 실패 함수로 “이미 비교한 접두사 정보를 버리지 않아” $O(n+m)$ → 라빈-카프는 롤링 해시 → 트라이 / 아호-코라식은 다중 패턴, 즉 채팅 금칙어 필터의 실제 구현입니다.

3. 정렬 — `std::sort`의 정체

알고리즘	평균	최악	공간	안정성	특징
삽입	$O(n^2)$	$O(n^2)$	$O(1)$	✅	거의 정렬된 데이터에 $O(n)$
병합	$O(n \log n)$	$O(n \log n)$	$O(n)$	✅	최악 보장
퀵	$O(n \log n)$	$O(n^2)$	$O(\log n)$	❌	상수가 작아 실측 최고속
힙	$O(n \log n)$	$O(n \log n)$	$O(1)$	❌	제자리 + 최악 보장
카운팅 / 기수	$O(n+k)$	동일	$O(k)$	✅	값 범위가 작을 때

퀵소트가 최악 $O(n^2)$인데도 표준인 이유: 제자리 정렬이라 추가 할당이 없고 캐시 지역성이 뛰어나며, 피벗을 랜덤·중앙값-of-3로 고르면 최악 확률이 무시할 수준입니다. (최악은 이미 정렬된 배열에서 첫 원소를 피벗으로 고를 때)
std::sort = Introsort: ① 퀵소트로 시작 → ② 재귀 깊이가 $2\log n$을 넘으면 힙소트로 전환(최악 보장) → ③ 구간이 16개 이하로 짧아지면 삽입 정렬로 마무리. 세 알고리즘의 장점만 조합한 하이브리드입니다.
안정성: 같은 키의 원래 순서 보존. 다중 기준 정렬을 순차적으로 할 수 있게 해줍니다. std::sort는 불안정, std::stable_sort는 안정. 리더보드 동점 처리, 같은 depth UI의 드로우 순서에 필요합니다.

커스텀 비교자 함정: 비교자는 엄격한 약한 순서를 만족해야 하며, 같을 때 false를 반환해야 합니다.

  
std::sort(v.begin(), v.end(), [](int a, int b){ return a <= b; });  // ❌ UB, 실제로 크래시
std::sort(v.begin(), v.end(), [](int a, int b){ return a <  b; });  // ✅

4. 재귀와 스택 프레임

필수 요소: ① 종료 조건(base case) ② 더 작은 문제로의 자기 호출
한계: 호출마다 프레임(매개변수·지역변수·반환 주소·이전 프레임 포인터)이 쌓입니다. 기본 스택이 약 1MB, 프레임이 100byte면 대략 1만 depth 근처에서 위험해집니다. 이때는 std::stack에 상태를 담아 반복문으로 전환합니다.
꼬리 재귀: 컴파일러가 반복문으로 최적화할 수 있지만 C++ 표준이 보장하지 않으므로 의존하면 안 됩니다.
연결 고리: 콜 스택은 결국 스택 자료구조 그 자체여서, 재귀 DFS와 명시적 스택 DFS가 같은 순서를 만듭니다.

5. 이진 탐색 — 핵심은 매개변수 탐색

전제는 정렬이며 $O(\log n)$입니다. 단, 정렬 비용이 $O(n \log n)$이라 한 번만 찾을 거면 선형 탐색이 낫고, 여러 번 검색할 때 이득입니다.

  
int mid = (lo + hi) / 2;        // ❌ 오버플로우 위험
int mid = lo + (hi - lo) / 2;   // ✅

lower_bound(x) = x 이상인 첫 위치, upper_bound(x) = x 초과인 첫 위치. 차를 구하면 x의 개수입니다. (랜덤 액세스 이터레이터일 때만 $O(\log n)$ — std::list에 쓰면 $O(n)$)
경계 조건에서 무한 루프가 잦으므로 반열린 구간 [lo, hi) 한 가지 형태로 통일하는 게 안전합니다.
매개변수 탐색: 어떤 값 $x$에 대해 조건이 단조(monotonic) 하게 참/거짓으로 갈리면, 답 자체를 이분 탐색해 $O(\log(\text{범위}))$에 찾습니다. (나무 자르기, 랜선 자르기)

게임 적용: 조준 발사 각도 계산, 카메라가 벽에 닿지 않는 최대 거리, 밸런싱 파라미터 역산(목표 클리어 시간이 나오는 몬스터 체력 찾기).

6. 완전 탐색과 비트마스크

완전 탐색이 정당한 경우는 ① n이 작을 때 ② 정확성이 우선일 때 ③ 다른 알고리즘의 정답 검증 기준이 필요할 때입니다. 면접에서는 “먼저 완전 탐색으로 정답을 보장하고, 그다음 최적화 지점을 찾는다”는 사고 순서를 보여주는 게 중요합니다.

기법: 반복문 중첩(고정 개수) / 재귀·DFS(가변 깊이) / 비트마스크(n ≤ 20) / std::next_permutation(정렬 상태에서 시작) / BFS(최소 횟수).

연산	코드
포함 확인	`(mask >> i) & 1`
추가	`mask \\|= (1 << i)`
제거	`mask &= ~(1 << i)`
토글	`mask ^= (1 << i)`
전체 순회	`for (int s = 0; s < (1 << n); ++s)`

게임 적용: 언리얼의 콜리전 채널이 정확히 비트마스크입니다. 오브젝트 타입별 비트를 세워 & 한 번으로 “충돌해야 하는가”를 판정하므로 수천 쌍을 검사해도 저렴합니다.

7. 백트래킹 — 가지치기

DFS 기반 완전 탐색에 가지치기(Pruning) 를 더한 것입니다. 현재 경로가 더 진행해도 답이 될 수 없으면 즉시 되돌아갑니다. 최악 복잡도는 완전 탐색과 같지만 실측 성능은 훨씬 좋습니다.

  
void backtrack(State& s, int depth) {
    if (isSolution(s)) { record(s); return; }
    for (auto& choice : candidates(s)) {
        if (!isPromising(s, choice)) continue;   // ← 가지치기
        apply(s, choice);
        backtrack(s, depth + 1);
        undo(s, choice);                         // ← 되돌리기 (최다 실수)
    }
}

가지치기 예: N-Queen(같은 열·대각선), 부분집합 합(목표 초과 시 중단), 스도쿠(후보 0개 칸 발생), 미로(방문 표시 후 해제).

게임 적용: AI가 몇 수 앞을 보는 미니맥스 + 알파베타 가지치기가 백트래킹의 직계 응용이고, 제약을 만족하는 배치를 찾는 절차적 레벨 생성(WFC류)에도 쓰입니다.

8. 그리디 vs DP — 구분이 핵심

그리디 성립 조건: ① 탐욕적 선택 속성 ② 최적 부분 구조. 증명 없이 쓰면 틀립니다. 동전 {1,4,5}로 8원은 그리디 5+1+1+1=4개지만 최적은 4+4=2개이고, {1,5,10,50}처럼 배수 관계면 성립합니다.

구분	Greedy	DP
선택 방식	현재 최선을 즉시 확정, 되돌아보지 않음	모든 경우를 검토 후 최선
속도	빠름 (보통 정렬 $O(n \log n)$)	느림 (상태 수 × 전이)
정답 보장	조건 만족 시에만	항상

판별 실전 팁: “지금의 선택이 나중의 선택 가능성을 제약하는가?” → 제약하면 DP, 독립적이면 그리디. 배낭 문제에서 분할 가능(Fractional)이면 그리디, 0/1이면 DP인 이유가 정확히 이것입니다.

대표 문제: 활동 선택(회의실 배정 — 종료 시각 기준 정렬), 거스름돈, 최소 회의실 수(우선순위 큐), 허프만 코딩, 크루스칼·프림 MST.

게임 적용: 타겟 선정(“가장 가까운 적”), 인벤토리 자동 정리, 스킬 로테이션. 다만 그리디 AI는 예측 가능해서 재미가 없다는 점도 고려해야 합니다.

9. DP — 4단계 접근과 유형표

적용 조건: ① 최적 부분 구조 ② 중복되는 부분 문제. ②가 없으면 DP가 아니라 그냥 분할 정복입니다(병합 정렬은 부분 문제가 겹치지 않으므로 DP가 아님).

구분	Top-down (메모이제이션)	Bottom-up (타뷸레이션)
구현	재귀 + 캐시	반복문 + 테이블
계산 범위	필요한 상태만	모든 상태
오버헤드	호출 비용, 스택 위험	없음, 더 빠름
메모리 최적화	어려움	슬라이딩 윈도우로 차원 축소 가능

접근 4단계: ① 상태 정의(가장 중요, 대부분 여기서 막힘) → ② 점화식 도출 → ③ 초기 조건 → ④ 순회 순서. dp[i][w] = i번째 물건까지 고려했을 때 무게 w 이하 최대 가치처럼 정의를 문장으로 소리 내어 말하는 것이 포인트입니다.

유형	상태 정의	복잡도
0/1 배낭	`dp[i][w]` = i개까지 고려, 무게 w 이하 최대 가치	$O(nW)$
LIS	`dp[i]` = i로 끝나는 최장 증가 부분수열 길이	$O(n^2)$ → 이분탐색 $O(n \log n)$
LCS	`dp[i][j]` = A의 i까지, B의 j까지 최장 공통 부분수열	$O(nm)$
편집 거리	`dp[i][j]` = A[..i] → B[..j] 최소 편집 횟수	$O(nm)$
동전 교환	`dp[amount]` = 금액을 만드는 최소 동전 수	$O(n \cdot amount)$
구간 DP	`dp[i][j]` = 구간 [i,j]의 최적값	$O(n^3)$
비트마스크 DP	`dp[mask][i]` = 방문 집합 mask, 현재 i (TSP)	$O(2^n n^2)$
트리 DP	`dp[node][state]` = 서브트리 최적값	$O(n)$

0/1 배낭 1차원 압축: dp[i][w]가 dp[i-1][*]만 참조하므로 압축 가능하되, 무게를 역순(W → w)으로 순회해야 합니다. 정순으로 하면 같은 물건을 여러 번 담아 무한 배낭이 됩니다. (역으로 무한 배낭은 정순)
피보나치 3단계: 단순 재귀 $O(2^n)$ → 메모이제이션 $O(n)$ → 직전 두 값만 유지해 공간 $O(1)$ (행렬 거듭제곱은 시간 $O(\log n)$)

게임 적용: 무게 제한 하 최적 아이템 조합, 제한된 스킬 포인트 배분, 예산 내 최대 효율 장비 조합.

10. 투 포인터 · 슬라이딩 윈도우 · 누적합

투 포인터: $O(n^2)$ 이중 루프를 $O(n)$으로 줄입니다. ① 양끝에서 마주 오기(정렬 배열의 두 수 합, 팰린드롬) ② 같은 방향(구간 합, 중복 제거, 플로이드 토끼-거북이 사이클 탐지 — $O(1)$ 공간). 설명의 핵심은 “왜 답을 놓치지 않는가”이며, 근거는 정렬 + 단조성입니다.
슬라이딩 윈도우: 투 포인터의 특수 형태로, 두 포인터가 같은 방향으로 움직이며 구간 상태를 유지합니다. 전체를 재계산하지 않고 sum += a[i] - a[i-k]로 $O(1)$ 갱신 → 전체 $O(n)$. 윈도우 내 최대값은 단조 덱으로 $O(1)$ 유지(각 원소가 한 번 들어가고 한 번 나가므로 총 $O(n)$).
누적합: sum(l..r) = prefix[r+1] - prefix[l], 전처리 $O(n)$ + 질의 $O(1)$. 전제는 배열이 변하지 않는 것입니다. 2차원은 포함-배제로, 반대로 차분 배열(Imos법) 은 구간 갱신을 $O(1)$로 처리합니다.

방법	구간 질의	값 갱신	난이도
누적합	$O(1)$	$O(n)$	하
펜윅 트리(BIT)	$O(\log n)$	$O(\log n)$	중
세그먼트 트리	$O(\log n)$	$O(\log n)$	상 (범용성 최고)

질의만 많으면 누적합, 갱신도 많으면 세그먼트 트리 — 이 트레이드오프가 핵심입니다. 게임 적용: 영향력 맵(Influence Map) + 2D 누적합으로 “가장 안전한 지점” 탐색, 프레임 타임 이동평균(프로파일러), 콤보 입력 윈도우 판정.

11. DFS & BFS

그래프 문제를 만나면 ① 방향성 ② 가중치 ③ 음수 가중치 ④ 정점·간선 규모 ⑤ 구하는 것(도달 가능성/최단 거리/모든 쌍/사이클/연결 요소) 5가지를 먼저 체크합니다.

구분	DFS	BFS
구현	스택 / 재귀	큐
최단 경로	보장 안 함	가중치 없을 때 보장
메모리	$O(깊이)$	$O(너비)$ — 넓으면 폭증
용도	모든 경로, 사이클 탐지, 위상 정렬, 연결 요소	최단 거리·최소 횟수, 레벨 처리, 플러드 필

BFS가 최단을 보장하는 이유: 거리 1인 정점 전부 → 거리 2인 정점 전부 순으로 방문하므로, 처음 도달한 시점이 곧 최단 거리입니다. 단 모든 간선 가중치가 동일해야 성립합니다.
실전 버그: visited는 큐에 넣는 시점에 체크해야 합니다. 꺼낼 때 체크하면 같은 정점이 큐에 여러 번 들어가 시간 초과의 흔한 원인이 됩니다.
0-1 BFS: 가중치가 0/1뿐이면 덱을 써서 0은 push_front, 1은 push_back → 거리 오름차순이 유지되어 $O(V+E)$로 다익스트라와 같은 결과를 냅니다.

게임 적용: BFS는 SRPG 이동 범위 표시, 플러드 필(물 퍼짐·영역 채우기), 폭발 전파. DFS는 절차적 미로 생성, 방 연결성 검증, 에셋 순환 참조 탐지, 스킬트리 선행 조건. 다중 시작점 BFS로 여러 적으로부터의 거리를 한 번에 계산해 위험도 맵을 만듭니다.

12. 다익스트라

시작점 거리 0·나머지 ∞로 초기화 → 미확정 정점 중 거리 최소를 선택(우선순위 큐) → 확정 후 인접 정점을 완화(Relaxation) → 반복. 우선순위 큐로 $O(E \log V)$이며, 밀집 그래프에서는 인접 행렬 $O(V^2)$가 오히려 유리합니다.

  
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;  // {거리, 정점}
dist[start] = 0;  pq.push({0, start});
while (!pq.empty()) {
    auto [d, u] = pq.top(); pq.pop();
    if (d > dist[u]) continue;          // ★ 오래된(stale) 항목 스킵
    for (auto [v, w] : adj[u]) {
        if (dist[u] + w < dist[v]) {
            dist[v] = dist[u] + w;
            pq.push({dist[v], v});
        }
    }
}

pair는 반드시 {거리, 정점} 순서로 넣어야 거리 기준 정렬이 됩니다.
STL 우선순위 큐는 decrease-key를 지원하지 않아 중복 push가 생깁니다. if (d > dist[u]) continue; 한 줄이 이를 걸러내며, 없으면 성능이 크게 나빠집니다.
음수 가중치에서 실패하는 이유: “한 번 확정한 거리는 더 짧아지지 않는다”는 그리디 가정이 깨지기 때문입니다. → 대안은 벨만-포드($O(VE)$, 음수 사이클 탐지 가능), SPFA, 플로이드-워셜($O(V^3)$, 경유지 k가 가장 바깥 루프).
경로 복원: 갱신 시 parent[v] = u를 기록해 도착점에서 거꾸로 따라간 뒤 뒤집습니다. 게임에서는 이게 AI 이동 경로 포인트 배열이 됩니다.

13. A* 와 NavMesh (게임 최중요)

\[f(n) = g(n) + h(n)\]

g(n)은 시작점부터의 실제 누적 비용, h(n)은 목표까지의 예상 비용(휴리스틱)입니다. f(n)이 최소인 노드를 먼저 확장하며, h(n)=0이면 정확히 다익스트라가 됩니다.

허용성(Admissible): h(n) ≤ 실제 최단 비용. 절대 과대평가하지 않아야 최적해가 보장됩니다. 과대평가하면 빠르지만 최단이 아닐 수 있습니다.
일관성(Consistent): h(n) ≤ cost(n,n') + h(n'). 만족하면 닫힌 목록 노드를 재방문할 필요가 없어 구현이 단순해집니다.
휴리스틱: 맨해튼(4방향), 유클리드(자유 방향), 옥타일(8방향). h에 1.001배를 곱하는 tie-breaking으로 동일 f 후보를 줄여 탐색을 가속할 수 있습니다.
Open List는 f 최소를 빨리 꺼내야 하므로 우선순위 큐, Closed List는 조회가 빨라야 하므로 해시셋/불리언 배열로 구현합니다.

상황	선택
가중치 없음 + 목표 1개	BFS
가중치 있음 + 모든 정점까지 거리	다익스트라
가중치 있음 + 목표가 특정 1곳	A*
음수 가중치 존재	벨만-포드
모든 쌍 최단 거리, V가 작음	플로이드-워셜

NavMesh와의 관계: NavMesh는 이동 가능 영역을 볼록 폴리곤으로 미리 분할한 그래프입니다(폴리곤=정점, 인접=간선). ① A*로 폴리곤 시퀀스(코리도) 탐색 → ② Funnel / String Pulling으로 경로 평활화. 넓은 평지를 폴리곤 하나로 표현하므로 타일 그리드보다 노드 수가 훨씬 적고 임의 방향 이동이 자연스럽습니다. A*는 전역 경로만 담당하고 실시간 유닛 충돌은 RVO/Detour Crowd가 처리하는 전역/지역 2계층 구조입니다.

AI 100마리로 프레임이 떨어질 때: ① 경로 요청 Time-slicing ② 워커 스레드 비동기 처리 ③ 리더 경로 공유 + 오프셋(플로킹) ④ 계층적 탐색(HPA*) ⑤ 거리·화면 여부에 따른 갱신 빈도 LOD ⑥ 목표가 하나이고 유닛이 매우 많으면(RTS) Flow Field — 목표에서 역방향 BFS로 방향 벡터 필드를 한 번 만들어 전부 공유, 유닛당 비용 $O(1)$.

14. 유형 판별 치트시트

문제의 신호	의심할 알고리즘
“최소 횟수”, 가중치 없음	BFS
“최단 거리”, 가중치 있음	다익스트라 / A*
“모든 경우”, “가능한 조합 전부”	완전 탐색 / 백트래킹
“최대/최소값” + 부분 문제 반복	DP
“정렬하면 뭔가 보인다”	그리디 / 투 포인터
“연속된 구간”	슬라이딩 윈도우 / 누적합
“K번째”, “조건 만족 최소값”, 범위가 큼	이분 탐색(매개변수 탐색)
“연결되어 있는가”, “그룹 개수”	DFS / BFS / Union-Find
“선행 조건”, “순서”	위상 정렬
“가장 큰/작은 것 반복 추출”	우선순위 큐(힙)
n ≤ 20, 부분집합	비트마스크

TIL(Today I Learned), 2026-07-29

This post is licensed under CC BY 4.0 by the author.