CS for DEV

Theme

1.3 알고리즘 설계 패러다임 — 문제 구조가 해법을 고른다 ​

알고리즘 목록을 외우는 것과 새 문제를 푸는 것은 다른 능력이다. 이 문서는 분할 정복·동적 계획법·그리디·백트래킹을 각각 "어떤 문제 구조의 신호를 보고 선택하는가 → 어떻게 동작하는가 → 언제 실패하는가"의 틀로 세운다. 목표는 처음 보는 실무 문제에서 구조 신호를 읽어 패러다임을 고르고, 선택이 틀렸을 때 그것을 알아차리는 것이다.

학습 목표 ​

  • 네 가지 설계 패러다임을 각각의 성립 조건(부분 문제의 독립성, 최적 부분 구조, 중복 부분 문제, 그리디 선택 속성)으로 구분해 설명한다.
  • 주어진 문제에서 구조 신호를 식별해 적절한 패러다임을 선택하고, 그 선택을 반례 또는 논증으로 정당화한다.
  • 그리디가 최적을 놓치는 문제와 동적 계획법이 성립하지 않는 문제를 반례로 판별한다.
  • 백트래킹의 탐색 공간이 지수적으로 폭발하는 구조를 식별하고 가지치기의 효과를 평가한다.

배경: 왜 이것이 존재하는가 ​

대부분의 흥미로운 문제는 해의 후보가 지수적으로 많다. n개 작업의 순서는 n!가지, 부분집합은 2ⁿ가지다. 전부 시도하는 것(brute force)은 항상 정확하지만 n이 조금만 커져도 불가능해진다. 알고리즘 설계 패러다임이란 결국 지수적 탐색 공간을 어떻게 다항 시간 안에 다루는가에 대한 서로 다른 전략이다.

  • 분할 정복은 공간을 독립인 조각으로 쪼개 각각 정복한다.
  • 동적 계획법은 탐색 공간 안의 중복을 발견해 같은 계산을 한 번만 한다.
  • 그리디는 매 단계 국소 최선의 선택이 전역 최선으로 이어진다는 것을 증명할 수 있을 때, 탐색 자체를 생략한다.
  • 백트래킹은 공간을 다 줄일 수 없을 때, 가망 없는 가지를 일찍 잘라내며 탐색한다.

핵심은 이 전략들이 문제의 구조적 성질에 대한 조건부 계약이라는 점이다. 조건이 성립하지 않는 문제에 패러다임을 강요하면 틀린 답(그리디)이나 지수 시간(중복 없는 메모이제이션)이 나온다. 그래서 각 패러다임을 "무엇을 하는가"보다 "무엇이 성립해야 쓸 수 있는가"로 기억해야 한다.

핵심 개념 ​

각 패러다임을 같은 틀로 정리한다: 선택 신호 → 동작 모델 → 대표 사례 → 실패 조건.

분할 정복 — 부분 문제가 독립일 때 ​

선택 신호: 문제를 작은 같은 꼴의 문제들로 쪼갰을 때, 조각들이 서로 겹치지 않고 독립적으로 풀린다. 조각의 답을 합치는 비용이 감당 가능하다.

동작 모델: 크기 n을 크기 n/b짜리 a개로 나누고, 재귀적으로 푼 뒤, f(n) 비용으로 합친다. 총비용 T(n) = aT(n/b) + f(n)은 마스터 정리(master theorem)로 닫힌 꼴을 얻는다. 유도보다 결과의 감각이 중요하다.

재귀 구조예시결과
반으로 나눠 한쪽만 (a=1, b=2, f=O(1))이진 탐색O(log n)
반으로 나눠 양쪽 다 + 선형 병합 (a=2, b=2, f=O(n))병합 정렬O(n log n)
반으로 나눠 양쪽 다 + 상수 병합 (a=2, b=2, f=O(1))트리 순회O(n)

대표 사례: 병합 정렬과 퀵 정렬(분할 기준의 차이 — 병합은 자리로 나누고 정렬하며 합치고, 퀵은 값으로 나누어 합치는 비용을 없앤다), 이진 탐색, 그리고 사고방식으로서는 "데이터를 쪼개 병렬로 처리하고 결과를 모은다"는 분산 배치 처리의 원형이기도 하다(챕터 17에서 다룬다).

