Algorithm Paradigms

분류: Layer 10 - 자료구조 & 알고리즘

Algorithm Paradigms (알고리즘 패러다임)

1. 한 줄 정의

알고리즘 패러다임은 문제를 직접 풀기보다 탐색해야 할 가능성의 수를 줄이는 사고 방식이다. Dynamic Programming, Greedy, Divide & Conquer, Backtracking은 모두 전수 탐색이 너무 커질 때 등장하지만, 줄이는 방식이 다르다.

Dynamic Programming(DP, 동적 프로그래밍): 같은 하위 문제를 다시 풀지 않도록 상태와 답을 저장한다.
Greedy(탐욕 알고리즘): 지금 하는 한 번의 선택이 나중에도 후회되지 않는다는 조건을 증명하고 되돌아가지 않는다.
Divide & Conquer(D&C, 분할 정복): 큰 입력을 서로 독립인 작은 문제로 쪼개고, 결과를 다시 합친다.
Backtracking(백트래킹): 가능한 선택지를 깊게 탐색하되, 제약을 위반한 가지는 즉시 버린다.

핵심은 이름을 외우는 것이 아니라 “이 문제에서는 무엇을 버려도 되는가?”를 판단하는 것이다.

이 문서는 L10의 마무리 토픽이다. 앞에서 배운 정렬·탐색의 Binary Search, 트리·그래프의 DFS와 Priority Queue는 여기서 독립 주제가 아니라 패러다임을 실현하는 도구로 다시 등장한다. 따라서 코드를 먼저 외우기보다, 각 패러다임이 어떤 탐색 공간을 버릴 권리를 얻는지부터 본다.

2. 왜 중요한가

같은 문제라도 패러다임 선택이 복잡도를 완전히 바꾼다. n개 아이템의 모든 부분집합은 2^n, 모든 순열은 n!개다. 입력이 조금만 커져도 전수 탐색은 실시간 시스템이나 코딩 테스트 제한 시간 안에 끝나지 않는다.

패러다임을 알면 문제를 보자마자 다음 질문을 던질 수 있다.

같은 상태를 반복해서 계산하고 있는가?
지금 최선의 선택이 전체 최적해 안에 반드시 포함되는가?
하위 문제가 서로 독립이라 병렬로 풀 수 있는가?
아직 완성되지 않은 해가 이미 제약을 위반했는가?

이 질문이 답을 좁힌다. DP, Greedy, D&C, Backtracking은 서로 경쟁하는 유행어가 아니라, 전수 탐색을 줄이는 네 가지 서로 다른 약속이다.

2.5. 선행 기술의 한계 - 네 패러다임의 등장 이유

알고리즘 패러다임은 “빠른 코딩 기법”으로 생긴 것이 아니다. 전수 탐색이 커질수록 같은 계산을 반복하고, 잘못된 선택까지 끝까지 따라가며, 독립적으로 나눌 수 있는 일을 한 덩어리로 처리하는 문제가 생겼다.

DP가 등장한 문제는 중복 계산이다. 피보나치 재귀에서 fib(3)은 여러 경로에서 반복 계산된다. 최단 경로, 문자열 비교, 배낭 문제도 겉으로는 선택지가 많아 보이지만 실제로는 같은 상태가 계속 다시 나타난다. DP의 철학은 “상태 공간을 정의하고, 각 상태의 답은 한 번만 계산한다”이다.

Greedy가 등장한 문제는 너무 많은 조합을 모두 비교하지 않아도 되는 경우다. 활동 선택 문제에서 가장 빨리 끝나는 활동을 고르면 뒤에 남는 시간 폭이 가장 크다. 이 선택은 나중에 손해가 되지 않음을 교환 논증(exchange argument)으로 보일 수 있다. Greedy의 철학은 “되돌아가지 않을 선택만 한다”이다.

D&C가 등장한 문제는 입력이 크지만 하위 문제가 서로 독립인 경우다. Merge Sort는 왼쪽 절반과 오른쪽 절반을 따로 정렬해도 서로의 내부 결정에 간섭하지 않는다. D&C의 철학은 “크기를 줄이고, 같은 모양의 문제를 풀고, 합산 비용을 통제한다”이다.

Backtracking이 등장한 문제는 모든 경우를 보아야 할 수 있지만 끝까지 볼 필요는 없는 경우다. N-Queens에서 같은 열이나 대각선에 퀸이 놓인 순간 그 아래 모든 배치는 실패한다. Backtracking의 철학은 “부분 해가 틀렸으면 그 하위 탐색 전체를 버린다”이다.

이 토픽이 없다면 최적화 문제는 쉽게 전수 탐색으로 회귀한다. 작은 예제에서는 답이 나오지만, 입력이 커지면 비용 최적화, 스케줄링, 문자열 비교, 경로 탐색이 모두 지수 시간으로 폭발한다.

3. 네 패러다임을 먼저 구분하기

패러다임 선택의 첫 질문

DP

같은 하위 상태가 반복되고, 상태의 답을 재사용할 수 있다.

중복 부분 문제와 최적 부분 구조가 모두 보일 때

Greedy

현재 선택을 고정해도 어떤 최적해 하나는 잃지 않는다.

탐욕 선택 성질을 반례 없이 설명하거나 증명할 수 있을 때

D&C

하위 문제가 서로 겹치지 않고 독립적으로 풀린다.

분할 비용과 합산 비용을 포함해도 전체 복잡도가 줄어들 때

Backtracking

부분 해를 만들며 탐색하고, 제약 위반 가지를 조기에 버린다.

모든 후보를 보아야 하지만 유효하지 않은 후보를 빨리 판별할 수 있을 때

판단 순서는 보통 다음처럼 잡는다.

1. 하위 문제가 반복되는가?
   - 예: DP 후보
   - 아니오: D&C 또는 Backtracking 후보

2. 한 번의 지역 선택을 되돌리지 않아도 되는가?
   - 예: Greedy 후보
   - 아니오: DP나 Backtracking으로 돌아간다

3. 하위 문제가 서로 독립인가?
   - 예: D&C 후보
   - 아니오: DP나 Backtracking 후보

4. 부분 해가 제약을 위반하면 그 아래를 모두 버릴 수 있는가?
   - 예: Backtracking 후보
   - 아니오: 전수 탐색, DP, 그래프 탐색 등 다른 모델을 검토한다

이 순서는 정답표가 아니라 오진 방지 절차다. 한 번에 패러다임 이름을 맞히려 하지 말고, 먼저 전수 탐색의 모양을 그린 뒤 “같은 상태를 합칠 수 있는가”, “선택 하나를 고정해도 되는가”, “절반이나 가지 하나를 증명하고 버릴 수 있는가”를 차례대로 반례로 흔든다. 반례를 만들 수 있으면 그 패러다임은 아직 증명된 선택이 아니다.

