Today's Algorithm(2019-01-03)

programmers. 정수 삼각형

동적 계획법의 대표적인 문제였던 것 같습니다. 처음에 재귀적으로만 접근했다가 '시간 초과'를 경험하고 다른 코드들을 참고하다가 Memorization을 사용할 수 있다는 것을 다시 깨닫게 되었습니다. Memorization은 이전의 값을 기록해둠으로써 이후에 불필요한 계산을 줄일 수 있게 해줍니다. 그렇기 때문에 앞의 결과에 따라서 뒤에서 처리해주는 것이 동적으로 달라지죠. 그럼 앞서 재귀로 풀면서 시간초과했던 코드부터 보겠습니다.

class Solution {
    private int maxSum;

    public int solution(int[][] triangle) {
        search(triangle, 0, 0, 0);
        return maxSum;
    }

    public void search(int[][] triangle, int point, int height, int sum) {
        if (height == triangle.length) {
            maxSum = Math.max(maxSum, sum);
            return;
        }

        sum += triangle[height][point];

        search(triangle, point, height + 1, sum);
        search(triangle, point + 1, height + 1, sum);
    }
}

위와 같이 풀면 모든 경우를 모두 탐색하게 됩니다. 이는 오히려 모든 경우를 탐색해야만 하는 Brute Force에 가깝죠. 하지만 여기 문제에선 굳이 모든 경우를 탐색할 필요는 없습니다.

 

앞서 말씀드렸던 Memorization을 쓰는 것인데요. 각 줄에서 제일 앞과 뒤를 제외한다면 중간의 값들을 위의 값 후보 2개중 큰 값만 고르면 됩니다. 이렇게만 할 수 있다면 각각의 수에 대해 두 경우를 고려해야 하는 것에서 하나로 줄어들 것이고, 이것은 층이 더 늘어날수록 속도 차이는 확연하게 빨리질 수 있을 것입니다. 자세한 설명은 여기 블로그에 잘 설명되어있네요! 그럼 코드를 살펴볼게요.

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;

        for (int i = 1; i < triangle.length; i++) {
            int eachSize = triangle[i].length;
            for (int j = 0; j < eachSize; j++) {

                if(j == 0) {
                    triangle[i][j] += triangle[i - 1][j];  // 제일 앞의 인덱스
                } else if(j == eachSize - 1) {
                    triangle[i][j] += triangle[i - 1][j - 1];  // 제일 뒤의 인덱스
                } else {
                    triangle[i][j] += Math.max(triangle[i - 1][j - 1], triangle[i - 1][j]);  // 중간 인덱스
                }

                if(i == triangle.length - 1) answer = Math.max(answer, triangle[i][j]);  // 마지막 줄

            }
        }

        return answer;
    }
}

동적 계획법의 중요성을 다시금 깨닫게 하네요!!