실패 조건: 쪼갠 부분 문제들이 겹칠 때. 피보나치를 fib(n) = fib(n-1) + fib(n-2)로 쪼개면 두 가지가 fib(n-2)를 공유한다. 이때 분할 정복은 같은 계산을 지수적으로 반복한다 — 그리고 이것이 다음 패러다임의 출발점이다.

동적 계획법 — 겹치는 부분 문제를 한 번만 풀기 ​

선택 신호 두 가지가 모두 필요하다.

  1. 최적 부분 구조(optimal substructure): 전체 최적해가 부분 문제의 최적해로 조립된다.
  2. 중복 부분 문제(overlapping subproblems): 재귀 전개에서 같은 부분 문제가 반복 등장한다.

동작 모델: 부분 문제의 답을 저장해(메모이제이션 또는 테이블) 각 부분 문제를 정확히 한 번 푼다. 실행 시간은 "서로 다른 부분 문제의 수 × 부분 문제당 비용"으로 떨어진다. 중복의 효과는 극적이다. 같은 재귀 구조에 저장만 더한 피보나치를 Node.js v24.14.0(Apple M5 Pro)에서 측정하면:

naive fib(40) = 102334155: 488.8ms   // 부분 문제 수: 약 3.3억 번의 호출
memo  fib(40) = 102334155: 0.020ms   // 부분 문제 수: 40개

동적 계획법(dynamic programming, DP)의 본질은 저장이라는 기법이 아니라 상태 설계다. "부분 문제를 무엇으로 정의하는가"가 곧 답이다. 대표 사례인 편집 거리(edit distance)로 보면 — 문자열 a의 앞 i글자를 b의 앞 j글자로 바꾸는 최소 편집 횟수를 d[i][j]로 정의하는 순간, 마지막 연산이 삽입/삭제/치환 중 하나라는 사실에서 점화식이 나온다.

js
// edit-distance.mjs — node edit-distance.mjs 로 실행
function editDistance(a, b) {
  const m = a.length, n = b.length;
  // d[i][j] = a[0..i)를 b[0..j)로 만드는 최소 편집 횟수
  const d = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
  for (let i = 0; i <= m; i++) d[i][0] = i; // 전부 삭제
  for (let j = 0; j <= n; j++) d[0][j] = j; // 전부 삽입
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      const substitute = d[i - 1][j - 1] + (a[i - 1] === b[j - 1] ? 0 : 1);
      d[i][j] = Math.min(d[i - 1][j] + 1, d[i][j - 1] + 1, substitute);
    }
  }
  return d[m][n];
}
console.log(editDistance('kitten', 'sitting')); // 3 (k→s, e→i, +g)

부분 문제 수 m×n, 부분 문제당 O(1) — 지수적 탐색 공간이 O(mn)으로 접혔다. 편집 거리와 그 사촌인 최장 공통 부분열(LCS)은 diff 도구, 맞춤법 교정, 유사도 검색의 근간이다(git의 기본 diff는 같은 문제를 다른 전략으로 푸는 Myers 알고리즘을 쓴다 — 참고 자료 참조).

top-down(재귀 + 메모) 대 bottom-up(테이블 채우기): 답은 같고 트레이드오프만 다르다. top-down은 점화식을 그대로 옮겨 적어 자연스럽고 필요한 부분 문제만 계산하지만, 재귀 깊이 한계(1.4에서 실측)와 호출 오버헤드가 있다. bottom-up은 순회 순서를 직접 설계해야 하지만 스택 안전하고, 배열 순차 접근이라 1.2의 논리대로 캐시 친화적이며, 직전 행만 유지하는 식의 공간 절약이 쉽다.

실패 조건:

  • 최적 부분 구조가 없을 때. 반례 — 그래프의 최장 단순 경로(같은 정점을 두 번 안 지나는). "s→t 최장 경로 = s→m 최장 + m→t 최장"이 성립하지 않는다. 두 부분 경로가 정점을 공유하면 합친 것이 단순 경로가 아니기 때문이다. 부분 문제들이 "정점을 안 겹쳐야 한다"는 제약으로 얽혀 독립성이 깨진 것이고, 실제로 이 문제는 NP-난해다.
  • 상태 공간 자체가 지수적일 때. 저장할 부분 문제 수가 2ⁿ이면 메모이제이션은 지수 시간을 지수 공간과 맞바꿀 뿐이다. DP의 이득은 어디까지나 "서로 다른 부분 문제 수가 다항"일 때 나온다.