4. Dynamic Programming - 반복 상태를 한 번만 계산한다

4-1. 정의

Dynamic Programming은 문제를 상태(state) 로 나누고, 각 상태의 답을 저장해 재사용하는 방법이다. 여기서 상태란 “남은 문제를 결정하는 데 필요한 최소 정보”다. 예를 들어 계단 오르기에서 dp[i]는 i번째 계단에 도달하는 방법의 수이고, LCS(Longest Common Subsequence, 최장 공통 부분 수열)에서 dp[i][j]는 두 문자열의 앞 i, j글자만 보았을 때의 답이다.

DP가 성립하려면 두 조건이 필요하다.

중복 부분 문제(Overlapping Subproblems): 같은 상태가 여러 경로에서 반복 등장한다.
최적 부분 구조(Optimal Substructure): 전체 답이 하위 상태의 답으로 구성된다.

4-2. 등장한 문제

전수 재귀는 호출 트리를 계속 펼친다. 피보나치 수열을 단순 재귀로 계산하면 fib(5) 안에서 fib(3), fib(2)가 여러 번 다시 계산된다. 문제 크기가 커질수록 고유 상태 수보다 호출 횟수가 훨씬 빠르게 증가한다.

DP는 이 낭비를 제거한다. 호출 트리의 모든 노드를 계산하는 대신, 고유 상태만 계산하고 결과를 저장한다. 그래서 피보나치처럼 고유 상태가 0..n뿐인 문제는 지수 시간에서 선형 시간으로 줄어든다.

fib(5)의 호출 트리를 보면 중복이 눈에 보인다.

                fib(5)
              /        \
          fib(4)        fib(3)
         /     \       /     \
     fib(3)  fib(2)  fib(2) fib(1)
    /    \
 fib(2) fib(1)

순수 재귀는 같은 fib(3)과 fib(2)를 여러 번 계산한다. 하지만 실제로 필요한 고유 상태는 fib(0)부터 fib(5)까지 6개뿐이다. DP는 호출 트리를 모두 걷는 대신 고유 상태 그래프를 한 번씩 채운다.

이 차이는 입력이 조금만 커져도 체감된다.

계산 대상	순수 재귀 호출 수의 감각	DP가 실제로 채우는 고유 상태
`fib(10)`	수백 번	11개
`fib(30)`	수백만 번	31개
`fib(40)`	약 3억 번	41개

여기서 중요한 점은 “재귀를 반복문으로 바꿨다”가 아니다. 순수 재귀는 같은 질문을 여러 번 하고, DP는 같은 질문에 이름을 붙여 한 번만 답한다. 그래서 DP를 떠올릴 때는 먼저 “이 문제에서 같은 질문이 다시 등장하는가?”를 찾는다.

4-3. 핵심 철학

DP의 철학은 “미래에 다시 필요할 답을 지금 저장한다”이다. 단, 아무 값이나 저장하면 DP가 아니다. 먼저 상태의 의미를 좁혀야 한다.

좋은 DP 상태는 다음 질문에 답한다.

이 상태만 알면 이후 결정을 할 수 있는가?
같은 상태에 도달한 경로가 여러 개여도 답이 같은가?
상태 수가 입력 크기 안에서 감당 가능한가?

상태가 너무 작으면 필요한 정보가 빠져 틀리고, 너무 크면 상태 수가 폭발한다.

4-4. 해결 메커니즘

DP 구현은 보통 두 방식 중 하나다.

Memoization(메모이제이션): 재귀로 내려가며 계산한 값을 캐시에 저장한다. 필요한 상태만 풀지만 재귀 깊이 문제가 생길 수 있다.
Tabulation(타뷸레이션): 작은 상태부터 반복문으로 테이블을 채운다. 순서를 명확히 잡아야 하지만 스택 오버플로우가 없다.

둘의 차이는 “캐시를 쓰는가”가 아니라 계산 순서다. Memoization은 큰 문제에서 시작해 필요한 하위 상태로 내려간다. Tabulation은 기저 상태에서 시작해 큰 상태로 올라간다. JavaScript/TypeScript처럼 재귀 깊이에 민감한 환경에서는 입력이 커질 수 있으면 Bottom-Up을 먼저 고려한다.

선택 기준은 다음처럼 잡으면 된다.

상황	더 자연스러운 방식	이유
도달 가능한 상태가 전체보다 적다	Memoization	필요한 상태만 재귀적으로 계산한다
모든 상태를 결국 채워야 한다	Tabulation	반복문 순서가 명확하고 재귀 오버헤드가 없다
입력 크기가 커서 재귀 깊이가 위험하다	Tabulation	콜스택 한계를 피할 수 있다
상태 전이 순서를 바로 떠올리기 어렵다	Memoization으로 먼저 모델링	재귀 정의가 점화식을 더 직접적으로 드러낸다
공간 최적화가 중요하다	Tabulation + rolling row/state	필요한 이전 행/열만 남기기 쉽다

예를 들어 DFS처럼 실제로 방문되는 상태가 드문 그래프 DP라면 Memoization이 과한 테이블 생성을 피한다. 반대로 LCS, Knapsack처럼 행과 열을 거의 모두 채우는 문제는 Tabulation이 디버깅과 공간 최적화에 유리하다. 둘은 정답의 원리가 아니라 계산 순서의 선택이다.

// 계단 오르기: dp[i] = dp[i - 1] + dp[i - 2]
function climbStairs(n) {
  if (n <= 2) return n;

  let prev2 = 1; // dp[1]
  let prev1 = 2; // dp[2]

  for (let i = 3; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
}

console.log(climbStairs(5)); // 8

이 예제에서 전체 배열을 저장하지 않는 이유는 dp[i]가 직전 두 상태만 필요로 하기 때문이다. 이것이 DP의 공간 최적화다. 테이블을 없앤 것이 아니라, 필요한 상태만 남긴 것이다.

4-4-1. 2D DP 예제: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)는 두 문자열에서 순서는 유지하되 연속일 필요는 없는 공통 부분 수열의 최장 길이를 찾는 문제다. Git diff, 문자열 비교, DNA 서열 비교처럼 “두 시퀀스가 얼마나 비슷한가”를 볼 때 등장한다.

상태는 dp[i][j]: 첫 번째 문자열의 앞 i글자와 두 번째 문자열의 앞 j글자만 보았을 때의 LCS 길이다.

function lcs(a, b) {
  const dp = Array.from({ length: a.length + 1 }, () =>
    new Array(b.length + 1).fill(0),
  );

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1;
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }

  return dp[a.length][b.length];
}

console.log(lcs("ABCBDAB", "BDCAB")); // 4

