동적 계획법

언제 쓰나

모든 경우를 따지면 개수가 너무 많은데, 큰 문제의 답이 조금 작은 문제의 답 몇 개로 정해질 때 씁니다.

• “최대”, “최소”, “경우의 수”를 묻습니다.
• 앞에서부터 하나씩 결정해 나가는 모양입니다. 집을 털지 말지, 계단을 한 칸 오를지 두 칸 오를지 같은 선택입니다.
• 지금의 결정이 바로 앞 몇 개의 결정에만 영향을 받습니다. 이 글의 대표 문제에서는 “바로 앞 집을 털었는가”만 중요합니다.

어떻게 동작하나

모든 경우를 따지면

LeetCode 198은 일렬로 선 집에서, 이웃한 두 집은 함께 털 수 없을 때 털 수 있는 최대 금액을 구하는 문제입니다. nums = [2, 7, 9, 3, 1]이면 집 0, 2, 4를 털어 2 + 9 + 1 = 12가 답입니다.

이웃하지 않게 집을 고르는 방법을 모두 세어 보면, 집이 1채일 때 2가지(털거나 안 털거나), 2채면 3가지, 3채면 5가지로 늘어나 10채면 144가지가 됩니다. 앞의 두 수를 더한 수가 다음 수가 되는 피보나치 수열과 같은 모양이라, 100채면 경우의 수가 21자리 수가 됩니다. 모든 조합을 하나씩 따지는 방식으로는 풀 수 없습니다.

테이블에 적어 두고 꺼내 쓴다

대신 질문을 작게 바꿉니다. **“집 i까지만 봤을 때 털 수 있는 최대 금액은 얼마인가”**를 dp[i]라고 하고, 집 0부터 차례로 칸에 적어 나갑니다. 이렇게 작은 문제의 답을 테이블에 적어 두고 큰 문제를 풀 때 꺼내 쓰는 방법을 동적 계획법(dynamic programming, DP)이라고 합니다.

집 i 앞에서 할 수 있는 선택은 둘뿐입니다. 아래 그림은 [2, 7, 9]에서 집 2를 볼 때입니다.

집 2 앞에서 고르는 두 후보 · nums = [2, 7, 9]

• 건너뛰기: 집 2를 털지 않으면, 집 1까지 봤을 때의 최댓값이 그대로 이어집니다. dp[1] = 7입니다.
• 털기: 집 2를 털면 바로 앞 집 1은 털 수 없으니, 집 0까지의 최댓값에 9를 더합니다. dp[0] + 9 = 2 + 9 = 11입니다.

둘 중 큰 11이 dp[2]가 됩니다. 식으로 쓰면 dp[i] = max(dp[i-1], dp[i-2] + nums[i])이고, 이렇게 칸 하나를 앞 칸들로 채우는 식을 점화식이라고 합니다. 앞 칸들은 이미 적어 둔 값이라 다시 계산하지 않고 꺼내 쓰면 됩니다. 칸이 n개이고 칸마다 비교를 한 번씩 하니, 경우의 수가 아무리 늘어도 계산은 n번입니다.

그림에서 테이블 맨 앞에 있는 0 두 칸은 첫 집보다 앞선 가상의 칸입니다. 이 칸이 있으면 집 0과 집 1도 “두 칸 앞”과 “바로 앞”을 똑같이 읽을 수 있어서, 첫 집을 따로 처리하는 코드가 필요 없습니다.

직접 따라가 보기

아래에서 “다음”을 누르면 집마다 두 단계씩, 후보 두 개를 보여 준 뒤 큰 쪽을 칸에 적습니다. 8~9번째 단계의 집 3에서는 건너뛰기(11)가 털기(10)보다 커서, 집 3을 털지 않는 쪽이 적힙니다. 마지막 단계에서는 끝 칸에서부터 털기를 고른 칸만 거슬러 올라가 실제로 턴 집을 찾습니다.

처음부터 이전 자동 재생 다음

단계 1 / 12

dp 테이블 · nums = [2, 7, 9, 3, 1]

변수

prev2

0두 칸 앞

prev1

0바로 앞 칸

cur

–

return

–

집마다 "여기까지 털 수 있는 최대 금액"을 dp 칸에 적어 나갑니다. 첫 집 앞에는 0 두 칸을 두고 시작합니다

• 지금 채우는 칸
• 두 후보가 읽는 칸
• 고른 후보 · 턴 집
• 아직 안 채운 칸

변수 칸의 prev2와 prev1은 아래 풀이 코드의 변수입니다. 칸을 채울 때 읽는 것이 늘 두 칸 앞과 바로 앞, 이 두 칸뿐이라 테이블 전체를 저장하지 않고 변수 두 개를 한 칸씩 밀면서 써도 됩니다.

대표 문제 풀이

점화식은 코치에게 들은 뒤, 제가 구현해 LeetCode 채점을 통과한 코드입니다.

function rob(nums) {
  if (nums.length === 0) {
    return 0;
  }
  if (nums.length === 1) {
    return nums[0];
  }

  let prev2 = 0;
  let prev1 = 0;
  for (let i = 0; i < nums.length; i++) {
    let cur = Math.max(prev2 + nums[i], prev1);
    prev2 = prev1;
    prev1 = cur;
  }
  return prev1;
}

prev2는 두 칸 앞 dp[i-2], prev1은 바로 앞 dp[i-1]입니다. 반복마다 cur에 이번 칸 값을 구한 뒤 두 변수를 한 칸씩 밀어, 반복이 끝나면 prev1에 마지막 칸 값이 남습니다. 두 변수를 0으로 시작하는 것이 위 그림의 가상 칸 0 두 개와 같습니다. 그래서 위쪽의 길이 0·1 검사는 없어도 결과가 같습니다(길이 1이면 반복 한 번으로 nums[0]이 나옵니다).

집마다 한 번씩 보므로 시간은 O(n)이고, 변수 몇 개만 쓰므로 공간은 O(1)입니다.

자주 하는 실수

모든 조합을 따질 때의 개수를 작게 봅니다. 저는 처음에 모든 경우를 대입하는 방법의 복잡도를 O(n²)으로 짐작했습니다. 직접 세어 보면 집이 하나 늘 때마다 경우의 수가 앞의 두 수의 합만큼 늘어, n²보다 훨씬 빠르게 커집니다.

두 후보 중 무엇을 고르는지 거꾸로 읽습니다. 집 3에서 건너뛰기 11과 털기 10을 계산해 놓고, “전자가 더 크면 지금 집을 포함”이라고 답한 적이 있습니다. 건너뛰기가 더 크다는 것은 이번 집을 털지 않는 쪽이 낫다는 뜻입니다. 위 시각화 9번째 단계가 이 장면입니다.

예시 하나에 맞춘 규칙을 세웁니다. 점화식을 찾다가 “i-1 최대 금액과 i-2 최대 금액이 같으면 …”처럼 [2, 7, 9, 3, 1]의 숫자에서 우연히 맞는 조건으로 규칙을 세운 적이 있습니다. 점화식은 특정 값이 아니라 “집 i 앞에서 할 수 있는 선택”에서 세워야 다른 입력에서도 맞습니다.