[Algorithm] 땅따먹기 알고리즘 / 동적 계획법

동적 계획법

---

동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 더 작은 하위 문제로 분할하고, 그 결과를 저장하면서 큰 문제를 해결하는 방법이다. 이를 통해 문제의 연산 시간을 효과적으로 줄일 수 있다. 동적 계획법을 적용하기 위해선 다음 두 가지 조건을 만족해야 한다. 피보나치 수열이 아래 두 조건을 만족하는 대표적인 예.

 

• 최적 하위 구조 Optimal Substructure
  작은 하위 문제의 최적 해를 조합하여 전체 문제의 최적 해를 얻을 수 있다.
• 하위 문제 중첩 Overlapping Subproblem
  동일한 하위 문제가 반복적으로 발생한다.

 

동적 계획법은 중복 계산 방지를 위해 메모이제이션 혹은 타뷸레이션 기법을 사용한다.

 

메모이제이션은 재귀 호출을 사용하여 필요한 문제만 계산하고, 타뷸레이션은 반복문을 사용하여 문제의 모든 가능한 해를 계산한다. 메모이제이션은 필요한 부분만 계산하므로 더 효율적일 수 있지만, 재귀 호출로 인해 스택 오버플로우 위험이 있다. 타뷸레이션은 모든 문제의 해를 계산하므로 더 많은 메모리를 사용하지만 재귀 호출의 제한 없이 안정적으로 동작한다.

 

동적 계획법은 크게 하향식, 상향식 접근 방법으로 나뉜다.

 

Top-Down (하향식)

주어진 문제를 더 작은 하위 문제로 분해하면서 문제 해결 — 메모이제이션 활용

 

하향식 동적 계획법으로 피보나치 수열을 계산하는 함수 ▼

function fibonacci(n, memo = [0, 1]) {
  if (memo[n] !== undefined) return memo[n];
  if (n <= 1) return n;

  memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
  return memo[n];
}

 

Bottom-Up (상향식)

작은 문제부터 순차적으로 해결하면서 주어진 문제 해결 — 타뷸레이션 활용

 

상향식 동적 계획법으로 피보나치 수열을 계산하는 함수 ▼

function fibonacci(n) {
  const table = [0, 1]; // 0~1번째 피보나치 수 미리 설정

  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 1] + table[i - 2];
  }

  return table[n];
}

 

땅따먹기 문제

---

그리디 (탐욕법)

프로그래머스 레벨 2의 땅따먹기 문제는 각 행(row)에서 선택할 수 있는 가장 큰 숫자의 합을 반환해야 한다. 단, 같은 열을 연속해서 선택할 수 없는 조건이 있다. 예를 들어 첫번째 행의 가장 큰 숫자인 5를 선택했다면, 다음 행에선 5와 동일한 열(인덱스 3)에 있는 8을 선택할 수 없다.

 

그리디(Greedy) 알고리즘은 현재 상황에서 지역적으로 최선의 선택을 하는 방법이다. 땅따먹기 문제를 그리디 방식으로 접근하면 각 행에서 최대값을 선택할 수 있지만, 아래와 같은 예시에선 최적의 해를 도출하지 못한다.

 

위 예시에선 첫 번째 행의 3, 두 번째 행의 2, 세 번째 행의 4를 선택해서 최적의 해(가장 큰 수 9)를 도출할 수 있다. 하지만 그리디 방식으로 각 행의 최댓값을 선택하면 합은 7이 된다(아래 참고). 두 번째 행의 가장 큰 수 3을 선택했기 때문에 세 번째 행에선 동일한 열에 있는 4를 선택할 수 없게 된 것이다.

 

따라서 이 문제를 그리디 알고리즘에 의존하면 최적의 해를 얻을 수 없다. 각 단계에선 최적의 선택을 했지만, 그 선택이 항상 전체 문제의 최적해를 보장하지 않기 때문이다. 그리디 알고리즘을 적용하려면 지역적으로 최적이면서 전역적으로도 최적인 문제여야 한다.

 

동적 프로그래밍

이 문제를 해결하려면 각 행에 있는 열(column)을 선택했을 때 얻을 수 있는 최댓값을 모두 계산해봐야 한다. 두 번째 행부터 시작하여 각 열이 얻을 수 있는 최댓값을 저장해 둔다면, 마지막 행에서 최적해를 찾아낼 수 있다.

 

예를 들어 두 번째 행의 첫 번째 열 2와, 첫 번째 행의 가장 큰 수 3을 더하면, 해당 열을 선택했을 때 얻을 수 있는 최댓값이 된다. 동일한 열을 연속해서 선택할 수 없으므로, 이전 행의 동일한 열은 계산에서 제외한다. 이런 식으로 두 번째 행의 모든 열에 대한 최댓값을 계산하고 저장한다.

 

 

마찬 가지로 세 번째 행 첫 번째 열의 최댓값은, 두 번째 행에 있는 가장 큰 수를 더해서 얻을 수 있다. 이 과정을 반복해서 모든 열의 계산을 완료하면, 마지막 행에 있는 가장 큰 수가 문제의 정답이 된다.

 

타뷸레이션을 사용한 동적 프로그래밍 ▼

function solution(land) {
  const row = land.length;
  const column = land[0].length;

  const dp = Array.from({ length: row }, () => Array(column).fill(0)); // 2차원 배열 초기화
  dp[0] = land[0].slice(); // 원본(land) 배열의 첫번째 행을 초기값으로 지정

  for (let i = 1; i < row; i++) {
    for (let j = 0; j < column; j++) {
      const prevRow = dp[i - 1].filter((_, index) => index !== j); // 동일한 열은 제외
      const prevRowMax = Math.max(...prevRow); // 현재 열을 제외한 이전 행의 최대값 계산
      dp[i][j] = prevRowMax + land[i][j]; // 현재 열을 선택했을 때 얻을 수 있는 최대 점수 저장
    }
  }

  return Math.max(...dp.at(-1)); // 마지막 행의 최대값 반환
}

 

이렇게 각 단계의 최적해(작은 하위 문제의 해답)를 이용해 전체 문제의 최적해(큰 문제의 해답)를 구하는 방법을 동적 프로그래밍이라고 부른다.