문자가 같으면 두 문자열에서 그 문자를 함께 쓰므로 대각선 상태에 1을 더한다. 문자가 다르면 첫 번째 문자열의 마지막 글자를 버리는 경우와 두 번째 문자열의 마지막 글자를 버리는 경우 중 더 긴 답을 고른다. 이 예제는 DP가 1차원 배열만이 아니라 “남은 문제를 결정하는 두 축”을 상태로 잡을 수 있음을 보여준다.

4-4-2. Rolling row와 메모리 감각

2D DP를 그대로 만들면 상태 수가 곧 메모리다. LCS에서 길이 5,000인 문자열 두 개를 비교하면 (5000 + 1) * (5000 + 1)개, 약 2,500만 개 셀이 필요하다. Int32Array로만 잡아도 약 100MB이고, 일반 JavaScript 배열의 숫자 객체와 행 배열 오버헤드까지 포함하면 훨씬 커질 수 있다.

하지만 LCS 전이식은 현재 행을 계산할 때 직전 행과 현재 행의 왼쪽 값만 필요하다. 그래서 전체 테이블 대신 두 행만 유지할 수 있다.

function lcsRolling(a, b) {
  let prev = new Int32Array(b.length + 1);
  let curr = new Int32Array(b.length + 1);

  for (let i = 1; i <= a.length; i++) {
    for (let j = 1; j <= b.length; j++) {
      if (a[i - 1] === b[j - 1]) {
        curr[j] = prev[j - 1] + 1;
      } else {
        curr[j] = Math.max(prev[j], curr[j - 1]);
      }
    }

    [prev, curr] = [curr, prev];
    curr.fill(0);
  }

  return prev[b.length];
}

console.log(lcsRolling("ABCBDAB", "BDCAB")); // 4

이 방식은 O(a.length * b.length) 시간은 그대로지만 공간은 O(b.length)로 줄인다. 길이 5,000 기준으로 두 행은 약 2 * 5001 * 4 bytes, 즉 40KB 정도다. 단, 실제 LCS 문자열 자체를 복원해야 한다면 전체 테이블이나 별도의 경로 정보가 필요할 수 있다. 공간 최적화는 “답의 길이만 필요한가, 선택 경로까지 필요한가”를 먼저 확인한 뒤 적용한다.

4-5. 경계와 오해

DP는 “캐시를 쓰는 모든 코드”가 아니다. 같은 입력을 저장하는 일반 캐시와 달리, DP는 문제 자체를 상태 전이식으로 쪼갠다.

DP가 어울리지 않는 신호는 다음과 같다.

하위 문제가 서로 겹치지 않는다. 이 경우 D&C가 더 자연스럽다.
지금 선택이 항상 안전하다는 성질이 있다. 이 경우 Greedy가 더 단순하고 빠를 수 있다.
상태에 포함해야 할 정보가 너무 많아 상태 수가 전수 탐색과 비슷해진다.
가중치나 용량 범위가 너무 커서 O(n * W) 테이블을 만들 수 없다.

0/1 Knapsack은 Greedy와 DP의 경계를 보여준다. 가치/무게 비율이 가장 높은 아이템부터 넣는 방식은 직관적이지만, 아이템을 쪼갤 수 없으면 최적해를 놓친다. 이때 상태는 dp[i][capacity]: 앞 i개 아이템만 보고 용량 capacity에서 얻을 수 있는 최대 가치가 된다.

작은 반례를 보면 경계가 선명하다.

item	weight	value	value / weight
A	10	60	6.0
B	20	100	5.0
C	30	120	4.0

가방 용량이 50일 때 density Greedy는 A와 B를 골라 value 160에서 멈춘다. 하지만 최적해는 B와 C를 고르는 value 220이다. 아이템을 쪼갤 수 있는 fractional knapsack이면 Greedy가 맞지만, 0/1 Knapsack에서는 “쪼갤 수 없음” 때문에 상태를 들고 비교해야 한다.

1D DP로 줄일 때는 용량을 역순으로 돈다.

function knapsack01(items, capacity) {
  const dp = new Array(capacity + 1).fill(0);

  for (const item of items) {
    for (let w = capacity; w >= item.weight; w--) {
      dp[w] = Math.max(dp[w], dp[w - item.weight] + item.value);
    }
  }

  return dp[capacity];
}

역순으로 도는 이유는 같은 아이템을 한 번만 쓰기 위해서다. 정순으로 돌면 방금 갱신한 dp[w]를 다시 참조해 같은 아이템을 여러 번 넣는 unbounded knapsack처럼 바뀐다.

Knapsack의 위험은 시간보다 메모리에서 먼저 보일 때가 많다. n개 아이템과 용량 W를 그대로 2D 테이블로 만들면 상태 수는 n * W다.

조건	셀 수	`Int32Array` 기준 대략 메모리	해석
`n=100`, `W=10,000`	100만	약 4MB	실습과 일반 코딩 테스트에서 감당 가능
`n=200`, `W=100,000`	2,000만	약 80MB	런타임 제한에 걸리기 시작
`n=500`, `W=1,000,000`	5억	약 2GB	2D DP 자체를 다시 생각해야 하는 규모
1D 최적화, `W=100,000`	100,001	약 0.4MB	이전 item 행만 필요할 때 가능한 절감

그래서 0/1 Knapsack은 O(n * W)라고 외우는 데서 끝나면 위험하다. W는 아이템 개수가 아니라 용량의 숫자 크기다. 용량이 큰데 값의 합이 작으면 value 기준 DP, 즉 “무게가 아니라 총 가치 점수를 상태 축으로 잡는 DP”가 더 나을 수 있다. 아이템 수가 40개 안팎이면 meet-in-the-middle, 즉 아이템을 두 절반으로 나누어 각 절반의 가능한 선택을 만든 뒤 합치는 전략도 검토할 수 있다. DP를 고를 때는 “상태 수가 몇 개인가”를 실제 숫자로 먼저 계산한다.

4-6. 실패 신호와 개념 디버깅

DP가 틀릴 때는 긴 복구 절차보다 다음 네 가지를 먼저 본다.

상태 의미가 불명확하다: dp[i]가 무엇을 뜻하는지 문장으로 설명하지 못한다.
기저 사례가 빠졌다: 빈 문자열, 용량 0, 첫 행/첫 열 같은 최소 상태가 정의되지 않았다.
전이식이 현재 상태를 다시 참조한다: 0/1 Knapsack에서 용량을 정순으로 돌면 같은 아이템을 여러 번 쓴다.
구현 방식이 입력 크기와 맞지 않는다: Top-Down 재귀가 깊어져 콜스택을 넘으면 Bottom-Up으로 바꾼다.

5. Greedy - 되돌아가지 않을 선택만 한다

5-1. 정의

Greedy는 매 단계에서 현재 기준으로 가장 좋아 보이는 선택을 하고, 그 선택을 다시 취소하지 않는 전략이다. 빠른 이유는 비교해야 할 조합을 크게 줄이기 때문이다. 위험한 이유도 같다. 틀린 선택을 되돌리지 않기 때문에, 선택 기준이 조금만 잘못되어도 조용히 최적해를 놓친다.

