언제 욕심내고 언제 기억하는가 - 이름과 비용: 알고리즘 ep.03

눈앞에서 가장 좋아 보이는 선택이 항상 옳지는 않습니다. 언제 옳은지가 문제입니다.

그리디는 두 조건 위에서만 작동합니다

그리디(greedy) 는 매 단계에서 그 순간 최선인 선택을 하고, 한 번 한 선택은 되돌리지 않는 방법입니다.

되돌리지 않기 때문에 빠릅니다. 그리고 되돌리지 않기 때문에 위험합니다. 이 방법이 정답을 보장하려면 두 가지가 성립해야 합니다.

탐욕 선택 속성(greedy choice property) 은 각 단계의 지역적 최선이 전체 최적해의 일부가 된다는 성질입니다. 지금 고른 것을 나중에 후회하지 않는다는 보장입니다.

최적 부분 구조(optimal substructure) 는 전체의 최적해가 부분 문제의 최적해로 이루어진다는 성질입니다. 하나를 고르고 남은 문제를 같은 방식으로 풀면 된다는 뜻입니다.

두 번째 조건은 동적 계획법도 요구합니다. 둘을 가르는 것은 첫 번째 조건입니다. 지역적 최선이 항상 안전한지, 아니면 여러 선택지를 다 따져봐야 하는지가 여기서 갈립니다.

증명 대신 반례를 찾습니다

두 조건 중 최적 부분 구조는 대체로 눈에 보이지만, 탐욕 선택 속성은 성립하는지 아닌지가 문제마다 다릅니다. 여기서 확인할 것은 탐욕 선택 속성이 성립하는지 실무에서 어떻게 판단하느냐입니다.

엄밀히 증명하려면 교환 논법 같은 도구가 필요합니다. 실무에서는 순서를 바꾸는 편이 빠릅니다. 반례를 먼저 찾아보고, 못 찾으면 그리디를 씁니다. 반례 하나면 그리디를 버릴 근거로 충분하고, 못 찾았다면 적어도 손으로 확인한 범위에서는 안전하기 때문입니다.

동전 문제가 표준적인 예입니다. 액면가가 500, 100, 50, 10원이고 목표가 1,260원이면 큰 것부터 고르는 방식이 최적입니다. 각 액면가가 그보다 작은 액면가의 배수 관계로 맞물려 있기 때문입니다.

액면가를 1, 3, 4로 바꾸고 목표를 6으로 두면 달라집니다.

큰 것부터 고르면 4를 쓰고 남은 2를 1 두 개로 채워 동전 세 개입니다. 3을 두 개 쓰면 두 개로 끝납니다. 첫 선택에서 이미 최적해를 벗어났고, 되돌리지 않는 방식이라 회복할 방법이 없습니다.

반례를 찾는 요령이 몇 가지 있습니다. 작은 입력부터 손으로 계산해봅니다. 조건을 극단으로 밀어봅니다. 어느 하나가 압도적으로 크거나 작은 경우를 넣어봅니다. 대부분의 잘못된 그리디는 크기가 열 이하인 입력에서 무너집니다.

그리디가 확실히 통하는 유형은 이미 알려져 있는 편입니다. 끝나는 시각이 이른 것부터 고르는 회의실 배정, 무게당 가치가 높은 것부터 담는 분할 가능 배낭 문제가 그렇습니다. 정렬 기준을 정하고 나면 한 번 훑어서 끝납니다.

회의실 배정은 그대로 실무 문제이기도 합니다. 예약이 겹치지 않게 최대한 많이 넣는 계산이 회의실 예약 화면이나 장비 대여 일정에서 필요한데, 끝나는 시각 순으로 정렬해 한 번 훑으면 답이 나옵니다.

동적 계획법은 중복을 기억으로 없앱니다

그리디가 깨진다면 여러 선택지를 다 따져봐야 합니다. 그대로 재귀로 펼치면 지수 시간이 됩니다. 그런데 펼쳐놓고 보면 같은 부분 문제가 반복해서 등장합니다.

피보나치 수를 그냥 재귀로 계산하면 fib(5)를 구하는 동안 fib(2)가 세 번 계산됩니다. N이 커지면 이 중복이 지수적으로 불어납니다.

동적 계획법(dynamic programming) 은 한 번 계산한 부분 문제의 답을 저장해 재사용합니다. 적용 조건은 두 가지입니다. 최적 부분 구조가 있어야 하고, 부분 문제가 겹쳐야 합니다.

겹치지 않으면 저장할 이유가 없습니다. 병합 정렬은 부분 문제로 쪼개지지만 서로 겹치지 않아서 동적 계획법이 아닙니다.

동적 계획법을 직접 구현하지 않아도 결과물은 자주 봅니다. 두 파일의 차이를 보여주는 diff는 가장 긴 공통 부분 수열을 구하는 계산이고, 검색어의 오타를 고쳐 제안하는 기능은 편집 거리를 계산합니다. 둘 다 표를 채워 나가며 답을 구합니다.

