프로그래머스 동적계획법: 정수 삼각형 javascript

문제링크

https://school.programmers.co.kr/learn/courses/30/lessons/43105

함수설명

함수는 완전 이진 트리 자료구조를 나타내는 2차원 배열 triangle을 입력으로 받습니다.
각 성분배열은 트리의 한 레벨을 의미합니다.

루트 노드부터 출발하여 리프 노드로 가는 경로에서,
노드에 있는 값들을 모두 더하여 구할수있는 "경로 합"값중
최댓값을 반환해야 합니다.

정답 코드

const solution = (triangle) => {
    const depth = triangle.length;

    const memo = [...Array(depth)].map((x,i) => [...Array(i + 1)].fill(0));
    triangle[depth -1].forEach((value, index) => memo[depth -1][index] = value);

    for (let i = depth - 2; i >=0; i--) {
        for(let j = 0; j <= i; j++){
            memo[i][j] = triangle[i][j] + Math.max(memo[i + 1][j],
                                                   memo[i + 1][j + 1])
        }
    }

    const answer = memo[0][0]
   return answer
}

후기

처음에는 재귀함수, BFS로 문제를 해결하려고 시도했습니다.
논리적으로는 올바르게 작동했지만, 실행 시간 초과 문제로 인해 제출 할 수 없었습니다.

동적 계획법을 사용하여 트리를 거꾸로 거슬러 올라가는 방식으로 문제를 풀었습니다.

해설

1. 메모 리프노드의 값들은 입력받은 triagle의 리프노드와 일치시켜줍니다.
2. 이후 한단계 낮은레벨에서 메모 노드의 값은 triangle에서 해당노드의 위치 + 두 자식중 큰값으로 저장해주었습니다.
3. 루트노드에는 경로합 값의 최대값이 저장됩니다.

새로 알게된점: Array.prototype.fill(객체) 메서드를 사용시 ,array의 성분이 전부 같은 객체를 참조하게됩니다.
각각 다른 참조를 갖는 객체를 저장하려면 map(x=> new Set()) 을 이용해주어야합니다.

실패한 풀이

bfs

const solution= (triangle) =>{ 
    let answer = 0;
    const queue = [[0, 0, triangle[0][0]]];
    while (queue.length) {
        const [arrI, levelI, sum] = queue.shift();
        if (arrI + 1 < triangle.length) {
            queue.push([arrI + 1,
                        levelI,
                        sum + triangle[arrI + 1][levelI]]);
            queue.push([arrI + 1,
                        levelI + 1,
                        sum + triangle[arrI + 1][levelI + 1]]);

        } else {
            answer = Math.max(answer, sum)
        }

    }
    return answer
}

재귀함수

const solution = (triangle) => {
    let answer = 0
    const recursive = (arrI, levelI, sum) => {
        if (arrI === triangle.length - 1) {
            answer = Math.max(answer, sum);
            return
        }
       recursive(
           arrI + 1,
           levelI + 1,
           sum + triangle[arrI + 1][levelI + 1]
       )
        recursive(
            arrI + 1,
            levelI,
            sum + triangle[arrI + 1][levelI]
                 )
   }

recursive(0,0,triangle[0][0])
   return answer
}