5-2. 등장한 문제

모든 최적화 문제를 DP로 풀면 상태 테이블이 커지고 구현도 복잡해진다. 그런데 어떤 문제는 한 선택을 먼저 해도 최적해를 잃지 않는다. 활동 선택 문제에서는 가장 빨리 끝나는 활동을 고르면 남은 시간 구간이 최대화된다. 이 선택은 다른 최적해의 첫 활동과 교환해도 전체 활동 수를 줄이지 않는다.

Greedy는 이런 문제에서 등장한다. “모든 조합을 비교하지 않아도 되는 이유”를 증명할 수 있을 때만 쓴다.

5-3. 핵심 철학

Greedy의 철학은 “지역 최적이 전역 최적과 충돌하지 않는 경우만 믿는다”이다. 여기서 필요한 성질은 두 가지다.

탐욕 선택 성질(Greedy Choice Property): 지금 고른 선택이 어떤 전체 최적해 안에 포함될 수 있다.
최적 부분 구조: 그 선택 뒤에 남는 문제도 같은 방식으로 최적으로 풀 수 있다.

이 두 조건을 증명하기 어렵다면 Greedy는 후보일 뿐이다.

5-4. 해결 메커니즘

Greedy 구현은 보통 정렬과 한 번의 순회로 끝난다. 중요한 것은 “무엇을 기준으로 정렬하는가”다.

// Activity Selection: 종료 시간이 빠른 활동부터 고른다.
function selectActivities(activities) {
  const sorted = [...activities].sort((a, b) => a.end - b.end);
  const selected = [];
  let lastEnd = -Infinity;

  for (const activity of sorted) {
    if (activity.start >= lastEnd) {
      selected.push(activity);
      lastEnd = activity.end;
    }
  }

  return selected;
}

console.log(
  selectActivities([
    { name: "A", start: 1, end: 4 },
    { name: "B", start: 3, end: 5 },
    { name: "C", start: 5, end: 7 },
  ]).map((activity) => activity.name),
); // ["A", "C"]

시작 시간이 아니라 종료 시간으로 정렬하는 이유가 핵심이다. 빨리 끝나는 활동을 고를수록 뒤에 남는 선택 공간이 커지고, 이 선택은 최적해와 교환 가능하다.

반대로 시작 시간이 빠른 순서나 duration이 짧은 순서로 고르면 깨진다.

활동	start	end
A	1	10
B	2	3
C	3	4
D	4	5

시작 시간이 빠른 A를 먼저 고르면 답은 1개다. 종료 시간이 빠른 B, C, D를 고르면 3개를 배정할 수 있다. Greedy에서 중요한 것은 “빨리 고르는 것”이 아니라, 그 선택이 남은 문제를 가장 덜 해치는 기준인지다.

종료 시간 기준이 맞는 이유는 교환 논증으로 볼 수 있다. 어떤 최적해가 첫 활동으로 X를 골랐다고 하자. 전체 활동 중 가장 빨리 끝나는 활동을 E라고 하면 E.end <= X.end다. X 대신 E를 넣어도 뒤에 배치할 수 있던 활동들의 시작 시간은 더 빡빡해지지 않는다. 따라서 최적해 하나를 “첫 선택이 E인 최적해”로 바꿀 수 있고, 이 첫 선택을 고정한 뒤 남은 구간에 같은 논리를 반복할 수 있다. Greedy를 쓸 때 필요한 것은 이런 교환 가능한 이유이지, 정렬 코드 자체가 아니다.

5-5. 경계와 오해

Greedy는 “대충 빠른 근사”가 아니다. 최적해를 주장하려면 탐욕 선택 성질이 필요하다. 성질이 없으면 Greedy는 휴리스틱이다. 휴리스틱은 실용적일 수 있지만, 최적해 보장과는 다르다.

대표 반례는 비표준 동전 체계다.

function greedyCoin(amount, coins) {
  const result = [];
  for (const coin of [...coins].sort((a, b) => b - a)) {
    while (amount >= coin) {
      result.push(coin);
      amount -= coin;
    }
  }
  return result;
}

console.log(greedyCoin(6, [4, 3, 1])); // [4, 1, 1]
// 최적해는 [3, 3]이다.

0/1 Knapsack도 같은 경계에 있다. 가치/무게 비율이 높은 아이템부터 고르는 선택은 분수형 Knapsack에서는 맞지만, 아이템을 쪼갤 수 없는 0/1 Knapsack에서는 틀릴 수 있다. 입력에서 “나눌 수 있음”과 “원자적으로 선택해야 함”을 구분해야 한다.

5-6. 실패 신호와 개념 디버깅

Greedy가 위험한 신호는 다음과 같다.

작은 반례 하나로 결과가 최적해와 달라진다.
정렬 기준을 바꾸면 답이 크게 달라진다.
선택 후 남은 문제가 원래 문제와 같은 구조로 남지 않는다.
최적해가 반드시 필요하지만 탐욕 선택 성질을 설명하지 못한다.

디버깅은 운영 절차보다 반례 설계가 중요하다. 입력을 균등하게만 만들지 말고, 큰 아이템 하나와 작은 아이템 여러 개, 긴 구간 하나와 짧은 구간 여러 개처럼 Greedy 기준을 흔드는 사례를 만든다.

6. Divide & Conquer - 독립 문제로 쪼개고 다시 합친다

6-1. 정의

Divide & Conquer는 큰 문제를 같은 형태의 작은 하위 문제로 나누고, 각 하위 문제를 풀고, 결과를 합쳐 전체 답을 만드는 전략이다. 핵심은 하위 문제가 서로 독립이라는 점이다. 겹치는 하위 문제가 많다면 D&C가 아니라 DP 후보가 된다.

6-2. 등장한 문제

큰 입력을 처음부터 끝까지 한 덩어리로 처리하면 비교 횟수나 탐색 범위가 커진다. 정렬에서는 전체 배열을 바로 정렬하기 어렵지만, 반씩 나누면 각 절반은 더 작은 정렬 문제다. 탐색에서는 정렬된 배열 전체를 훑지 않고 절반씩 버릴 수 있다.

D&C는 입력 크기를 줄여 복잡도를 낮추기 위해 등장했다. 독립 하위 문제는 병렬 처리와도 잘 맞는다.

6-3. 핵심 철학

D&C의 철학은 “문제 크기를 줄이면 같은 규칙을 다시 적용할 수 있다”이다. 그래서 항상 세 단계를 묻는다.

Divide: 어떻게 나눌 것인가?
Conquer: 하위 문제를 어떻게 풀 것인가?
Combine: 하위 답을 합치는 비용은 얼마인가?