그리디 — 탐색을 생략해도 된다는 증명이 있을 때 ​

선택 신호: 매 단계에서 국소적으로 최선인 선택을 하면, 남은 문제가 같은 꼴의 더 작은 문제가 되고, 그 선택이 최적해를 망치지 않는다(그리디 선택 속성, greedy choice property).

동작 모델: 정렬 또는 우선순위 큐로 "지금 최선"을 정의하고, 선택 → 축소를 반복한다. 보통 O(n log n) — DP가 상태 공간 전체를 채우는 것과 비교하면 압도적으로 싸다. 대신 정당성의 부담이 알고리즘에서 증명으로 옮겨 간다. 표준 증명 기법은 교환 논증(exchange argument)이다: 임의의 최적해를 가져와, 그리디의 선택과 다른 첫 지점을 그리디의 선택으로 교환해도 나빠지지 않음을 보인다. 귀납적으로 그리디 해 전체가 최적과 같아진다.

대표 사례 — 인터벌 스케줄링(interval scheduling): 겹치지 않게 최대 개수의 작업을 고르는 문제. "가장 일찍 끝나는 작업부터"가 최적이다. 교환 논증이 한 문장으로 된다: 최적해의 첫 작업을 가장 일찍 끝나는 작업으로 바꿔도, 더 일찍 끝나므로 뒤의 어떤 작업과도 새로 충돌하지 않는다.

js
// intervals.mjs — node intervals.mjs 로 실행
function maxNonOverlapping(intervals) {
  const byEnd = [...intervals].sort((a, b) => a.end - b.end); // 종료 시각 기준
  const chosen = [];
  let lastEnd = -Infinity;
  for (const iv of byEnd) {
    if (iv.start >= lastEnd) { chosen.push(iv); lastEnd = iv.end; }
  }
  return chosen;
}

const jobs = [
  { name: 'A', start: 0, end: 6 },
  { name: 'B', start: 1, end: 4 },
  { name: 'C', start: 3, end: 5 },
  { name: 'D', start: 5, end: 7 },
  { name: 'E', start: 8, end: 9 },
];
console.log(maxNonOverlapping(jobs).map((j) => j.name)); // [ 'B', 'D', 'E' ]

직관적으로 그럴듯한 다른 기준들 — "가장 짧은 것부터", "가장 일찍 시작하는 것부터" — 은 모두 반례가 있다. 그럴듯함과 증명의 거리가 그리디의 위험이다.

같은 골격의 다른 사례로 다익스트라 최단 경로(미방문 정점 중 가장 가까운 것을 확정 — 1.4에서 정당성 조건과 함께), 허프만 부호(빈도가 가장 낮은 두 노드를 합침 — 챕터 3에서 구현), 최소 신장 트리의 Kruskal/Prim이 있다.

실패 조건 — 그리디 선택이 미래의 더 좋은 조합을 막을 때. 동전 교환 반례를 실행해 보면:

js
// coins.mjs — node coins.mjs 로 실행 (coinDP는 아래 접힌 구현 참조)
// 액면 [1, 3, 4]로 6을 만드는 최소 동전 수
console.log(coinGreedy([1, 3, 4], 6)); // [ 4, 1, 1 ] — 3개 (큰 동전부터)
console.log(coinDP([1, 3, 4], 6));     // [ 3, 3 ]    — 2개 (최적)
coinGreedy / coinDP 전체 구현
js
function coinGreedy(coins, amount) {
  const sorted = [...coins].sort((a, b) => b - a);
  const used = [];
  let rest = amount;
  for (const c of sorted) {
    while (rest >= c) { used.push(c); rest -= c; }
  }
  return rest === 0 ? used : null;
}

