C++로 찾는 최대 평균값 경로: 동적 계획법 완벽 풀이

문제 개요

이 문제에서는 2차원 행렬이 주어지며, 그중 최대 평균값을 가지는 경로를 찾아야 합니다. 경로의 시작점은 가장 왼쪽 위 셀이고, 도착점은 가장 오른쪽 아래 셀입니다. 예를 들어 다음과 같습니다.

입력 : Matrix = [1, 2, 3
                4, 5, 6
                7, 8, 9]
출력 : 5.8
최대 평균 경로 : 1 -> 4 -> 7 -> 8 -> 9
경로의 합은 29이고, 평균은 29/5 = 5.8

이 문제에서는 오른쪽 또는 아래 방향으로만 이동할 수 있습니다. 이 제약 조건 덕분에 문제가 훨씬 단순해집니다. 목적지에 도달하려면 오른쪽으로 N-1번, 아래로 N-1번 이동해야 하므로 모든 유효한 경로의 길이가 동일합니다. 이러한 관찰을 바탕으로 접근 방식을 설계할 수 있습니다.

문제 해결 접근 방식

핵심 아이디어는 간단합니다. 시작점에서 도착점까지의 경로 길이는 항상 (2×N − 1)로 고정된 분모가 됩니다. 따라서 평균을 최대화하려면 경로의 합을 최대화하면 되고, 이는 동적 계획법(Dynamic Programming)으로 효율적으로 계산할 수 있습니다.

예제 코드

위 접근 방식을 구현한 C++ 코드

#include <bits/stdc++.h>
using namespace std;
int maximumPathSum(int cost[][3], int n){ // 최대 평균을 반환하는 함수
    int dp[n+1][n+1];
    dp[0][0] = cost[0][0];
    for (int i = 1; i < n; i++) // dp 행렬의 첫 번째 열 초기화
        dp[i][0] = dp[i-1][0] + cost[i][0];
    for (int j = 1; j < n; j++) // dp 행렬의 첫 번째 행 초기화
        dp[0][j] = dp[0][j-1] + cost[0][j];
    for (int i = 1; i < n; i++) // 나머지 dp 행렬 채우기
        for (int j = 1; j <= n; j++)
            dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + cost[i][j];
    return dp[n-1][n-1]; // 최대 경로합을 이동 횟수로 나누어 평균 계산
}
int main(){
    int cost[3][3] = { {1, 2, 3}, {4, 5, 6},{7, 8, 9}};// 주어진 그리드
    int n = 3; // 행렬의 차수
    printf("%.1f", float(maximumPathSum(cost, n)) / float((2*n-1)));
    return 0;
}

실행 결과

5.8

코드 상세 설명

위 접근 방식에서 한 칸당 이동 횟수의 총합은 (2×N − 1)과 같습니다. 여기서 N은 비용 행렬의 차수입니다. 분모가 고정되어 있으므로 우리는 최대 경로합만 계산하면 됩니다. 이는 고전적인 동적 계획법(DP) 문제 중 하나로, 각 셀에서 가능한 최대 누적 합을 저장하는 dp 테이블을 만들어 해결합니다. 첫 번째 행과 열은 이전 값에 현재 값을 더해 초기화하고, 나머지 셀은 위쪽(dp[i-1][j])과 왼쪽(dp[i][j-1]) 값 중 큰 것에 현재 셀의 값을 더하여 채워 나갑니다. 마지막으로 dp[n-1][n-1]에 저장된 최대 경로합을 전체 이동 횟수인 (2×N − 1)로 나누어 결과를 출력합니다.

시간 복잡도

이 알고리즘은 행렬의 모든 셀을 한 번씩 방문하므로 시간 복잡도는 O(N²)이며, 추가 공간 역시 dp 테이블을 위해 O(N²)가 필요합니다.

결론

이 튜토리얼에서는 최대 평균값을 가지는 경로를 찾는 문제를 해결했습니다. 경로 길이가 고정되어 있다는 관찰을 활용해 문제를 '최대 경로합' 문제로 변환하고, 동적 계획법으로 효율적으로 해결하는 전체 과정을 살펴보았습니다. 동일한 로직은 C, Java, Python 등 다른 언어로도 손쉽게 작성할 수 있습니다. 이 튜토리얼이 여러분의 학습에 도움이 되기를 바랍니다.