분할만 빠르고 합산이 비싸면 전체 알고리즘은 느리다. D&C는 분할과 합산을 함께 계산해야 한다.

6-4. 해결 메커니즘

Merge Sort는 가장 전형적인 D&C 예제다.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let i = 0;
  let j = 0;

  while (i < left.length && j < right.length) {
    result.push(left[i] <= right[j] ? left[i++] : right[j++]);
  }

  return result.concat(left.slice(i), right.slice(j));
}

console.log(mergeSort([38, 27, 43, 3])); // [3, 27, 38, 43]

Merge Sort의 점화식은 T(n) = 2T(n/2) + O(n)이다. 절반 크기 문제가 두 개 생기고, 합치는 데 전체 원소 수만큼 필요하다. 깊이는 log n, 각 깊이의 합산 비용은 n이므로 전체는 O(n log n)이다.

Binary Search도 D&C다. 다만 한 번에 한쪽 절반을 버리기 때문에 점화식은 T(n) = T(n/2) + O(1)이고, 결과는 O(log n)이다.

function binarySearch(sorted, target) {
  let low = 0;
  let high = sorted.length - 1;

  while (low <= high) {
    const mid = low + Math.floor((high - low) / 2);

    if (sorted[mid] === target) return mid;
    if (sorted[mid] < target) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }

  return -1;
}

console.log(binarySearch([2, 5, 8, 12, 16, 23, 38], 16)); // 4

손으로 따라가면 D&C의 “버리는 힘”이 보인다.

단계	`low`	`high`	`mid` 값	판단
1	0	6	12	16이 더 크므로 왼쪽 절반 버림
2	4	6	23	16이 더 작으므로 오른쪽 버림
3	4	4	16	찾음

Merge Sort는 두 절반을 모두 풀고 합친다. Binary Search는 정렬이라는 전제 덕분에 한쪽 절반을 증명하고 버린다. 같은 D&C라도 a=2인지 a=1인지가 복잡도를 갈라놓는다.

조금 더 일반화하면 D&C 복잡도는 자주 T(n) = aT(n/b) + f(n) 모양으로 쓴다.

기호	의미
`a`	하위 문제의 개수
`b`	각 하위 문제의 크기 축소 비율
`f(n)`	나누고 합치는 데 드는 비용

Master Theorem은 이 형태의 점화식을 빠르게 분석하는 도구다. 먼저 n^(log_b a)를 계산하고, 그것과 f(n) 중 어느 쪽이 더 큰지 비교한다. Merge Sort는 a=2, b=2, f(n)=n이라 n^(log_2 2)=n과 합산 비용이 균형을 이뤄 O(n log n)이 된다. Binary Search는 a=1, b=2, f(n)=1이라 각 단계에서 절반만 남아 O(log n)이 된다.

점화식을 외우기 어렵다면 재귀 트리로 먼저 본다.

알고리즘	한 단계 뒤 남는 문제	깊이	한 깊이의 비용	전체 직관
Binary Search	절반 크기 1개	`log n`	`O(1)`	매번 한쪽을 버려 `O(log n)`
Merge Sort	절반 크기 2개	`log n`	`O(n)`	모든 깊이마다 전체 원소를 병합
불균형 분할	`n-1` 크기 1개	`n`	`O(n)` 가능	Quick Sort 최악처럼 `O(n^2)` 위험

이 표는 a, b, f(n)이 왜 필요한지 보여준다. 하위 문제 개수(a)가 많아도 각 깊이의 총량이 통제되면 괜찮고, 하위 문제 하나만 남아도 크기가 거의 줄지 않으면 깊이가 길어져 실패한다.

6-5. 경계와 오해

D&C는 “재귀를 쓰면 다 되는 방식”이 아니다. 재귀가 있어도 하위 문제가 겹치면 DP가 더 적합하고, 하위 문제가 독립이어도 합산 비용이 너무 크면 이득이 사라진다.

경계는 다음과 같다.

겹치는 하위 문제: 피보나치 순수 재귀는 D&C처럼 보이지만 같은 값을 반복 계산하므로 DP가 맞다.
불균형 분할: Quick Sort에서 피벗이 계속 최솟값이나 최댓값이면 깊이가 n까지 늘어 O(n^2)이 된다.
비싼 합산: 분할은 잘했지만 합치는 과정이 O(n^2)이면 전체 복잡도가 다시 커진다.
공유 상태: 하위 문제가 서로 독립이 아니면 병렬화하기 어렵고, 결과도 순서에 의존할 수 있다.

6-6. 실패 신호와 개념 디버깅

D&C가 흔들리는 신호는 다음과 같다.

분할 후 하위 문제가 같은 형태가 아니다.
base case가 없어 재귀가 끝나지 않거나, 너무 늦게 끝난다.
Combine 단계에서 정렬성, 순서, 중복 제거 조건이 깨진다.
분할이 한쪽으로 치우쳐 재귀 깊이가 입력 크기만큼 커진다.

디버깅할 때는 재귀 전체를 한 번에 보지 않는다. n=1, n=2, n=4처럼 작은 입력에서 Divide, Conquer, Combine이 각각 어떤 값을 만드는지 분리해서 본다.

7. Backtracking - 틀린 가지를 빨리 버린다

7-1. 정의

Backtracking은 해를 한 조각씩 만들면서 탐색하고, 부분 해가 제약을 위반하면 이전 선택으로 되돌아가는 전략이다. DFS(Depth-First Search, 깊이 우선 탐색)와 비슷하게 깊게 들어가지만, 모든 노드를 방문하는 것이 목적이 아니라 불가능한 가지를 가지치기(pruning) 하는 것이 목적이다.

7-2. 등장한 문제

순열, 조합, N-Queens, 스도쿠처럼 후보가 폭발하는 문제는 단순한 공식으로 바로 답을 만들기 어렵다. 하지만 부분적으로 만든 답이 이미 실패인지 판단할 수 있는 경우가 많다. N-Queens에서 같은 열에 퀸이 두 개 있으면 그 아래 행은 더 볼 필요가 없다.

Backtracking은 “모두 보되, 실패가 확정된 순간 멈춘다”는 전략으로 등장했다.

7-3. 핵심 철학

Backtracking의 철학은 “선택은 임시이며, 상태는 반드시 되돌릴 수 있어야 한다”이다. 그래서 구현은 거의 항상 다음 세 단계로 읽는다.

1. Choose: 현재 선택을 상태에 반영한다.
2. Explore: 다음 단계로 들어간다.
3. Unchoose: 선택 전 상태로 되돌린다.

여기에 Pruning 조건이 붙는다. Pruning은 성능 최적화가 아니라 문제 정의의 일부다. 어떤 부분 해가 절대 완성될 수 없는지 알아야 탐색 공간을 줄일 수 있다.

7-4. 해결 메커니즘