function coinDP(coins, amount) {
  // best[a] = 금액 a를 만드는 최소 동전 수, pick[a] = 그때 마지막으로 쓴 동전
  const best = new Array(amount + 1).fill(Infinity);
  const pick = new Array(amount + 1).fill(-1);
  best[0] = 0;
  for (let a = 1; a <= amount; a++) {
    for (const c of coins) {
      if (c <= a && best[a - c] + 1 < best[a]) {
        best[a] = best[a - c] + 1;
        pick[a] = c;
      }
    }
  }
  if (best[amount] === Infinity) return null;
  const used = [];
  for (let a = amount; a > 0; a -= pick[a]) used.push(pick[a]);
  return used;
}

4를 집는 국소 최선이 3+3이라는 전역 최선을 막았다. 흥미로운 것은 통용 화폐 체계([1, 5, 10, 50, 100, …])에서는 그리디가 최적이라는 점이다 — 그리디의 정당성이 알고리즘이 아니라 입력 데이터의 성질에 달려 있다는 뜻이고, 데이터가 바뀌면(이벤트 쿠폰 액면, 요금제 조합) 어제 맞던 그리디가 오늘 틀린다.

백트래킹 — 잘라내며 탐색하기 ​

선택 신호: 해가 일련의 선택으로 구성되고, 부분 선택만 보고도 "이 방향엔 답이 없다"를 판정할 수 있다. 최적화 구조(DP·그리디)가 없어 탐색이 불가피한 제약 충족 문제(constraint satisfaction)가 주 무대다.

동작 모델: 깊이 우선으로 선택을 쌓아가되, 제약 위반이 확정되는 즉시 그 가지 전체를 포기하고 되돌아간다(backtrack). 최악은 여전히 지수 시간이다 — 백트래킹은 복잡도를 낮추는 기법이 아니라 탐색 공간의 실제 방문량을 줄이는 기법이고, 성능은 전적으로 가지치기(pruning)의 힘에 달려 있다. 스도쿠, 배치 문제, SAT 솔버의 골격(DPLL)이 모두 이 구조다. 여기에 "지금까지 찾은 최선보다 나빠질 수밖에 없는 가지"를 자르는 하한 계산을 더하면 분기 한정법(branch and bound)이 된다.

실무에서 가장 자주 만나는 백트래킹은 직접 쓴 코드가 아니라 정규식 엔진이다. 백트래킹 기반 정규식 엔진은 (a|a)* 같은 패턴에서 같은 문자열을 지수적으로 많은 방식으로 매칭 시도할 수 있고, 매칭 실패 입력에서 전체 탐색을 다 해 보고서야 실패를 보고한다. 공격자가 이런 입력을 보내는 것이 ReDoS다. 이것은 "중복 부분 문제를 저장 없이 재탐색하는" 구조로, 챕터 2에서 오토마타 이론과 함께 구조적 원인과 해법(NFA 시뮬레이션)을 다룬다.

실패 조건: 가지치기 조건이 약해 탐색이 지수 그대로 남을 때. 부분 선택에서 위반을 조기 판정할 수 없는 문제라면 백트래킹은 brute force와 다르지 않다.

실무 관점 ​

문제에서 구조 신호 읽기 ​

처음 보는 문제 앞에서 던질 질문의 순서다.

  1. 해가 선택의 나열인가? 후보가 조합적으로 많은가? — 그렇다면 이 문서의 영역이다.
  2. 국소 최선이 전역 최선을 보장하는가? 교환 논증을 스케치해 본다. 성립하면 그리디(가장 싸다). 반례가 하나라도 나오면 즉시 포기한다.
  3. 최적 부분 구조 + 중복 부분 문제가 있는가? 재귀로 문제를 정의해 보고, 같은 부분 문제가 반복 등장하며 그 수가 다항이면 DP.
  4. 둘 다 아니면 제약으로 가지치기하는 백트래킹, 그것도 못 버티는 규모면 정확한 최적을 포기하는 단계다 — 근사·휴리스틱·전용 솔버. 이 판단의 이론적 근거(NP-난해성 식별)는 챕터 2에서 다룬다.

실무 문제에 대응시켜 보면: 회의실/작업자 배정은 인터벌 스케줄링 계열(그리디), 텍스트 비교·버전 병합은 편집 거리/LCS 계열(DP), 제한 예산에서 캐시할 항목 고르기는 배낭 문제 계열(DP), 배포·마이그레이션 순서는 의존성 그래프의 위상 정렬(1.4)이다. 패턴 매칭이 아니라 구조 신호(독립성, 중복, 교환 가능성)의 확인이 판단의 근거가 되어야 한다 — 같은 "스케줄링"이라도 제약이 하나 추가되면(작업 간 의존, 가변 소요 시간) 문제의 클래스가 바뀐다.

