정수 삼각형 | 알고달레

프로그래머스의 정수 삼각형 문제를 함께 풀어보도록 하겠습니다.

문제

삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 3에서는 그 아래칸의 8 또는 1로만 이동이 가능합니다.

삼각형의 정보가 담긴 배열 triangle이 매개변수로 주어질 때, 거쳐간 숫자의 최댓값을 return 하도록 solution 함수를 완성하세요.

삼각형의 높이는 1 이상 500 이하입니다.
삼각형을 이루고 있는 숫자는 0 이상 9,999 이하의 정수입니다.

예제

입력: [[7], [3, 8], [8, 1, 0], [2, 7, 4, 4], [4, 5, 2, 6, 5]]
출력: 30

풀이 1

문제에서 주어진 예제의 입력을 삼각형으로 시각화해보면 다음과 같습니다.

    [7]
   [3, 8]
  [8, 1, 0]
 [2, 7, 4, 4]
[4, 5, 2, 6, 5]

이 문제는 재귀적으로 접근을 할 수 있는데요. 삼각형을 자세히 보시면 그 안에 수 많은 작은 삼각형이 들어 있습니다. 예를 들어서, 꼭대기가 7인 삼각형 안 에는, 꼭대기가 3인 삼각형과, 꼭대기가 8인 삼각형이 있고, 한 단계 더 들어가면 꼭대기가 3인 삼각형 안 에는, 꼭대기가 8인 삼각형과, 꼭대기가 1인 삼각형이 있습니다.

                [7]
               [3, 8]
              [8, 1, 0]
             [2, 7, 4, 4]
            [4, 5, 2, 6, 5]

       [3]                     [8]
      [8, 1]                  [1, 0]
     [2, 7, 4]               [7, 4, 4]
    [4, 5, 2, 6]            [5, 2, 6, 5]

  [8]          [1]
 [2, 7]       [7, 4]
[4, 5, 2]    [5, 2, 6]

꼭대기가 7인 삼각형에서 경로의 최대 합을 구하려면, 우리는 그 보다 작은 꼭대기가 3인 삼각형과 꼭대기가 8인 삼각형에서 경로의 최대합을 구해야합니다. 최대 합을 구해야하니 이 둘 중에서 더 큰 값을 선택해서 현재 꼭대기에 잇는 숫자와 더하면 그 꼭대기에서 경로의 최대 합을 구할 수 있을 것입니다. 일반화시켜 보면 다음과 같은 공식을 얻을 수 있겠네요.

꼭대기에서 경로의 최대 합 = 꼭대기에 있는 숫자 + MAX(
    왼쪽 대각선에 아래 삼각형에서 경로의 최대 합,
    오른쪽 대각선 아래 삼각형에서 경로의 최대 합
)

마찬가지로 꼭대기가 3인 삼각형 경로의 최대 합을 구하려면, 그 보다 작은 꼭대기가 8인 삼각형과 꼭대기가 1인 삼각형에서 경로의 최대합을 구해야합니다. 이런 식으로 계속 삼각형의 크기기를 줄이면서 내려가다보면, 바닥에 있는 숫자를 만나게 될 것입니다. 이 숫자들은 왼쪽 대각선과 오른쪽 대각선에 더 이상 더 작은 삼각형이 없으므로 그 숫자 자체가 경로의 최대 합이자 최소합이 됩니다. 바로 이 것이 재귀 알고리즘의 기저 조건이 될 것입니다.

지금까지 설명드린 알고리즘을 한번 파이썬으로 구현해볼까요?

def solution(triangle):
    def dfs(row, col):
        if row == len(triangle) - 1:
            return triangle[row][col]
        return triangle[row][col] + max(dfs(row + 1, col), dfs(row + 1, col + 1))

    return dfs(0, 0)

같은 코드를 자바스크립트로 구현하면 다음과 같습니다.

function solution(triangle) {
  function dfs(row, col) {
    if (row === triangle.length - 1) {
      return triangle[row][col];
    }
    return (
      triangle[row][col] + Math.max(dfs(row + 1, col), dfs(row + 1, col + 1))
    );
  }

  return dfs(0, 0);
}

참고로 예제에서 주어진 입력으로 이 함수를 호출하면 다음과 같은 형태로 호출 트리가 그려질 것입니다.

