[프로그래머스][JAVA] 43105. 정수 삼각형

💡 문제
정수 삼각형 (https://school.programmers.co.kr/learn/courses/30/lessons/43105)
자세한 문제 설명과 입출력 예는 링크를 참고해주세요.

📝 선행 개념

• 최적 부분 구조 (Optimal Substructure):
  • 큰 문제를 작은 문제로 쪼갤 수 있고, 작은 문제의 최적해를 이용하여 큰 문제의 최적해를 구할 수 있는 구조입니다.
  • 동적 프로그래밍은 이러한 최적 부분 구조를 활용하여 문제를 해결합니다.
• 중복되는 부분 문제 (Overlapping Subproblems):
  • 동적 프로그래밍에서는 같은 문제를 반복해서 해결해야 할 때가 있습니다.
  • 이때 중복되는 계산을 피하기 위해 이미 계산한 값을 저장하고 재활용합니다.
  • 동적 프로그래밍의 효율성은 이 중복되는 부분 문제를 최소화하여 계산 효율을 높이는 데 있습니다.
• 메모이제이션 (Memoization):
  • 중복되는 계산을 피하기 위해 이미 계산한 값을 저장하고 재활용하는 기법입니다.
  • 주로 재귀적인 방법에서 활용됩니다. 이미 계산한 값을 캐시에 저장하여 나중에 필요할 때 사용합니다.
  • 동적 프로그래밍에서 중요한 개념 중 하나이며, 효율적인 동적 프로그래밍 구현에 필수적입니다.
• 탑다운 vs. 보텀업 (Top-down vs. Bottom-up):
  • 동적 프로그래밍은 일반적으로 두 가지 방식으로 구현됩니다.
  • 탑다운 방식은 재귀적으로 문제를 풀고, 메모이제이션을 통해 중복 계산을 피합니다.
  • 보텀업 방식은 작은 문제부터 시작하여 큰 문제까지 순차적으로 해결하며, 중복 계산을 피합니다.
• 상태 정의 및 전이 관계 (State Definition and Transition Relation):
  • 동적 프로그래밍에서는 문제를 해결하기 위해 상태를 정의하고 상태 간의 전이 관계를 이해해야 합니다.
  • 각 상태는 문제의 특정 부분을 나타내며, 상태 간의 전이는 작은 문제로부터 큰 문제로 해결하는 방법을 정의합니다.

---

🤓 문제 풀이

🔨 문제 설명

문제에 주어진 삼각형에서 위에서부터 아래로 내려오면서 각 위치마다 거쳐간 숫자의 최댓값을 구하는 문제입니다. 이 문제는 동적 계획법(Dynamic Programming)을 사용하여 해결할 수 있습니다.

 

---

🔨 접근 방법

• 각 위치마다 최대값을 저장할 2차원 배열을 만듭니다.
• 맨 위의 숫자는 그대로 최대값이 됩니다.
• 아래층으로 내려가면서 현재 위치까지의 최대값을 계산합니다.
• 각 위치마다 왼쪽 위에서 온 경우와 오른쪽 위에서 온 경우 중 더 큰 값을 현재 위치에 더합니다.
• 최하단까지 이 과정을 반복하면 맨 아래에는 최종적으로 거쳐간 숫자의 최댓값이 저장됩니다.

---

🔨 문제 풀이 과정

1. 먼저, 2차원 배열 dp를 생성하여 각 위치마다의 최댓값을 저장할 것입니다.
2. dp[0][0]에는 주어진 삼각형의 맨 꼭대기의 값을 넣어줍니다.
3. 이후 삼각형의 각 층에 대해, 왼쪽 끝과 오른쪽 끝의 경우를 별도로 처리해주고, 그 외의 경우에는 왼쪽 위에서 오는 경우와 오른쪽 위에서 오는 경우 중 더 큰 값을 현재 위치의 값에 더하여 dp 배열에 저장합니다.
4. 이렇게 맨 아래층까지 계산하고, 맨 아래층의 최댓값이 문제에서 요구하는 결과가 됩니다.

---

🔨 동적 프로그래밍(Dynamic Programming)으로 푸는 이유

이 문제를 동적 프로그래밍(Dynamic Programming)으로 푸는 이유는 중복 계산을 피하기 위해서입니다. 이 문제에서는 같은 위치로부터 시작하여 아래로 내려가면서 계산을 하게 됩니다. 이러한 계산은 이전 계산 결과에 의존하고, 같은 위치에 대해 여러 번 계산이 필요할 수 있습니다.

따라서 동적 프로그래밍을 사용하여 각 위치에서의 최댓값을 한 번만 계산하고 그 값을 저장하여 재활용함으로써 중복 계산을 피할 수 있습니다. 이를 통해 계산 속도를 획기적으로 향상시킬 수 있습니다.

이 문제를 다른 방법으로 푸는 것도 가능하지만, 일반적으로 동적 프로그래밍이 이러한 유형의 문제를 가장 효율적으로 해결할 수 있는 방법 중 하나입니다. 하지만 다음과 같은 방법으로도 문제를 해결할 수 있습니다.

1. 재귀적 접근: 문제를 재귀적으로 해결할 수 있습니다. 각 위치에서 다음 위치로 이동하면서 최대값을 구하는 방법입니다. 하지만 이 경우 중복 계산이 발생하고, 계산 효율이 떨어질 수 있습니다.
2. 그리디 알고리즘: 현재 위치에서 가장 큰 값을 선택하며 이동하는 방법도 가능합니다. 그러나 이러한 접근 방법은 최적해를 보장하지 않을 수 있습니다. 따라서 이 문제에서는 적합하지 않을 수 있습니다.

동적 프로그래밍은 이러한 문제를 효율적으로 해결할 수 있는 가장 일반적이고 강력한 방법 중 하나입니다. 따라서 이 문제를 풀 때 동적 프로그래밍을 사용하는 것이 바람직합니다.

• 2차원 배열 dp를 사용하여 각 위치의 최댓값을 저장하고, 이를 활용해 문제를 효율적으로 해결할 수 있습니다.
• 맨 아래층의 최댓값을 구하기 위해 dp[n-1]의 값을 순회하면서 최댓값을 찾습니다. 이 값이 문제에서 요구하는 결과입니다.

---

🔨 구현코드

class Solution {
    public int solution(int[][] triangle) {
        int n = triangle.length;
        int[][] dp = new int[n][n];
        
        // 맨 꼭대기 값 초기화
        dp[0][0] = triangle[0][0];
        
        // 삼각형의 각 층에 대해 최댓값 계산
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= i; j++) {
                // 왼쪽 끝 값인 경우
                if (j == 0) {
                    dp[i][j] = dp[i-1][j] + triangle[i][j];
                }
                // 오른쪽 끝 값인 경우
                else if (j == i) {
                    dp[i][j] = dp[i-1][j-1] + triangle[i][j];
                }
                // 그 외의 경우
                else {
                    dp[i][j] = Math.max(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
                }
            }
        }
        
        // 맨 아래층의 최댓값 반환
        int answer = 0;
        for (int num : dp[n-1]) {
            answer = Math.max(answer, num);
        }
        return answer;
    }
}

