행렬에서 최대 경로 구하기

1. 문제

2. 문제 분석

행렬의 좌측상단에서 행렬의 원소( i, j )까지 도달하는 경로들의 점수 중 최고점을 구해보자.

 

원소( i, j )에 도달하기 직전에 방문할 수 있는 행렬의 원소는 2개이다.

즉, 원소( i-1, j ) 와 원소( i, j-1 ) 이다.

 

원소( i, j )는 무조건 방문되므로, 원소( i, j )의 값은 반드시 더해진다.

원소( i-1, j ) 거쳐서 원소( i, j )에 도달하는 경우와

원소( i , j-1 ) 거쳐서 원소( i, j )에 도달하는 경우 중에서 점수가 높은 쪽을 택하면 된다.

즉, (i-1,j)까지 도달하는 최고점수와 (i, j-1)까지 도달하는 최고 점수 중

큰 것에 원소(i,j)의 점수를 더하면 원소 (i,j)까지 도달하는 최고 점수가 된다.

 

위 점화식의 M은 둘 중에 높은 값을 선택하는 함수이다.

(1). i = j = 1이면 원소( 1, 1 )에 이르는 최고점수를 구하는 것으로, 원소( 1, 1 )만 방문한다.

      그래서, 원소( 1, 1 )의 값이 답이다.

 

(2). i = 1, j > 1이면 첫째 행의 한 원소에 이르는 최고점수를 구하는 것이다.

      첫째 행을 따라 오른쪽으로 수평 이동하는 방법밖에 없다.

       따라서, (1, j)의 바로 왼쪽 원소(1, j-1) 에 이르는 점수

       ( (1, j-1)에 이르는 유일한 점수이자 최고점수 ) 에 원소 (1,j)의 값을 더하면 된다.

 

(3). i > 1, j = 1이면 첫째 열의 한 원소에 이르는 최고점수를 구하는 것이다.

      첫째 열을 따라 아래로 수직 이동하는 방법밖에 없다.

      따라서, (i,1)의 바로 위쪽 원소(i-1,1)에 이르는 점수

      ( (i-1,1)에 이르는 유일한 점수이자 최고 점수) 에 원소 (i,1)의 값을 더하면 된다.

 

(4). 위의 3가지 경우가 아니면 원소( i , j )의 바로 왼쪽 원소에 이르는 최고 점수와

      원소( i , j )의 바로 위쪽 원소에 이르는 최고 점수중 큰 값에 원소( i , j )의 값을 더한 것이

      원소 (i,j)에 이르는 최고 점수이다.

 

3. 알고리즘 수도 코드

 

4. 구현

프로그램 실행결과

5. 소스 파일

main.c

0.00MB

 

6. 보완할 점

위의 방식에서는 중복 호출이 일어난다.

그러므로, 동적 프로그래밍의 좋은 대상임을 알 수 있다.

아래는 동적 프로그래밍의 알고리즘 수도 코드이다.

 

아래는 구현 부분.

프로그램 실행결과

 

소스 파일

main.c

0.00MB