h을 삼각형의 높이라고 했을 때, 이 풀이의 시간 복잡도는 O(2^h)입니다. 재귀 함수가 한 번 호출될 때 마다 두 번의 연쇄 호출이 일어나기 때문입니다. 반면에 재귀 알고리즘의 호출 스택이 삼각형의 높이에 비례해서 깊어지기 때문에 O(h)이 되겠습니다.

풀이 2

재귀 알고리즘이 호출되는 모습을 자세히 관찰해 보시면 아래로 내려갈 수록 동일한 삼각형에 대해서 중복 호출이 폭발적으로 일어난다는 것을 볼 수 있는데요. 이렇게 불필요한 연산을 하지 않는다면 성능을 크게 개선할 수 있을 것 같습니다.

dfs(0, 0)
        dfs(1, 0)
                dfs(2, 0)
                        dfs(3, 0)
                                dfs(4, 0)
                                dfs(4, 1)
                        dfs(3, 1)
                                dfs(4, 1) 👉 중복
                                dfs(4, 2)
                dfs(2, 1)
                        dfs(3, 1) 👉 중복
                                dfs(4, 1) 👉 중복
                                dfs(4, 2) 👉 중복
                        dfs(3, 2)
                                dfs(4, 2) 👉 중복
                                dfs(4, 3)
        dfs(1, 1)
                dfs(2, 1) 👉 중복
                        dfs(3, 1) 👉 중복
                                dfs(4, 1) 👉 중복
                                dfs(4, 2) 👉 중복
                        dfs(3, 2) 👉 중복
                                dfs(4, 2) 👉 중복
                                dfs(4, 3) 👉 중복
                dfs(2, 2)
                        dfs(3, 2) 👉 중복
                                dfs(4, 2) 👉 중복
                                dfs(4, 3) 👉 중복
                        dfs(3, 3)
                                dfs(4, 3) 👉 중복
                                dfs(4, 4)

재귀 알고리즘에서 중복 연산을 제거할 때는 메모이제이션(Memoization) 기법이 많이 활용됩니다.

파이썬에서는 functools 모듈에서 제공하는 @cache 데코레이터를 사용하면 매우 쉽게 메모이제이션을 적용할 수 있습니다.

from functools import cache


def solution(triangle):
    @cache
    def dfs(row, col):
        if row == len(triangle) - 1:
            return triangle[row][col]
        return triangle[row][col] + max(dfs(row + 1, col), dfs(row + 1, col + 1))

    return dfs(0, 0)

그런데 아직까지 프로그래머스에서는 파이썬 3.8으로 답안 코드를 실행을 해주더라고요. @cache 데코레이터를 파이썬 3.9에서 추가된 기능이므로, 대안으로 @lru_cache 데코레이터를 사용해서 구현해보겠습니다. @lru_cache 데코레이터는 디폴트로 최대 128개의 호출 결과를 저장할 수 있습니다. 문제에서 삼각형의 높이가 최대 500이 될 수 있다고 했기 때문에 maxsize 옵션을 500 * 500 / 2 = 125000으로 설정해주었습니다.

from functools import lru_cache


def solution(triangle):
    @lru_cache(maxsize=125000)
    def dfs(row, col):
        if row == len(triangle) - 1:
            return triangle[row][col]
        return triangle[row][col] + max(dfs(row + 1, col), dfs(row + 1, col + 1))

    return dfs(0, 0)

자바스크립트에는 이러한 데코레이터가 없기 때문에 객체나 Map을 사용하여 직접 캐싱을 해줘야 합니다.

function solution(triangle) {
  const cache = new Map();

  function dfs(row, col) {
    if (row === triangle.length - 1) {
      return triangle[row][col];
    }
    const key = `${row}-${col}`;
    if (cache.has(key)) {
      return cache.get(key);
    }
    const result =
      triangle[row][col] + Math.max(dfs(row + 1, col), dfs(row + 1, col + 1));
    cache.set(key, result);
    return result;
  }

  return dfs(0, 0);
}

불필요한 재귀 함수의 호출이 없어지면 삼각형 내의 모든 숫자를 대상으로 딱 한 번만 재귀 함수를 호출하게 됩니다.

전체 호출 트리를 시각화해보면 다음과 같은 모습이 될 것입니다.

