2026-07-28 TIL (106일차)

알고리즘

---

1. 전체 흐름 한눈에

8가지는 따로 있는 기법이 아니라 하나의 흐름으로 연결됩니다. 재귀로 “다 해보기”를 배우고 → 쓸데없는 가지를 자르면 백트래킹, 중복 계산을 저장하면 DP, 탐색 없이 규칙으로 고르면 그리디입니다.

순서	주제	핵심 한 줄	앞 주제와의 연결
1	재귀 (Recursion)	자기 자신을 호출하는 함수	모든 탐색의 기본 문법
2	정렬 (Sorting)	줄 세우기의 기술	분할 정복 = 재귀의 대표 사례
3	이진 탐색 (Binary Search)	반으로 쪼개면 답이 보인다	정렬이 전제 조건
4	완전 탐색 (Brute Force)	전부 다 해보면 된다	재귀로 모든 경우를 생성
5	백트래킹 (Backtracking)	불필요한 길은 가지 않는다	완전 탐색 + 가지치기
6	그리디 (Greedy)	매 순간 최선의 선택	탐색 없이 규칙으로 확정
7	DP 입문	같은 계산을 두 번 하지 마라	재귀의 중복 호출 제거
8	DP 활용	작은 답이 큰 답이 된다	점화식 유형 패턴화

---

2. 문제 접근 순서와 입력 크기 판단

문제를 받으면 항상 “완전 탐색으로 시간 내에 되나?”부터 계산합니다. 안 되면 그때 가지치기(백트래킹) → 중복 제거(DP) → 규칙 발견(그리디) → 답의 범위 탐색(이진 탐색) 순으로 전환합니다.

1초 ≈ 약 1억(10^8)번의 연산이 기준입니다.

N의 크기	허용 복잡도	떠올릴 것
N ≤ 10	$O(N!)$	순열, 완전 탐색
N ≤ 20	$O(2^N)$	부분집합, 비트마스크 DP
N ≤ 100	$O(N^3)$	플로이드 워셜, 구간 DP
N ≤ 2,000	$O(N^2)$	2차원 DP, LCS
N ≤ 100,000	$O(N \log N)$	정렬, 이진 탐색, 우선순위 큐
N ≤ 10,000,000	$O(N)$	투 포인터, 누적 합, 1차원 DP

---

3. 주제별 핵심

• 재귀: 필수 요소는 종료 조건(base case) 과 재귀식 두 개뿐입니다. 종료 조건을 먼저 쓰고, “n의 답을 n-1의 답으로 표현”하는 순서로 작성합니다. 호출마다 스택 프레임이 쌓이므로 공간 복잡도는 $O(깊이)$이며, Python은 sys.setrecursionlimit(10**6) 설정이 필요합니다.
• 정렬: 정렬은 목적이 아니라 도구입니다. 비교 기반 정렬의 하한은 $O(N \log N)$이고, 그보다 빠른 계수·기수 정렬은 비교를 하지 않기 때문에 가능합니다. 실전에서는 내장 정렬(Timsort)을 쓰고, 승부는 다중 기준 정렬 키를 어떻게 잡는가에서 갈립니다.
• 이진 탐색: 전제는 정렬 또는 단조성(monotonicity) 입니다. 실전 핵심은 매개변수 탐색 — “최댓값을 구하라”를 “이 값이 가능한가?(Yes/No)”라는 판정 문제로 바꾸는 기법입니다. lo = mid로 쓰면 무한 루프에 빠지므로 ±1을 반드시 붙입니다.
• 완전 탐색: 정답이 100% 보장되는 기준점입니다. 경우의 수를 수식으로 세운 뒤 숫자를 대입해 가능 여부를 먼저 판단하고, 도구(순열/조합/비트마스크/DFS·BFS)를 고릅니다. 부분집합은 for state in range(1 << n) 비트마스크가 정석입니다.
• 백트래킹: 선택 → 재귀 → 되돌리기 3박자가 전부입니다. 가지치기는 정답을 잃지 않으면서 탐색량만 줄입니다. 최악은 여전히 지수 시간이지만 실전에서는 통과합니다.
• 그리디: 성립 조건은 탐욕 선택 속성 + 최적 부분 구조이며, 반드시 반례를 먼저 찾아본 뒤 적용합니다. 짝꿍은 정렬과 우선순위 큐이고, 대부분 “무엇을 기준으로 정렬하느냐”가 문제의 본질입니다(회의실 배정 → 종료 시간 기준).
• DP 입문: 조건은 중복 부분 문제 + 최적 부분 구조입니다. Top-down(재귀+메모)과 Bottom-up(반복+테이블)은 결과가 같으니 편한 쪽을 쓰되 둘 다 가능해야 합니다.
• DP 활용: 실력 = 암기한 점화식 수 × 상태 정의 감각. 0/1 배낭, LIS, LCS, 편집 거리, 구간 DP, 비트마스크 DP를 유형으로 익힙니다. 점화식에 정보가 부족하면 차원을 늘립니다(dp[i] → dp[i][j]).

---

4. 반드시 외워야 하는 템플릿 2개

백트래킹 3박자

int n, m;
vector<int> path;
vector<vector<int>> result;
vector<bool> used;

void backtrack(int depth) {
    if (depth == m) {                    // 종료 조건
        result.push_back(path);          // vector 대입 = 값 복사 (Python의 path[:])
        return;
    }
    for (int c = 0; c < n; ++c) {
        if (used[c] || !promising(c)) continue;  // 가지치기

        path.push_back(c);               // 선택
        used[c] = true;

        backtrack(depth + 1);            // 재귀

        path.pop_back();                 // 되돌리기 ← 최다 실수
        used[c] = false;
    }
}

DP 4단계 (이 순서를 지키면 대부분 풀립니다)

1. 상태 정의 — dp[i]가 무엇인지 한 문장으로 쓴다 (여기에 시간을 가장 많이 쓸 것)
2. 점화식 — dp[i]를 더 작은 dp로 표현한다
3. 초기값 — 가장 작은 문제의 답을 직접 채운다
4. 계산 순서 — 필요한 값이 먼저 계산되도록 루프 방향을 정한다

---

5. 헷갈리는 개념 비교

비교	차이의 핵심
완전 탐색 vs 백트래킹	백트래킹은 가능성 없는 가지를 미리 자른다
백트래킹 vs DP	백트래킹은 경우를 나열, DP는 값을 재사용
그리디 vs DP	그리디는 한 선택만 보고 확정(증명 필요), DP는 모든 선택을 비교
이진 탐색 vs 매개변수 탐색	앞은 “값 찾기”, 뒤는 “조건을 만족하는 최적값 찾기”

---

6. 실수 노트

• 재귀: 종료 조건 누락, 리스트를 매번 복사해서 넘기기
• 정렬: 숫자를 문자열로 정렬("10" < "9"), 정렬 후 원래 인덱스 유실
• 이진 탐색: while lo <= hi와 lo < hi 템플릿 혼용, 탐색 범위를 좁게 잡아 답 누락
• 백트래킹: 상태 복구 누락, result.append(path)로 참조를 넣어 전부 빈 리스트가 되는 문제
• 그리디: 반례 검증 없이 제출, 정렬 기준 오류
• DP: 상태 정의를 건너뛰고 점화식부터 쓰기, 초기값 오류(최솟값 문제를 0으로 초기화), 0/1 배낭 1차원 구현에서 루프를 정순으로 돌려 물건 중복 사용

코드를 외우는 게 아니라 “이 문제는 왜 이 알고리즘인가”를 설명할 수 있으면 끝난 것입니다.