[알고리즘] 다이나믹 프로그래밍 적용 문제 (1) 행렬 경로

다이나믹 프로그래밍 적용 문제 (1) 행렬 경로

 

문제 설명

양수 원소들로 구성된 n×n 행렬이 주어지고, 행렬의 좌상단에서 우하단까지 이동한다.

• 이동 방법 (제약조건)

- 오른쪽이나 아래쪽으로만 이동할 수 있다

- 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다

• 목표: 좌상단에서 우하단까지 이동하되, 방문한 칸에 있는 점수들의 최대합을 구한다.

 

점화식

maxSum[i, j] = 위치 (i, j) 에 이르는 최대합

m[i, j] = 위치 (i, j) 에 해당하는 원본 값

 

0    ( if  i = 0 or j=0 )

m[i, j] + max(maxSum[i - 1, j], maxSum[i, j - 1])    ( else )

 

최대합 = maxSum(n, n)

 

(i, j)의 위치에 있는 값은 위치의 위쪽 혹은 왼쪽 값 중 더 큰 값을 자신과 합한 값으로 정해진다. 각각의 값들은 각각의 해당 위치까지의 최대합이 기록되기 위해 과정을 반복한다.

재귀적 해법의 경우에는 반복되는 과정에서 같은 함수가 여러번 호출되고 다이나믹 프로그래밍의 경우에는 한번 계산된 결과는 필요시 재사용되므로 재호출이 일어나지 않는다.

 

행렬 경로 문제 : 재귀적 알고리즘 (효율성 측면에서 부적합)

maxSum(i, j) { 
	if (i = 0 or j = 0) then return 0; 
	else return (m[i, j] + (max(maxSum(i - 1, j), maxSum(i, j - 1)))); 
} 
print(maxSum(n, n))

 

행렬 경로 문제 : 다이나믹 프로그래밍

for i ← 0 to n 
	maxSum[i, 0] ← 0; 
for j ← 1 to n 
	maxSum[0, j] ← 0; 
    
for i ← 1 to n                      
	for j ← 1 to n                                        
		maxSum[i, j] ← m[i, j] + max(maxSum[i-1,  j], maxSum[i,  j-1]); 

print(maxSum[n, n]);
# Θ(n^2)

 

문제 예시1

m[i, j]

	0	1	2	3
0
1		1	1	1
2		5	1	6
3		1	1	1

maxSum[i, j]

 

	0	1	2	3
0	0	0	0	0
1	0	1	2	3
2	0	6	7	13
3	0	7	8	14

 

 

문제 예시2

m[i, j]

	0	1	2	3
0
1		1	2	3
2		1	4	2
3		2	1	1

maxSum[i, j]

 

	0	1	2	3
0	0	0	0	0
1	0	1	3	6
2	0	2	7	9
3	0	4	8	10

 

문제 예시3

m[i, j]

	0	1	2	3	4
0
1		6	7	12	5
2		5	3	11	18
3		7	17	3	3
4		8	10	14	9

maxSum[i, j]

	0	1	2	3	4
0	0	0	0	0	0
1	0	6	13	25	30
2	0	11	16	36	54
3	0	18	35	39	57
4	0	26	45	59	68