재귀 알고리즘에서 중복 연산을 제거하므로써 시간 복잡도를 O(1/2 * h^2) = O(h^2)로 대폭 향상시켰습니다. 호출 스택이 삼각형의 높이에 비례해서 깊어진다는 사실은 변함이 없으므로 공간 복잡도는 여전히 O(h)이 되겠습니다.

풀이 3

지금까지는 삼각형의 꼭대기부터 아래로 내려오면서 경로의 최대 합을 구했는데요. 이번에는 역발상을 해서 삼각형의 바닥부터 꼭대기로 거슬러 올라오면 어떨까요? ⬆︎

우선 우리는 삼각형의 맨 아래 줄에서 경로의 최대 합을 구하는 방법을 이미 알고 있습니다. 당연히 숫자가 하나 밖에 없으므로 그 숫자가 최소 합이자 최대 합이 되지요.

삼각형: [4, 5, 2, 6, 5]
최대합: [4, 5, 2, 6, 5]

그 윗 줄은 바로 아래 줄의 최대합을 알면 구할 수 있습니다. 바로 왼쪽 대각선의 최대 합과 오른쪽 대각선의 최대 합 중에서 큰 값에 그 자리의 숫자를 합치면 됩니다.

삼각형: [2, 7, 4, 4]

2 + MAX(4, 5) = 7
7 + MAX(5, 2) = 12
4 + MAX(2, 6) = 10
4 + MAX(6, 5) = 10

최대합: [7, 12, 10, 10]

그 윗에 있는 줄들도 마찬가지 방법으로 최대합을 구할 수 있습니다.

삼각형: [8, 1, 0]

8 + MAX(7, 12) = 20
1 + MAX(12, 10) = 13
0 + MAX(10, 10) = 10

최대합: [20, 13, 10]

삼각형: [3, 8]

3 + MAX(20, 13) = 23
8 + MAX(13, 10) = 21

최대합: [23, 21]

결국에는 삼각형의 꼭대기에 도착하겠지요?

삼각형: [7]

7 + MAX(23, 21) = 30

최대합: [30]

이와 같이 더 적은 입력에 대한 답을 먼저 구해서 저장해놓고, 더 큰 입력에 대한 답을 구할 때 활용하는 풀이 기법을 동적 계획법(dynamic programming)이라고 하는데요. 이 문제의 경우, 입력 삼각형과 동일한 크기의 2차원 배열에 최대 합을 저장할 수 있을 것 같습니다.

그럼 지금까지 설명드린 알고리즘을 파이썬으로 구현해보겠습니다. dp 배열의 모든 값을 0으로 초기화해놓고, 삼각형의 바닥부터 꼭대기까지 올라오면서 최대 합을 구합니다.

def solution(triangle):
    dp = [[0] * (r + 1) for r in range(len(triangle))]
    for r in range(len(triangle) - 1, -1, -1):
        for c in range(r + 1):
            dp[r][c] = triangle[r][c]
            if r < len(triangle) - 1:
                dp[r][c] += max(dp[r + 1][c], dp[r + 1][c + 1])
    return dp[0][0]

dp 배열에 입력 배열을 그대로 복사해놓고 시작하면, 현재 꼭대기에 있는 숫자를 굳이 더할 필요가 없어서 코드가 미세하게 더 간결해질 것입니다.

def solution(triangle):
    dp = [row[:] for row in triangle]
    for r in range(len(triangle) - 1, -1, -1):
        for c in range(r + 1):
            if r < len(triangle) - 1:
                dp[r][c] += max(dp[r + 1][c], dp[r + 1][c + 1])
    return dp[0][0]

같은 코드를 자바스크립트로도 한번 구현해보았습니다.

function solution(triangle) {
  const dp = triangle.map((row) => [...row]);

  for (let r = triangle.length - 1; r >= 0; r--) {
    for (let c = 0; c <= r; c++) {
      if (r < triangle.length - 1) {
        dp[r][c] += Math.max(dp[r + 1][c], dp[r + 1][c + 1]);
      }
    }
  }

  return dp[0][0];
}

이 풀이는 시간 복잡도는 삼각형 내의 숫자의 수와 비례하므로 O(1/2 * h^2) = O(h^2)이 됩니다. 공간 복잡도도 O(h^2)인데 dp 배열도 삼각형 내의 숫자의 수와 비례해서 커지기 때문입니다.