Logo

정수 삼각형

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

문제

삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾아보려고 합니다. 아래 칸으로 이동할 때는 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동 가능합니다. 예를 들어 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);
}

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

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)

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);
}

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

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

dfs(0, 0)
        dfs(1, 0)
                dfs(2, 0)
                        dfs(3, 0)
                                dfs(4, 0)
                                dfs(4, 1)
                        dfs(3, 1)
                                dfs(4, 2)
                dfs(2, 1)
                        dfs(3, 2)
                                dfs(4, 3)
        dfs(1, 1)
                dfs(2, 2)
                        dfs(3, 3)
                                dfs(4, 4)

재귀 알고리즘에서 중복 연산을 제거하므로써 시간 복잡도를 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 배열도 삼각형 내의 숫자의 수와 비례해서 커지기 때문입니다.