function permutations(nums) {
  const result = [];
  const used = new Array(nums.length).fill(false);

  function backtrack(current) {
    if (current.length === nums.length) {
      result.push([...current]);
      return;
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;

      used[i] = true; // Choose
      current.push(nums[i]);

      backtrack(current); // Explore

      current.pop(); // Unchoose
      used[i] = false;
    }
  }

  backtrack([]);
  return result;
}

console.log(permutations([1, 2, 3]).length); // 6

이 코드는 모든 순열을 만들기 때문에 시간 복잡도는 O(n!)이다. Backtracking이 항상 다항 시간으로 바꿔주는 것은 아니다. 다만 제약 조건이 강한 문제에서는 많은 가지를 초기에 버릴 수 있다.

순열과 조합은 탐색 상태가 비슷해 보여도 경계가 다르다. 순열은 [1, 2]와 [2, 1]을 다른 결과로 보지만, 조합은 같은 결과로 본다. 그래서 조합에서는 used 배열보다 다음에 볼 시작 위치(start index) 를 넘겨 중복 순서를 막는다.

function combinations(nums, k) {
  const result = [];

  function backtrack(start, current) {
    if (current.length === k) {
      result.push([...current]);
      return;
    }

    const need = k - current.length;
    for (let i = start; i <= nums.length - need; i++) {
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  }

  backtrack(0, []);
  return result;
}

console.log(combinations([1, 2, 3, 4], 2));
// [[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

여기서 backtrack(i + 1, current)가 핵심 경계다. i + 1부터 보므로 이미 고른 원소를 다시 고르지 않고, 앞쪽 원소로 되돌아가지 않으므로 [2, 1] 같은 중복 순서도 만들지 않는다. 반대로 backtrack(0, current)로 매번 처음부터 돌면 중복과 재사용이 섞이고, backtrack(i, current)로 호출하면 같은 원소를 다시 고를 수 있어 “조합 with repetition” 문제가 된다. 부분집합(subset) 생성도 같은 원리로 start를 넘긴다.

N-Queens는 pruning의 효과를 더 잘 보여준다. n x n 체스판에 퀸 n개를 서로 공격하지 않게 놓아야 한다. 같은 열, 같은 대각선에 이미 퀸이 있으면 그 아래 배치는 더 볼 필요가 없다.

function countNQueens(n) {
  let count = 0;
  const cols = new Set();
  const diagDown = new Set(); // row - col
  const diagUp = new Set(); // row + col

  function backtrack(row) {
    if (row === n) {
      count++;
      return;
    }

    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diagDown.has(row - col) || diagUp.has(row + col)) {
        continue;
      }

      cols.add(col);
      diagDown.add(row - col);
      diagUp.add(row + col);

      backtrack(row + 1);

      cols.delete(col);
      diagDown.delete(row - col);
      diagUp.delete(row + col);
    }
  }

  backtrack(0);
  return count;
}

console.log(countNQueens(4)); // 2

여기서 cols, diagDown, diagUp은 이미 실패가 확정된 선택을 O(1)에 판별하기 위한 상태다. 단순 순열 생성은 Choose/Explore/Unchoose를 보여주지만, N-Queens는 Backtracking의 핵심인 Pruning을 보여준다.

Pruning의 효과는 “빨라질 수도 있다”가 아니라 탐색해야 할 상태 수를 직접 줄이는 데서 나온다. n=8에서 각 행마다 아무 열이나 고르는 방식은 최대 8^8, 약 1,677만 개 배치를 만든다. 같은 열을 금지해 순열만 보아도 8! = 40,320개로 줄고, 대각선 충돌을 부분 해 단계에서 버리면 완성 후보까지 내려가기 전에 더 많은 가지가 사라진다. 반대로 pruning 검사가 O(n)으로 비싸거나 너무 늦게 실행되면 줄인 가지보다 검사 비용이 커질 수 있다. 그래서 Backtracking에서는 “무엇을 버릴 수 있는가”와 “그 판단을 얼마나 싸게 할 수 있는가”를 같이 설계한다.

7-5. 경계와 오해

Backtracking은 DP나 Greedy를 대체하는 만능 탐색이 아니다.

같은 상태가 반복되고 답을 재사용할 수 있으면 DP가 더 낫다.
한 선택이 항상 안전하다면 Greedy가 더 빠르다.
제약 위반을 초기에 판별할 수 없으면 사실상 전수 탐색과 같다.
공유 상태를 되돌리지 않으면 이후 탐색이 오염된다.

N-Queens에서 열, 좌하향 대각선, 우하향 대각선을 Set으로 관리하는 이유는 Pruning을 O(1)에 하기 위해서다. Pruning 자체가 느리면 가지를 줄여도 전체 시간은 잘 줄지 않는다.

7-6. 실패 신호와 개념 디버깅

Backtracking이 틀릴 때는 대부분 상태 복구 문제다.

push 뒤에 대응되는 pop이 없다.
결과에 현재 배열 참조를 그대로 넣어 모든 결과가 같은 값으로 바뀐다.
다음 재귀의 시작 인덱스를 잘못 잡아 중복 조합이 생긴다.
Pruning 조건이 너무 강해 유효한 해까지 버린다.
Pruning 조건이 너무 약해 전수 탐색과 거의 같아진다.

디버깅은 작은 입력에서 탐색 트리를 손으로 그리는 방식이 가장 빠르다. n=3에서 어떤 선택이 들어가고 빠지는지 로그로 확인하면 상태 오염을 찾기 쉽다.

8. 패러다임 선택 경계

질문	예라고 답하면	아니오라면
같은 상태가 반복되는가?	DP 후보	D&C, Greedy, Backtracking 후보
현재 선택이 나중에도 안전한가?	Greedy 후보	DP나 Backtracking 후보
하위 문제가 서로 독립인가?	D&C 후보	DP나 Backtracking 후보
부분 해가 틀렸는지 빨리 알 수 있는가?	Backtracking 후보	전수 탐색 또는 다른 모델 검토
최적해가 꼭 필요한가?	DP, 증명된 Greedy, 정확한 D&C	휴리스틱 Greedy도 가능

중요한 것은 한 문제에 패러다임이 하나만 붙는다는 뜻이 아니다. Binary Search on Answer는 가능한 답의 범위를 이진 탐색으로 줄이고, 각 후보가 가능한지는 별도 판정 함수로 검사한다. A* 탐색은 시작점에서 온 실제 비용은 기록하고, 목표까지 남은 예상 비용은 휴리스틱으로 고른다. 결합 문제도 결국 각 부분이 어떤 약속 위에 있는지 설명할 수 있어야 한다.

패턴을 고를 때는 구현 템플릿보다 실패 조건을 먼저 묻는다.