두 가지 구현 방향

메모이제이션(memoization) 은 재귀를 그대로 두고 결과를 캐시에 저장하며 위에서 아래로 내려갑니다.

function fib(n, memo = new Map()) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const value = fib(n - 1, memo) + fib(n - 2, memo);
  memo.set(n, value);
  return value;
}

타뷸레이션(tabulation) 은 작은 문제부터 순서대로 배열을 채우며 아래에서 위로 올라갑니다.

function fib(n) {
  if (n <= 1) return n;
  let prev = 0;
  let curr = 1;
  for (let i = 2; i <= n; i++) {
    [prev, curr] = [curr, prev + curr];
  }
  return curr;
}

메모이제이션은 점화식을 그대로 옮기면 되니 사고 흐름에 가깝고, 필요한 부분 문제만 계산합니다. 대신 재귀 깊이 제한에 걸릴 수 있습니다.

타뷸레이션은 스택을 쓰지 않고 대체로 상수 계수가 작습니다. 자료구조 시리즈 ep.01 크기가 접근법을 정한다에서 본 공간 최적화도 이쪽이 적용하기 쉽습니다. 예시 코드처럼 이전 두 값만 들고 있으면 배열이 필요 없어집니다.

점화식을 세우는 순서

동적 계획법에서 어려운 부분은 구현이 아니라 점화식입니다. 순서를 고정해두면 접근이 쉬워집니다.

상태를 정합니다. dp[i]가 무엇을 뜻하는지 문장으로 씁니다. “i번째까지 봤을 때의 최댓값” 같은 형태입니다. 이 문장이 모호하면 뒤가 전부 어긋납니다.

전이(어떻게 변하는지)를 씁니다. dp[i]를 더 작은 상태로 어떻게 표현하는지 정합니다. 보통 마지막 선택이 무엇이었는지로 경우를 나눕니다.

초기값을 정합니다. 가장 작은 상태의 답을 직접 채웁니다.

순서를 확인합니다. dp[i]를 계산할 때 필요한 값들이 이미 채워져 있는지 봅니다.

계단 오르기를 예로 들면 상태는 “i번째 계단에 도달하는 방법의 수”입니다. 마지막에 한 칸을 올랐거나 두 칸을 올랐으므로 dp[i] = dp[i-1] + dp[i-2]입니다. 초기값은 dp[0] = 1, dp[1] = 1이고, 순서는 작은 인덱스부터입니다.

배낭 문제는 두 갈래로 나뉩니다

배낭 문제(knapsack problem) 는 무게 한도가 정해진 가방에 물건을 담아 가치를 최대로 만드는 문제입니다. 물건을 쪼갤 수 있느냐로 난이도가 갈립니다.

물건을 쪼갤 수 있으면 그리디로 풀립니다. 무게당 가치가 높은 것부터 담고 마지막에 남은 공간만큼 잘라 넣으면 됩니다.

쪼갤 수 없으면 그리디가 무너집니다. 무게당 가치가 가장 높은 물건을 담았더니 남은 공간에 아무것도 안 들어가는 경우가 생깁니다. 이때 동적 계획법이 필요합니다.

function knapsack(items, capacity) {
  // dp[w] = 무게 한도가 w일 때의 최대 가치
  const dp = new Array(capacity + 1).fill(0);

  for (const { weight, value } of items) {
    // 뒤에서부터 채워야 각 물건을 한 번만 쓴다
    for (let w = capacity; w >= weight; w--) {
      dp[w] = Math.max(dp[w], dp[w - weight] + value);
    }
  }
  return dp[capacity];
}

배낭 코드에서 눈여겨볼 부분은 안쪽 반복문이 역순이라는 점입니다. 순방향으로 돌면 방금 갱신한 dp[w - weight]를 다시 참조해서 같은 물건을 여러 번 담게 됩니다. 물건을 무제한으로 쓸 수 있는 변형에서는 반대로 순방향이 맞습니다. 반복 방향 하나가 문제의 종류를 바꿉니다.

한정된 자원에 무엇을 담을지 고르는 문제가 배낭 문제입니다. 예산 안에서 집행할 항목을 고르거나 한 번의 배포에 넣을 작업을 고를 때가 그렇습니다. 쪼갤 수 있는지부터 확인하면 그리디로 끝낼 수 있는지 표를 채워야 하는지 알 수 있습니다.

참고 자료

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
Kleinberg, J., & Tardos, É. (2005). Algorithm Design. Addison-Wesley.
Bellman, R. (1957). Dynamic Programming. Princeton University Press.

다음 편 예고

ep.04 - 가중치와 순서와 연결성

간선에 비용이 붙으면 너비 우선 탐색으로는 최단 거리를 얻을 수 없습니다. 가중치가 있을 때, 순서 제약이 있을 때, 연결 여부만 알면 될 때 각각 어떤 도구를 쓰는지 정리합니다.