다이나믹 프로그래밍 적용 문제 (3) 행렬 곱셈 순서 문제 설명 행렬 A1, A2, A3, . . . , An을 곱하는 수를 최소로 하는 최적의 곱셈 순서를 구하라. 예로, 행렬 A(2 × 3), B(3 × 5), C(5 × 2)가 있을 때 곱할 수 있는 경우의 수는 다음과 같다. (AB)C = 2 × 3 × 5 + 2 × 5 × 2 = 50 A(BC) = 3 × 5 × 2 + 2 × 3 × 2 = 42 두 경우의 수에서 최솟값인 42에 해당하는 연산이 최소의 곱셈 횟수 42와 최적의 곱셈 순서 A(BC) 가 된다. 마지막 행렬 곱셈이 수행되는 상황을 다음과 같이 정리할 수 있으며, 경우의 수는 총 n - 1이다. 점화식 Ak의 크기 : pk-1 * pk m[i, j] : 행렬 Ai, …, Aj의 곱을 ..

다이나믹 프로그래밍 적용 문제 (2) 조약돌 놓기 문제 설명 • 3×N 테이블의 각 칸에 양 또는 음의 정수가 기록되어 있다 • 조약돌을 놓는 방법 (제약조건) - 가로나 세로로 인접한 두 칸에 동시에 조약돌을 놓을 수 없다 - 각 열에는 적어도 하나 이상의 조약돌을 놓는다 • 목표: 돌이 놓인 자리에 있는 수의 합을 최대가 되도록 조약돌을 놓는다 5 2 -1 3 -1 8 -5 0 2 3 12 7 • 임의의 열을 채울 수 있는 패턴은 모두 4가지다. 패턴 위치 P1 ● P2 ● P3 ● P4 ● ● • 서로 양립할 수 있는 패턴은 다음과 같다. 패턴 양립 가능한 패턴 P1 P2 P3 P2 P1 P3 P4 P3 P1 P2 P4 P2 예로, 어떤 i열의 패턴이 P3라면 전 열에 올 수 있는 패턴은 P1과 P..

다이나믹 프로그래밍 적용 문제 (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)의 위치에 있는 값은 위치의 위쪽 혹은 왼쪽 ..

다이나믹 프로그래밍 (Dynamic Programming) 기본 개념 최적화 문제를 해결하는 알고리즘 기술이다. 전체 문제의 최적 해가 부분 문제의 최적 해를 포함함을 활용한다. 이전에 계산한 값을 저장함으로써 동일 계산의 반복을 제거한다. 재귀적 구조 - 큰 문제 안에 닮음꼴의 작은 문제가 들어있는 구조다. - 관계중심으로 문제를 간명하게 파악 가능하다. 재귀적 해법 - 잘 쓰면 보약, 잘못 쓰면 맹독이다. - 심각한 중복 호출이 일어나는 경우가 있다. > 재귀적 해법이 바람직한 예 - 퀵 정렬, 병합 정렬 등의 정렬 알고리즘 - 계승(factorial) 구하기 - 그래프의 DFS > 재귀적 해법이 치명적인 예 - 피보나치수 구하기 - 행렬곱셈 최적순서 구하기 대표 문제 : 피보나치 수 아주 간단한 문..