행렬에서 최대 경로 구하기
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. 소스 파일
6. 보완할 점
위의 방식에서는 중복 호출이 일어난다.
그러므로, 동적 프로그래밍의 좋은 대상임을 알 수 있다.
아래는 동적 프로그래밍의 알고리즘 수도 코드이다.
아래는 구현 부분.
프로그램 실행결과
소스 파일