다이나믹 프로그래밍 적용 문제 (4) 최장 공통 부분순서 LCS 문제 설명 부분순서와 공통 부분순서의 예시는 다음과 같다. 는 문자열 의 부분순서. 는 문자열 와 의 공통 부분순서. 최장 공통 부분순서(Longest Common Subsequence)란 공통 부분순서들 중 가장 긴 것을 말한다. 예를 들어, 다음 두 문자열의 LCS를 구하면 다음과 같다. h e r o i c a l l y s c h o l a r l y 결과 문자열 : holly, LCS : 5 주어지는 두 문자열의 LCS를 구하라. 점화식 LCS(i, j) : 문자열 X[i] = "x1,x2, … ,xi" 과 Y[j] = "y1,y2, … ,yj" 의 LCS 길이 LCS(i, j) = { 0 ( if i = 0 or j = 0 ) L..

다이나믹 프로그래밍 적용 문제 (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 > 재귀적 해법이 치명적인 예 - 피보나치수 구하기 - 행렬곱셈 최적순서 구하기 대표 문제 : 피보나치 수 아주 간단한 문..

플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm) 플로이드-워셜 알고리즘은 그래프에서 모든 정점 간의 최단 거리를 구하는 알고리즘입니다. 데이크스트라 알고리즘이 하나의 정점(시작 정점)으로부터 다른 모든 정점까지의 최단 경로를 구하는 알고리즘이었다면, 플로이드-워셜 알고리즘은 모든 정점에서 모든 정점으로부터 모든 정점까지의 최단 경로를 구하는 알고리즘이며 음의 경로가 존재하는 그래프에서도 사용할 수 있습니다. 또한 플로이드-워셜 알고리즘은 다이나믹 프로그래밍 기법이 적용될 수 있습니다. 알고리즘 원리 플로이드-워셜 알고리즘은 정점 A에서 정점 C에 대한 최단경로를 구하기 위해 `정점 A에서 정점 C에 대한 경로`와 `정점 A에서 정점 B를 거쳐 정점 B에서 정점 C로 가는 경로`를 ..