문제 신호	먼저 의심할 패턴	확인해야 할 약속
후보 답이 숫자 범위 안에 있다	Binary Search on Answer	판정 함수가 단조인가
같은 `(위치, 남은 조건)`이 반복된다	DP	그 상태의 답을 경로와 무관하게 재사용할 수 있는가
지금 선택을 고정해도 손해가 없다	Greedy	교환 논증이나 반례 부재를 설명할 수 있는가
부분 해가 이미 불가능함을 안다	Backtracking	pruning을 싸게 판별하고 상태를 되돌릴 수 있는가
목표까지의 거리 감각이 있다	A*	휴리스틱이 실제 남은 비용을 과대평가하지 않는가

이 표는 정답표가 아니라 오진 방지 장치다. 예를 들어 “답을 이진 탐색할 수 있어 보인다”는 말은 충분하지 않고, 후보를 한쪽으로 움직일 때 가능/불가능이 한 번만 바뀌는지까지 확인해야 한다.

8-1. 결합 예제: Binary Search on Answer

Binary Search on Answer는 배열 안에서 값을 찾는 것이 아니라, 정답이 될 수 있는 숫자 범위를 이진 탐색한다. 조건은 하나다. 후보를 한쪽으로 움직일 때 가능/불가능이 한 번만 바뀌어야 한다. 최소 용량처럼 “가능한 최소값”을 찾는 문제에서는 x가 가능하면 더 큰 값도 가능한 경우가 많고, 최대 거리처럼 “가능한 최대값”을 찾는 문제에서는 x가 가능하면 더 작은 값도 가능한 경우가 많다. 방향은 달라도 중요한 성질은 가능 영역과 불가능 영역 사이에 단일 경계가 있다는 점이다. 이런 성질을 단조 판정(monotonic predicate)이라고 한다.

예를 들어 weights = [3, 2, 2, 4, 1, 4]를 3일 안에 순서대로 배송할 때 필요한 최소 선박 용량을 찾는다고 하자. 용량이 6이면 가능하고 7도 가능하다. 용량이 5이면 불가능하고 4도 불가능하다. 이 “가능/불가능” 경계가 정렬된 것처럼 보이기 때문에 답 공간을 이진 탐색할 수 있다.

function canShip(weights, days, capacity) {
  let usedDays = 1;
  let load = 0;

  for (const weight of weights) {
    if (load + weight > capacity) {
      usedDays++;
      load = 0;
    }
    load += weight;
  }

  return usedDays <= days;
}

function minCapacity(weights, days) {
  let low = Math.max(...weights);
  let high = weights.reduce((sum, weight) => sum + weight, 0);

  while (low < high) {
    const mid = low + Math.floor((high - low) / 2);
    if (canShip(weights, days, mid)) {
      high = mid;
    } else {
      low = mid + 1;
    }
  }

  return low;
}

console.log(minCapacity([3, 2, 2, 4, 1, 4], 3)); // 6

작은 후보를 직접 찍어 보면 단조성이 보인다.

후보 용량	3일 안에 가능한가	이유
5	아니오	`[3,2]`, `[2]`, `[4,1]`, `[4]`로 4일 필요
6	예	`[3,2]`, `[2,4]`, `[1,4]`로 3일
7	예	용량을 늘렸으므로 6에서 가능했던 배치 유지

여기서 D&C는 답 범위를 반씩 줄이고, Greedy에 가까운 판정 함수는 현재 날짜에 실을 수 있을 만큼 싣는다. 핵심 실패 신호는 판정 함수가 단조가 아닌 경우다. capacity=6은 가능한데 capacity=7이 불가능해지는 문제가 있다면 이진 탐색으로 답 경계를 찾을 수 없다.

8-2. 결합 예제: A* 탐색

A*는 그래프 탐색에 Greedy 판단을 섞은 방식이다. 각 후보 노드에 대해 f(n) = g(n) + h(n)을 계산한다. g(n)은 시작점에서 현재 노드까지 실제로 온 비용이고, h(n)은 현재 노드에서 목표까지 남았다고 추정하는 비용이다. 격자에서 상하좌우로만 움직인다면 Manhattan distance가 대표적인 h(n) 후보가 된다. Manhattan distance는 |x1 - x2| + |y1 - y2|로 계산하는 격자 거리이며, 대각선 이동이 없고 한 칸 비용이 1이면 장애물을 무시한 최단 거리의 하한이 된다.

작은 격자에서 시작점이 (0,0), 목표가 (4,4)라고 하자. (1,0)까지 온 실제 비용은 1이고 목표까지 Manhattan distance는 7이므로 f=8이다. (0,1)도 f=8이다. 반면 벽을 피해 돌아가느라 (2,0)까지 실제 비용이 4로 늘었다면 남은 추정 거리가 6이어도 f=10이 되어 우선순위가 밀린다. A*는 “지금까지 많이 돌아온 경로”와 “목표에서 멀어 보이는 경로”를 동시에 벌점 처리한다.

값	의미	패러다임 관점
`g(n)`	지금까지 확정된 실제 비용	DP처럼 노드별 best-known cost를 저장한다
`h(n)`	목표까지 남은 비용의 추정	Greedy처럼 목표에 가까워 보이는 후보를 우선한다
`f(n)`	다음에 확장할 후보의 우선순위 기준	탐색 공간을 줄이는 결합 기준

구현 관점에서는 Priority Queue가 f(n)이 가장 작은 후보를 먼저 꺼낸다. 앞선 Tree & Graph 토픽의 Priority Queue가 여기서는 “가장 급한 작업”이 아니라 “현재 가장 promising한 경로 후보”를 고르는 장치가 된다.

단, h(n)이 실제 남은 비용을 과대평가하면 최단 경로 보장이 깨질 수 있다. admissible은 h(n)이 실제 남은 최단 비용보다 크지 않다는 뜻이다. 목표 노드를 우선순위 큐에서 꺼냈을 때 “더 싼 미탐색 경로가 없다”고 확정하려면 이 조건이 필요하다.

반례도 작게 만들 수 있다. 시작점 S에서 목표 G로 바로 가는 간선 비용이 10이고, S -> A -> G 경로 비용이 2 + 2 = 4라고 하자. 그런데 휴리스틱이 h(A)=100이라고 과대평가하면 A*는 A의 f=2+100을 너무 나쁘게 보고 직접 경로 G를 먼저 확정할 수 있다. 실제 최단 경로는 A를 거치는 4인데도 휴리스틱 때문에 10을 고르는 것이다. A*가 빠른 이유는 휴리스틱을 믿기 때문이고, A*가 깨지는 이유도 휴리스틱을 너무 믿기 때문이다.

8-3. 새 문제를 볼 때의 결정 절차

패러다임 선택은 보통 구현 템플릿이 아니라 전수 탐색을 줄이는 근거에서 시작한다. 새 문제를 보면 먼저 가장 단순한 전수 탐색을 말로 적는다. “모든 부분집합을 본다”, “모든 순서를 본다”, “모든 경로를 본다”, “모든 답 후보를 본다”처럼 후보 공간을 드러내면 어떤 낭비가 반복되는지 보인다.