패러다임은 조합된다 ​

실전 알고리즘은 순종이 드물다. Timsort는 분할 정복(병합)에 입력 적응(run 감지)을 결합했고, 다익스트라는 그리디에 자료구조(힙)를 결합했으며, SAT 솔버는 백트래킹에 학습(절 학습)을 결합했다. 패러다임을 배타적 분류가 아니라 조합 가능한 부품으로 다루면, "이 라이브러리 함수가 왜 이렇게 동작하는가"를 읽는 도구가 된다.

흔한 오판 ​

  • 그럴듯한 그리디를 증명 없이 배포. 통용 동전처럼 "우연히 맞는 데이터"에서 검증하면 통과한다. 반례 탐색(작은 입력 전수 비교: 그리디 결과 vs brute force 결과)을 테스트로 두는 것이 실용적 방어다.
  • DP를 "테이블 채우는 기술"로 암기. 본질은 상태 정의다. 상태가 잘못되면(정보 부족) 점화식이 성립하지 않고, 상태가 과하면(정보 과잉) 공간이 폭발한다.
  • 지수적 최악을 가진 코드의 방치. 백트래킹류 로직(정규식 포함)이 외부 입력을 받는다면, 최악 입력이 언젠가 도착한다고 가정하고 시간 제한·입력 제한·엔진 교체를 검토한다.

정리 ​

  • 네 패러다임은 지수적 탐색 공간에 대한 서로 다른 전략이다: 독립이면 쪼개고(분할 정복), 겹치면 저장하고(DP), 증명되면 생략하고(그리디), 안 되면 잘라내며 탐색한다(백트래킹).
  • 각 패러다임은 문제 구조에 대한 조건부 계약이다. 분할 정복은 부분 문제의 독립성, DP는 최적 부분 구조 + 다항 개수의 중복 부분 문제, 그리디는 교환 논증으로 증명되는 선택 속성을 요구한다.
  • 그리디의 정당성은 입력 데이터의 성질에 의존할 수 있다(동전 체계). 데이터가 바뀌면 재검증해야 한다.
  • DP의 본질은 저장이 아니라 상태 설계다. top-down과 bottom-up은 같은 답의 다른 실행 전략이며 스택·캐시·공간 트레이드오프로 고른다.
  • 백트래킹의 성능은 가지치기가 결정하며, 최악은 지수 시간으로 남는다. 외부 입력이 최악을 유발할 수 있는 경로(정규식 등)는 방어가 필요하다.

확인 문제 ​

1. 결제 시스템에 "포인트 쿠폰 액면 [1000, 7000, 9000]원을 조합해 결제액을 정확히 채우되 쿠폰 개수를 최소화"하는 로직이 큰 액면 우선 그리디로 구현되어 있고, 테스트도 통과해 운영 중이다. 이 구현의 문제를 반례로 보이고, 어떤 구조 확인이 설계 단계에서 빠졌는지, 무엇으로 교체해야 하는지 설명하라.

정답과 해설

반례: 결제액 14000원. 그리디는 9000 → 1000×5로 6장을 쓰지만 최적은 7000×2로 2장이다(본문 [1,3,4]로 6 반례와 동일 구조). 빠진 확인: 그리디 선택 속성의 증명 — 통용 화폐처럼 각 액면이 하위 액면의 배수 관계에 가까운 canonical 체계에서는 그리디가 최적이지만, 임의 액면 집합에서는 성립 보장이 없다. 쿠폰 액면은 마케팅이 정하는 값이라 언제든 non-canonical해진다. 교체: 금액을 상태로 하는 DP(coinDP와 동일, 상태 수 = 결제액/최소 단위)로 바꾸고, 회귀 방지로 작은 금액 전수에 대해 brute force와 결과를 비교하는 테스트를 둔다.