---

📚 풀이 보완

코드 설명

1. 2차원 배열 dp 초기화:
   • dp 배열은 각 위치에서의 최댓값을 저장하기 위한 배열입니다. dp[i][j]는 삼각형의 i번째 행에서 j번째 열까지의 최댓값을 나타냅니다.
   • 먼저, 맨 꼭대기의 숫자는 시작점이므로 그대로 dp[0][0]에 넣어줍니다.
2. 삼각형의 각 층에 대한 최댓값 계산:
   • 이중 반복문을 사용하여 삼각형의 각 층에 대해 최댓값을 계산합니다. 왜냐하면 각 위치마다 최댓값을 구해야 하기 때문에 층별로 계산해야 합니다.
   • 안쪽 반복문에서는 각 층의 해당 위치에 도달했을 때, 왼쪽 끝 값인지, 오른쪽 끝 값인지, 그 외의 경우인지를 판별하여 처리합니다.
3. 왼쪽 끝 값 및 오른쪽 끝 값 처리:
   • 왼쪽 끝 값인 경우, 현재 위치의 왼쪽 위에서 온 경우만 고려합니다. 따라서 dp[i][j] = dp[i-1][j] + triangle[i][j];와 같이 값을 갱신합니다.
   • 오른쪽 끝 값인 경우도 비슷하게 처리합니다.
   • 그 외의 경우에는 현재 위치의 왼쪽 위에서 온 경우와 오른쪽 위에서 온 경우 중 더 큰 값을 선택하여 현재 위치의 값에 더합니다. 이는 Math.max() 함수를 이용하여 간단히 처리할 수 있습니다.
4. 맨 아래층의 최댓값 찾기:
   • 모든 계산이 끝나고 나면, dp 배열의 가장 마지막 행에는 각 위치에서의 최댓값이 저장됩니다.
   • 따라서 이 행을 순회하면서 최댓값을 찾아 반환합니다.

---

📍 Plus+

시간복잡도 (알고리즘이 실행될 때 소요되는 시간의 양)

• 코드는 이중 반복문을 사용하여 각 층의 모든 위치에 대해 최댓값을 계산합니다.
• 외부 반복문은 각 층에 대한 반복을 수행하므로 총 O(n)번 반복됩니다. 내부 반복문은 현재 층의 위치에 따라 최대 O(n)번 반복됩니다.
• 따라서 총 시간 복잡도는 O(n2)입니다.

공간 복잡도 (메모리 공간의 양을)

• 이 코드는 삼각형의 각 위치에서 최댓값을 저장하기 위한 2차원 배열인 dp를 사용합니다.
• dp 배열의 크기는 삼각형의 높이에 비례하므로, n×n 크기의 배열이 필요합니다.
• 따라서 공간 복잡도는 O(n2)입니다.

이 코드의 시간 복잡도는 삼각형의 크기인 n에 대하여 이차 다항식으로 증가하며, 공간 복잡도도 n에 대하여 이차 다항식으로 증가합니다.

요약

 

---