그다음 버릴 수 있는 것을 하나만 고른다. 같은 (index, capacity)가 반복되면 DP 상태로 합친다. 가장 빨리 끝나는 활동처럼 한 선택을 고정해도 남은 문제가 손해 보지 않으면 Greedy를 의심한다. 정렬된 배열이나 단조 판정처럼 한쪽 절반을 증명하고 버릴 수 있으면 D&C나 Binary Search on Answer를 쓴다. 아직 확정 답은 아니지만, 같은 열·대각선 충돌처럼 부분 해의 실패를 즉시 알 수 있으면 Backtracking으로 가지를 자른다.

마지막으로 숫자를 세고 반례를 만든다. DP라면 상태 수가 n * W처럼 감당 가능한지, Greedy라면 작은 반례 하나에도 깨지지 않는지, D&C라면 분할 깊이와 Combine 비용이 전체를 지배하지 않는지, Backtracking이라면 pruning 검사가 줄이는 가지보다 싸게 동작하는지 확인한다. 이 세 단계가 빠지면 패러다임 이름은 맞아 보여도 실제 복잡도나 정답 보장이 틀릴 수 있다.

9. 짧은 실패 신호 모음

목표는 명령어를 외우는 것이 아니라 어떤 개념이 깨졌는지 빠르게 찾는 것이다.

패러다임	실패 신호	먼저 볼 개념
DP	일부 경계 입력만 틀린다	상태 정의, 기저 사례, 전이 순서
DP	입력이 커지면 스택이 터진다	Top-Down 재귀 깊이, Bottom-Up 전환
DP	메모리가 먼저 터진다	상태 수, rolling row, `n * W` 규모
Greedy	대부분 맞지만 반례 하나에서 최적해를 놓친다	탐욕 선택 성질, 교환 논증
Greedy	정렬 기준을 바꾸면 답이 크게 달라진다	선택 기준이 문제의 최적성과 연결되는지
D&C	재귀가 끝나지 않거나 한쪽으로만 깊어진다	base case, 균형 분할
D&C	합치는 단계에서 결과가 깨진다	Combine 불변식
결합 패턴	이진 탐색 답 범위가 흔들린다	단조 판정 함수
결합 패턴	휴리스틱 경로가 최단 경로를 놓친다	A*의 admissible heuristic
Backtracking	결과가 중복되거나 모두 같은 배열처럼 보인다	Unchoose, 결과 복사
Backtracking	조합에서 중복 또는 재사용이 생긴다	`start` index 경계
Backtracking	너무 느리다	Pruning 조건의 강도와 비용

10. 학습 체크리스트

Algorithm Paradigms 체크

DP 상태를 한 문장으로 정의하고, 그 상태 수를 계산할 수 있는가?
Memoization과 Tabulation의 차이를 구현 방식이 아니라 계산 순서로 설명할 수 있는가?
2D DP를 rolling row로 줄여도 되는지 필요한 이전 상태를 설명할 수 있는가?
Greedy를 쓰기 전에 탐욕 선택 성질이나 반례 탐색을 먼저 확인하는가?
D&C에서 Divide, Conquer, Combine 각각의 비용을 따로 계산할 수 있는가?
새 문제에서 전수 탐색의 후보 공간과 버릴 수 있는 근거를 먼저 적는가?
Binary Search on Answer에서 판정 함수가 단조인지 확인하는가?
Backtracking 코드에서 Choose, Explore, Unchoose가 서로 대응되는지 확인하는가?
조합과 부분집합에서 start index가 중복 순서를 막는 이유를 설명할 수 있는가?
패러다임 이름보다 어떤 탐색 공간을 줄였는지 먼저 설명할 수 있는가?

11. 핵심 키워드

키워드	의미
State	DP에서 남은 문제의 답을 결정하는 최소 정보
Recurrence	현재 상태의 답을 더 작은 상태의 답으로 표현한 식
Base Case	더 쪼개지 않고 바로 답을 아는 최소 상태
Memoization	Top-Down DP. 재귀 결과를 저장해 중복 계산을 막는 방식
Tabulation	Bottom-Up DP. 작은 상태부터 테이블을 채우는 방식
Rolling Row	2D DP에서 필요한 직전 행/현재 행만 남겨 공간을 줄이는 방식
Overlapping Subproblems	같은 하위 문제가 여러 경로에서 반복 등장하는 성질
Optimal Substructure	전체 최적해가 하위 문제의 최적해로 구성되는 성질
Greedy Choice Property	지금의 지역 최선 선택이 어떤 전체 최적해에 포함될 수 있는 성질
Exchange Argument	Greedy 선택을 최적해의 선택과 바꿔도 손해가 없음을 보이는 증명 방식
Divide	문제를 같은 형태의 작은 하위 문제로 나누는 단계
Combine	하위 답을 합쳐 전체 답을 만드는 단계
Master Theorem	`T(n) = aT(n/b) + f(n)` 형태의 D&C 점화식을 분석하는 정리
Monotonic Predicate	답 후보가 커지거나 작아질 때 가능/불가능이 한 방향으로만 바뀌는 판정
A* Heuristic	목표까지 남은 비용을 추정해 다음 탐색 후보의 우선순위를 정하는 값
Admissible Heuristic	A*에서 실제 남은 최단 비용을 과대평가하지 않는 휴리스틱
Pruning	제약을 위반한 탐색 가지를 조기에 버리는 것
Start Index	조합·부분집합에서 이미 본 앞쪽 원소를 다시 보지 않게 하는 경계
Unchoose	Backtracking에서 선택 전 상태로 되돌리는 단계

12. 참고 소스

Bellman 1954 - Theory of Dynamic Programming: DP가 다단계 의사결정 문제에서 어떤 원리로 등장했는지 볼 수 있다.
MIT OpenCourseWare - Introduction to Algorithms: D&C, DP, Greedy를 대학 알고리즘 수업 흐름으로 복습하기 좋다.
OpenStax - Algorithmic Paradigms: 여러 패러다임의 정의와 차이를 입문 수준에서 비교한다.
Wikipedia - Master theorem: D&C 점화식 분석의 표준 형태를 빠르게 확인할 수 있다.
FreeCodeCamp - Backtracking Algorithms Explained: N-Queens를 통해 Choose, Explore, Unchoose 흐름을 직관적으로 볼 수 있다.

13. 한 줄 요약

DP는 반복 상태를 기억하고, Greedy는 후회하지 않을 선택만 고정하고, D&C는 독립 문제로 쪼개고, Backtracking은 틀린 가지를 되돌린다. 네 패러다임의 차이는 코드 모양이 아니라 어떤 탐색 공간을 줄일 수 있다고 믿는가에 있다.