99클럽 코테 스터디 21일차 TIL + Java Algorithm

소개

• 알고리즘 스터디를 참여하며 작성하는 TIL입니다.
• TIL이란? 'Today I Learned'의 약자로, 한국어로 번역하면 '오늘 내가 배운 것'이란 의미입니다.
• 제가 오늘 하루 배운 것 혹은 경험하고 느낀 것들을 기록하고 회고하는 습관을 기르기 위한 글입니다.

 

문제 & 키워드

• 프로그래머스 - 정수 삼각형 (문제 링크)
• 동적 계획법 (Dynamic Programming)
• 최댓값 경로 찾기

 

---

 

문제 설명

주어진 삼각형 형태의 배열에서 꼭대기에서부터 바닥까지 내려가며 거쳐간 숫자의 합이 가장 큰 경로를 찾는 문제입니다. 이동할 때는 아래 칸으로 이동하며, 대각선 방향으로 한 칸 오른쪽 또는 왼쪽으로만 이동이 가능합니다.

제한사항

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

입출력 예

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

문제 설명

위의 삼각형에서 최댓값 경로를 예로 들면, 경로는 7 -> 3 -> 8 -> 7 -> 5를 선택하여 합이 30이 됩니다.

 

---

 

문제 접근

이 문제는 동적 계획법(DP)을 사용하여 해결할 수 있습니다. DP는 큰 문제를 작은 문제로 나누어 해결하며, 이전 단계의 최적 결과를 이용해 현재 단계의 최적 결과를 구하는 방식입니다.

1. 삼각형 초기화
   • 주어진 삼각형 배열을 이용해 각 위치에서 가능한 최댓값을 저장해 나갑니다.
2. 최댓값 계산
   • 첫 번째 행부터 시작하여 각 위치에서 선택 가능한 왼쪽 위 또는 오른쪽 위 값 중 더 큰 값을 선택하여 현재 위치의 값을 갱신합니다.
   • 갱신된 값은 그 위치까지의 최댓값이 됩니다.
3. 결과 반환
   • 마지막 행에서 가장 큰 값을 반환하여 전체 경로의 최댓값을 구합니다.

 

풀이 - 동적 계획법

class Solution {

    public int solution(int[][] triangle) {
        // 삼각형의 각 위치에서의 최댓값을 계산
        for (int i = 1; i < triangle.length; i++) {
            for (int j = 0; j < triangle[i].length; j++) {

                // 가장 왼쪽의 경우 위에서 내려올 수 있는 경로는 하나
                if (j == 0) {
                    triangle[i][j] += triangle[i - 1][j];
                // 가장 오른쪽의 경우도 위에서 내려올 수 있는 경로는 하나
                } else if(j ==  triangle[i].length - 1){
                    triangle[i][j] += triangle[i - 1][j - 1];
                // 그 외의 경우, 왼쪽 위와 오른쪽 위 중 큰 값을 선택
                }else {
                    int left = triangle[i - 1][j - 1];
                    int right = triangle[i - 1][j];
                    triangle[i][j] += Math.max(left, right);
                }
            }
        }

        // 마지막 행에서 가장 큰 값 찾기
        int answer = 0;
        int lastIndex = triangle.length - 1;
        for (int cost : triangle[lastIndex]) {
            answer = Math.max(answer, cost);
        }

        return answer;
    }
}

풀이 설명

1. 삼각형 초기화 및 갱신
   • 삼각형의 첫 번째 행을 제외한 각 행에 대해 왼쪽 위와 오른쪽 위에서 내려올 수 있는 경로 중 더 큰 값을 선택해 현재 위치의 값을 갱신합니다.
   • 가장 왼쪽의 값과 가장 오른쪽의 값은 각각 한 경로만 가능하므로, 해당 경로를 더해줍니다.
2. 최댓값 계산
   • 마지막 행에서 가장 큰 값을 선택하여 최종 경로의 최대 합을 구합니다.
3. 결과 반환
   • 마지막 행에서 가장 큰 값을 반환하여 문제에서 요구한 최댓값 경로의 합을 반환합니다.

 

---

 

마무리하며

• 이번 문제를 통해 동적 계획법(DP)의 기초적인 개념을 활용하여 문제를 해결하는 방법을 익혔습니다.
• 삼각형의 각 위치에서 가능한 최댓값을 계산하고 이를 누적하여 최종 결과를 도출하는 과정으로 문제를 해결했습니다.