[Javascript][Programmers] 정수 삼각형

 

문제

삼각형의 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 가장 큰 경우를 찾는 문제입니다. 이 문제는 동적 프로그래밍(DP)으로 해결하기에 적합합니다. 그 이유는 다음과 같습니다:

1. 삼각형의 꼭대기에서 특정 위치까지의 최대 합은 이전 위치들의 최대 합에 기반합니다.
2. 여러 경로가 같은 위치를 지나갈 수 있어 중복 계산이 발생합니다.

 

풀이

처음에는 재귀를 활용한 Top-down 방식으로 접근했습니다. 

• 시간복잡도: O(N²) (N: 삼각형의 높이)

function solution(triangle) {
    const memo = {};
    
    function dp(i, j) {
        // 삼각형의 마지막 행에 도달한 경우
        if (i === triangle.length - 1) {
            return triangle[i][j];
        }
        
        // 메모이제이션 키 생성
        const key = `${i},${j}`;
        if (key in memo) {
            return memo[key];
        }
        
        // 왼쪽 자식과 오른쪽 자식 중 최대값 계산
        const leftPath = dp(i + 1, j);
        const rightPath = dp(i + 1, j + 1);
        
        memo[key] = Math.max(leftPath, rightPath) + triangle[i][j];
        return memo[key];
    }
    
    return dp(0, 0);
}

이 방식은 정확성 테스트는 통과했지만, 효율성 테스트를 통과하지 못했습니다. 재귀 함수를 사용하다보니 함수 호출 오버헤드가 발생해서 그런 것 같았습니다. 

 

효율성을 개선하기 위해 반복문만 사용하는 Bottom-up 방식으로 코드를 수정했습니다.

• 시간복잡도: O(N²) (N: 삼각형의 높이)

function solution(triangle) {
    const n = triangle.length;
    // 삼각형의 마지막 행으로 dp 배열 초기화
    let dp = [...triangle[n-1]];
    
    // 아래에서 위로 계산
    for (let i = n - 2; i >= 0; i--) {
        const newDp = [];
        for (let j = 0; j <= i; j++) {
            // 현재 위치에서 가능한 최대 합 계산
            newDp[j] = triangle[i][j] + Math.max(dp[j], dp[j+1]);
        }
        dp = newDp;
    }
    
    return dp[0];
}

해당 방식은 삼각형의 마지막 행부터 시작하여 위로 올라가면서 각 위치에서의 최대 경로 합을 계산합니다. 각 단계에서는 이전에 계산한 결과를 사용하여 현재 위치에서의 최대 합을 구합니다.

 

성능 분석

두 접근법 모두 시간 복잡도는 O(N²)입니다. 각 위치에서의 계산은 상수 시간이 소요되며, 삼각형에 있는 모든 위치를 한 번씩 방문합니다.

 

그러나 공간 복잡도 측면에서는 차이가 있습니다:

• Top-down: O(N²) - 모든 위치에 대한 메모이제이션 테이블 필요
• Bottom-up: O(N) - 한 번에 하나의 행에 대한 정보만 저장

이 문제에서는 삼각형의 높이가 최대 500이므로, 상향식 접근법이 메모리 사용량 측면에서 더 효율적입니다.