2. "그래프에서 두 노드 사이의 최장 단순 경로"를 편집 거리처럼 DP로 풀려던 동료가 "부분 문제로 쪼개지는데 답이 계속 틀린다"고 한다. 이 문제에서 DP의 어떤 전제가 무너지는지 설명하고, 같은 그래프에서 "최단 경로"는 왜 DP·그리디가 성립하는지 대비해 보라.

정답과 해설

최장 단순 경로는 최적 부분 구조가 없다. s→t 최장 경로가 m을 지난다고 해도, 그것이 "s→m 최장 + m→t 최장"으로 분해되지 않는다 — 두 부분 경로가 정점을 공유하면 이어 붙인 결과가 단순 경로가 아니게 되므로, 부분 문제들이 "서로 어떤 정점을 썼는가"라는 전역 제약으로 얽힌다. 상태에 방문 집합을 넣으면 상태 수가 2ⁿ이 되어 DP의 이득이 사라진다(이 문제는 NP-난해로, 해밀턴 경로의 일반화다). 반면 최단 경로(음수 간선 없음)는 부분 경로를 교체해도 제약이 얽히지 않는다 — 최단 경로의 부분 경로는 그 자체로 최단이어야 하고(아니라면 바꿔치기로 더 짧아져 모순), 이 성질이 다익스트라의 그리디와 벨만-포드의 DP를 모두 정당화한다. "부분해가 서로 자원을 공유·경쟁하는가"가 구조 판별의 실용적 질문이다.

3. 사용자 입력을 검증하는 정규식 ^(\w+\s?)*$이 특정 입력(공백 없는 긴 문자열 + 끝에 특수문자)에서 요청을 수 초씩 물고 있는 것이 발견됐다. 이 현상을 백트래킹 패러다임의 언어로 설명하고 — 어떤 탐색 공간이 왜 폭발하는가, 가지치기는 왜 작동하지 않는가 — 단기 대응을 제시하라.

정답과 해설

(\w+\s?)*에서 \s?가 선택적이므로, 연속된 단어 문자를 그룹 반복 경계로 나누는 방법이 조합적으로 많다(길이 n 문자열의 분할 방법은 2ⁿ⁻¹ 규모). 끝의 특수문자 때문에 전체 매칭은 반드시 실패하는데, 백트래킹 엔진은 실패를 확정하려면 모든 분할을 다 시도해야 한다. 조기 판정 조건이 없다 — 어떤 분할이든 마지막 문자에 도달하기 전까지는 유효해 보이므로 가지치기가 작동하지 않고, 같은 접미사에 대한 매칭 시도가 저장 없이 지수적으로 반복된다(중복 부분 문제를 DP 없이 재탐색하는 구조). 단기 대응: (1) 중첩 수량자를 제거한 동치 패턴으로 수정(^\w+(\s\w+)*\s?$ 같은 모호성 없는 형태), (2) 입력 길이 상한, (3) 매칭 시간 제한 또는 백트래킹 없는 엔진(RE2 계열)으로 교체. 구조적 원인(NFA 시뮬레이션 대 백트래킹)은 챕터 2에서 다룬다.

참고 자료 ​

  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms 4th ed. (2022) — 분할 정복(4장, 마스터 정리 포함), 동적 계획법(14장), 그리디(15장)의 표준 서술과 정당성 증명.
  • Kleinberg, Tardos, Algorithm Design (2005) — 교환 논증과 인터벌 스케줄링을 포함한 그리디 증명 기법(4장), DP의 상태 설계 관점(6장)이 특히 좋다. 문제에서 구조를 읽는 훈련이라는 이 문서의 관점과 같은 노선이다.
  • Eugene Myers, An O(ND) Difference Algorithm and Its Variations (1986) — git 기본 diff의 원 논문. 편집 거리를 편집 그래프의 최단 경로로 재정식화해, DP 테이블 전체를 채우지 않고 답에 도달하는 과정을 보여 준다(1.4의 그래프 환원과 이어진다).
  • Russ Cox, Regular Expression Matching Can Be Simple And Fast (2007) — 백트래킹 정규식 엔진의 지수 폭발을 실측과 함께 해부한 글. 챕터 2 실습(NFA 엔진 구현)의 예습 자료.
  • Tim Peters, listsort.txt — 패러다임 조합(분할 정복 + 적응 + 그리디한 run 병합 정책)의 실물 사례로 다시 읽어 볼 가치가 있다.