[Programmers, Lv.2] 땅따먹기 (feat. 동적계획법, 자바스크립트)

🚀 동적계획법을 이용하여 자바스크립트 언어로 땅따먹기 문제를 해결해 봅시다!

문제 설명

땅따먹기 게임을 하려고 합니다. 땅따먹기 게임의 땅(land)은 총 N행 4열로 이루어져 있고, 모든 칸에는 점수가 쓰여 있습니다. 1행부터 땅을 밟으며 한 행씩 내려올 때, 각 행의 4칸 중 한 칸만 밟으면서 내려와야 합니다. 단, 땅따먹기 게임에는 한 행씩 내려올 때, 같은 열을 연속해서 밟을 수 없는 특수 규칙이 있습니다.

예를 들면,

| 1 | 2 | 3 | 5 |

| 5 | 6 | 7 | 8 |

| 4 | 3 | 2 | 1 |

로 땅이 주어졌다면, 1행에서 네번째 칸 (5)를 밟았으면, 2행의 네번째 칸 (8)은 밟을 수 없습니다.

마지막 행까지 모두 내려왔을 때, 얻을 수 있는 점수의 최대값을 return하는 solution 함수를 완성해 주세요. 위 예의 경우, 1행의 네번째 칸 (5), 2행의 세번째 칸 (7), 3행의 첫번째 칸 (4) 땅을 밟아 16점이 최고점이 되므로 16을 return 하면 됩니다.

제한사항

• 행의 개수 N : 100,000 이하의 자연수
• 열의 개수는 4개이고, 땅(land)은 2차원 배열로 주어집니다.
• 점수 : 100 이하의 자연수

입출력 예

land	answer
[[1,2,3,5],[5,6,7,8],[4,3,2,1]]	16

문제 풀이

이 문제는 동적계획법을 통해 풀이할 수 있습니다. (자바스크립트 외의 언어로 풀 경우 완전탐색으로도 풀이가 가능하지만, 자바스크립트로는 시간 한계로 인해 동적계획법만 가능한 것으로 알고 있습니다..😂 )

동적계획법이란?

동적 계획법에 대해 이미 아시는 분은 맨 마지막 문제 풀이 코드(자바스크립트)로 넘어가 주세요.

동적계획법(Dynamic Programming, aka DP)은 기본적인 아이디어로 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결하는 풀이 방식을 의미합니다. 즉 특정 알고리즘이라기 보다는 하나의 문제 해결 패러다임으로 볼 수 있습니다.

왜 동적계획법을 사용할까

동적계획법을 사용하는 이유로는 일반적인 재귀의 한계를 극복하기 위해서입니다. 특정 횟수로 반복된 재귀함수의 값을 구해야 할 때, 해당 재귀함수를 필요할 때 마다 반복하게 되면 엄청난 시간이 소요됩니다. 이미 한번 그 답을 구한 적이 있음에도 불구하고 말이죠.

이에 반해 한번 구한 특정 횟수의 재귀함수 값을 기억해뒀다가, 다음 재귀에서 이전에 구했던 재귀함수 값을 이용하는 방식을 이용하면 소요되는 시간을 획기적으로 줄일 수 있습니다. 이렇게 동적계획법은 큰 문제를 작은 문제로 쪼개어 정복해나가는 방식으로 문제를 풀이합니다.

대표적인 동적계획법 풀이

로는 피보나치 수열이 있습니다.

아래와 같이 f(n) = f(n-1) + f(n-2)가 반복되는 수열을 피보나치 수열이라고 합니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 ...

만약 100번째 피보나치 수열을 구하기 위해선 재귀를 몇번이나 반복해야 할까요? 매 피보나치 수를 구할 때 마다 재귀가 기하급수적으로 늘어나게 되며, 100번째에 달했을 때는 약 7해 ####경 ####조 ... 번 이상 함수가 호출된다고 합니다.

아마 컴퓨터도 죽겠죠..? 😂

이러한 상황에서 동적계획법을 이용하면 획기적으로 재귀 횟수를 줄일 수 있습니다. 100번째 수에 도달할 때 까지 그 직전의 피보나치 수를 기억하여, 기억된 전 피보나치 수를 이용하여 다음 피보나치 수를 구한다면, 0(n) 시간복잡도로 100번째 피보나치 수를 구할 수 있습니다.

2번째 피보나치 수 ⇒ 앞서 계산해 기억해놓은 0번째, 1번째 피보나치 수를 더한다.

3번째 피보나치 수 ⇒ 앞서 계산해 기억해놓은 1번째, 2번째 피보나치 수를 더한다.

4번째 피보나치 수 ⇒ 앞서 계산해 기억해놓은 2번째, 3번째 피보나치 수를 더한다.

…

100번째 피보나치 수 ⇒ 앞서 구해 저장해놓은 98번째, 99번째 피보나치 수를 더한다.

이렇게 약 7해…의 재귀 횟수를 98번으로 줄이는 것을 통해 동적계획법의 능력(?)을 확인할 수 있습니다.

문제 풀이 코드 (자바스크립트)

다시 문제로 돌아와서, 이번 땅따먹기 문제도 동적계획법을 이용해서 풀이할 수 있습니다.

이 문제에서 필요한 답은 오직 ‘최대의 값’입니다. 따라서 이전 땅에서 가능한 최대의 값을 미리 저장해두었다가, 다음 땅으로 이동할 때 미리 저장해둔 이전 땅의 최대의 값을 이용하여 다음 최대의 값을 구하는 방식을 이용하면 됩니다.

이전 땅의 값에 다음 최대 값을 더할 때는, 같은 인덱스의 땅은 밟을 수 없다는 규칙을 반영하여, 현재 인덱스 외의 나머지 땅의 값들 중 최대 값을 더해주면 됩니다.

위의 풀이를 자바스크립트 코드로 풀면 다음과 같습니다.

const solution = land => 
     Math.max(...land.reduce((a, c) => 
        [
            c[0] + Math.max(a[1], a[2], a[3]),  
            c[1] + Math.max(a[0], a[2], a[3]),
            c[2] + Math.max(a[0], a[1], a[3]),
            c[3] + Math.max(a[0], a[1], a[2]),
        ];
    , [0, 0, 0, 0]);

다만 위의 코드는 매 땅의 개수가 4개로 정해져 있다는 한계가 있습니다. 해당 한계를 극복해서, 땅의 개수에 유연하게 대응할 수 있는 코드로 리팩토링하면 아래 코드와 같습니다.

const solution = (land) =>
  Math.max(
    ...land.reduce(
      (a, c) =>
        c.map((v, i) => v + Math.max(...a.filter((_, aIdx) => i !== aIdx))),
      [0, 0, 0, 0]
    )
  );