[알고리즘] 3장. Dynamic Programming

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 3-1

* Dynamic Programming

- Multistage decision proccess

* Dynamic

- multistage, time-varying

* Programming

- 훈련과 병참지원을 위한 military schedule의 optimal program을 구하는 방법을 program이라고 했음.

* 동적계획
- divide-and-conquer 알고리즘은 하향식(top-down) 해결법
- dynamic programming은 상향식(bottom-up approach) 해결법
- 작은 문제 -> 큰 문제 순서로 해결한다.
- 인덱스를 조정해서 중복된 계산을 피한다.
- 작은 문제의 해를 모아서 다음 단계의 문제 해결에 사용한다.

* <A> 이항계수 계산 (분할정복법)
- 동일한 계산이 이뤄지는 경우가 많다.

- 문제 : 이항계수를 계산한다.
- 입력 : 음수가 아닌 정수 n과 k, 여기서 k <= n
- 출력 : bin, (n k)

int bin(int n, int k) {
	if (k == 0 || n == k)
		return 1;
	else
		return bin(n-1,k-1) + bin(n-1,k)
}

* <A> 이항계수 계산 (동적계획법)
- (1) 재귀 관계식 정립:
- 2차원 배열 B를 만들고, 각B[i][j]에는 iCj값을 저장하도록 한다.
- 그 값은 다음과 같은 관계씩으로 계산한다.
B[i][j] = B[i-1][j-1] + B[i-1][j]
- (2) nCk를 구하기 위해서는 다음과 같이 B[0][0]부터 시작해서 위에서 아래로 재귀 관계식을 적용하여 배열을 채워나가면 된다. 결국 값은 B[n][k]에 저장된다.

- 문제 : 이항계수를 계산한다.
- 입력 : 음수가 아닌 정수 n과 k, 여기서 k <= n
- 출력 : bin2, (n k)

int bin2(int n, int k) {
	index i, j;
	int B[0..n][0..k];
	for (i = 0; i <= n; i++)
		for (j = 0; j <= minimum(i,k); j++)
			if (j == 0 || j == 1)
				B[i][j] = 1;
			else
				B[i][j] = B[i-1][j-1] + B[i-1][j];
	return B[n][k];
}

---

📌 3-2

* 그래프 용어
- 정점 (vertex, node), 이음선 (edge, arc)
- 방향 그래프 (directed grapth / digraph)
- 가중치 (weight), 가중치 포함 그래프 (weighted graph)
- 경로 (path) : 각 정점에서 다음 정점을 잇는 이음선이 존재하는 일련의 정점들.
- 단순경로 (simple path) : 같은 정점을 두 번 지나지 않는 경로
- 순환 (cycle) : 한 정점에서 다시 그 정점을로 돌아오는 경로
- 순환 그래프 (cyclic graph) vs. 비순환 그래프 (acyclic graph)
- 길이 (length) : 경로상에 있는 가중치의 합(가중치포함그래프), 경로상의 이음선의 개수(가중치가 없는 그래프)

* 최단경로 문제 (all-pairs shortest paths problem)
- 보기 : 모든 도시에 대해, 한 도시에서 다른 도시로 갈 수 있는 가장 짧은 길을 찾는 문제
- 문제 : 가중치 포함, 방향성 그래프에서 최단경로 찾기
- 최적화문제 (optimization problem) : 주어진 문제에 대해 하나 이상의 많은 해답이 존재할 때, 이 가운데에서 가장 최적인 해답(optimal solution)을 찾아야 하는 문제

* 최단경로찾기
- 무작정 알고리즘 (brute-force algorithm) : 모든 경로를 찾은 후 가장 짧은 것을 고른다. 매우 비효율적인 방법이다.
- 동적계획식 설계전략 / 자료구조 :
- 그래프의 인접행렬(adjacency matrix)식 표현 : W, w[i][j] = 이음선의 가중치, 무한, 0
- 그래프에서 최단경로의 길이의 표현 : D[i][j] = 최단경로의 길이

* 최단경로찾기 동적계획식 설계절차
1. 재귀 관계식 : D(k)[i][j] = minimum{D(k-1)[i][j], D(k-1)[i][k]+D(k-1)[k][j];
2. 상향식으로 k=1부터 n까지 다음과 같이 이 과정을 반복하여 해를 구한다. D(0), D(1), ..., D(n)

* <A> Floyd의 알고리즘

- 문제 : 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 계산하라.
- 입력 : 가중치 포함, 방향성 그래프 W와 그 그래프에서의 정점의 수  n.
- 출력 : 최단거리의 길이가 포함된 배열 D

void Floyd(int n, const number W[][], number D[][]) {
	int i, j, k;
	D = W;
	for (k = 1; k <= n; k++)
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
				D[i][j] = minimum(D[i][j], D[i][k] + D[k][j]);
}

* <A> Floyd의 알고리즘 2

- 문제 : 가중치 포함 그래프의 각 정점에서 다른 모든 정점까지의 최단거리를 계산하라.
- 입력 : 가중치 포함, 방향성 그래프 W와 그 그래프에서의 정점의 수  n.
- 출력 : 최단거리의 길이가 포함된 배열 D, 그리고 다음을 만족하는 배열 P.

P[i][j] = vi에서 vj까지 가는 최단경로의 중간에 놓여있는 정점이 최소한 하나 있는 경우
-> 그 놓여있는 정점 중에서 가장 큰 인덱스
P[i][j] = 최단경로의 중간에 놓여있는 정점이 없는 경우 -> 0

void Floyd2(int n, const number W[][], number D[][]) {
	int i, j, k;
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			P[i][j] = 0;
	D = W;
	for (k = 1; k <= n; k++)
		for (i = 1; i <= n; i++)
			for (j = 1; j <= n; j++)
				if (D[i][k] + D[k][j] < D[i][j]) {
					P[i][j] = k;
					D[i][j] = D[i][k] + D[k][j];
				}
}

* <A> Floyd2 정점 출력

void path(index q, r) {
	if (P[q][r] != 0) {
		path(q, P[q][r]);
		cout << " v" << P[q][r];
		path(P[q][r], r);
	}
}

---

📌 3-3

* 동적계획법에 의한 설계 절차
(1) 문제의 입력에 대해서 최적(optimal)의 해답을 주는 재귀 관계식(recursive property)을 설정
(2) 상향적으로 최적의 해답을 계산
(3) 상향적으로 최적의 해답을 구축

* 최적의 원칙
- 어떤 문제 사례에 대한 최적 해가 그 사례를 분할한 부분사례에 대한 최적 해를 항상 포함하고 있으면, 그 문제는 최적의 원칙(the principle of optimality)이 적용된다라고 한다.
- 최적의 원칙이 적용되어야지만 동적계획법을 사용할 수 있다.
- 최적의 원칙이 적용되지 않는 예 : 최장경로 문제

* 연쇄 행렬곱셈 (matrix-chain multiplication)
- 행렬의 곱셈 순서에 따라 총 필요한 곱셈의 횟수가 달라진다.
- 무작정 알고리즘의 시간 복잡도 2^(n-2) => Θ(2^n)

* 연쇄 행렬 곱셈 무작정 알고리즘
- 무작정 알고리즘의 모든 가능한 가지 수 P(n)
- P(n) = C(n-1) = Cn = 1/n+1 (2n n) : nth Catalan number
- C(n)은 n개의 노드를 갖고 있는 이진트리의 모양의 경우의 수와 같다.
- 2개의 matrix를 곱하는 경우의 수 - AA -1가지

* 연쇄 행렬 곱셈 동적계획식 설계전략
- Ak의 크기는 dk-1 x dk : dk-1 : 행, dk : 열
- A1의 행의 수는 d0.
- M[i][j] = i <= j일 때, Ai부터 Aj까지의 행렬을 곱하는데 필요한 기본적인 곱셈의 최소 횟수 = minimum(M[i][k] + M[k+1][j] + di-1dkdj)

* <A> 행렬 최소곱셈횟수 (동적계획법)

- 문제 : n개의 행렬을 곱하는데 필요한 기본적인 곱셈의 횟수의 최소치를 결정하고,
그 최소치를 구하는 순서를 결정하라.
- 입력 : 행렬의 개수 n, 배열 d[i-1] x d[i]는 i번째 행렬의 규모를 나타낸다.
- 출력 : 기본적인 곱셈의 횟수의 최소치를 나타내는 minmult.
최적의 순서를 구할 수 있는 배열 P, P는 1...n-1 by 1..n.
여기서 P[i][j]는 행렬 i부터 j까지가 최적의 순서로 갈라지는 기점을 나타낸다.

in minmult(int n, const int d[], index P[][]) {
	index i, j, k, diagonal;
	int M[1..n][1..n];
	for (i = 1; i <= n; i++)
		M[i][j] = 0;
	for (diagonal = 1; diagonal <= n - 1; diagonal++)
		for (i = 1; i <= n - diagonal; i++) {
			j = i + diagonal;
			M[i][j] = minimum(M[i][k] + M[k+1][j] + d[i-1]*d[k]*d[j]);
			P[i][j] = 최소치를 주는 k의 값
		}
	return M[1][n];
}

* <A> 최적의 해를 주는 순서의 출력

- 문제 : n개의 행렬을 곱하는 최적의 순서를 출력하시오.
- 입력 : n과 P
- 출력 : 최적의 순서

void order(index i, index j) {
	if (i == j)
		cout << "A" << i;
	else {
		k = P[i][j];
		cout << "(";
		order(i, k);
		order(k+1, j);
		cout << ")";
	}
}

---

📌 3-4

* 최적 이진검색 트리
- left(right) subtree : 이진트리에서 어떤 마디의 왼쪽(오른쪽)자식마디가 뿌리마디가 되는 부분트리
- 이진검색트리(binary search tree) : 순서가능집합(ordered set)에 속한 아이템(키)으로 구성된 이진 트리
- 각 마디는 하나의 키만 가지고 있다.
- 주어진 마디의 왼쪽(오른쪽) 부분트리에 있는 키는 그 마디의 키보다 작거나(크거나) 같다.

* Optimal binary search tree

- 키를 찾는데 걸리는 평균시간이 최소가 되도록 구축된 트리

* Optimal binary search tree problem

- 각 키를 찾을 확률이 주어져 있을 때(모두 같지는 않음을 가정) 키를 찾는데 걸리는 평균시간이 최소가 되도록 이진트리를 구축하는 문제

* <C> 이진검색트리의 검색
- notation :
Key1, Key2, ..., Keyn : n개의 키
pi : Keyi가 검색키일 확률
ci : 주어진 트리에서 키 Keyi를 찾는데 필요한 비교횟수
평균 검색 시간 : sigma cipi
- n개의 키가 있는 경우 이진검색트리의 개수
Cn = 1/n+1(2n n) : nth Catalan number
- 모든 경우의 이진검색트리를 구축하여 이 중 최적을 선택하는 방법은 비현실적 -> 동적계획법을 이용한 효과적인 방법 필요

void search (node_pointer tree, keytype keyin, node_pointer& p) {
	bool found;
	p = tree;
	found = false;
	while (!found)
		if (p->key == keyin)
			found = true;
		else if (keyin < p->key)
			p = p->left;
		else
			p = p->right;
}

- 키의 검색 시간 : depth(key) + 1

- 노드 타입
struct nodetype {
	keytype key;
	nodetype* left;
	nodetype* right;
};
typedef nodetype* node_pointer;

* 이진검색트리 평균검색시간
A[1][n] = min(A[1][k-1] + A[k+1][n]) + sigma(p)

* <A> 최적이진검색트리 구하기

void optsearchtree(int n, const float p[], float& minavg, index R[][]) {
	index i, j, k, diagonal;
	float A[1..n+1][0..n];
	for (i = 1; i <= n; i++) {
		A[i][i-1] = 0; A[i][i] = p[i];
		R[i][i] = i; R[i][i-1] = 0;
	}
	A[n+1][n] = 0;
	R[n+1][n] = 0;
	for (diagonal = 1; diagonal <= n-1; diagonal++) {
		for (i = 1; i <= n - diagonal; i++) {
			j = i + diagonal;
			A[i][j] = min(A[i][k-1] + A[k+1][j]) + sigma(p);
			R[i][j] = 최소값을 주는 k의 값
		}
	}
	minavg = A[1][n];
}

* <A> 최적이진검색트리 구축

node_pointer tree(index i, index j) {
	index k;
	node_pointer p;
	k = R[i][j];
	if (k == 0)
		return NULL;
	else {
		p = new nodetype;
		p->key = Key[k];
		p->left = tree(i, k-1);
		p->right = tree(k+1, j);
		return p;
	}
}

---

📌 3-5

* DNA 서열 맞춤
- 분자유전학(molecular genetics)의 한 분야인 동족(homologous) DNA 서열 맞춤문제를 동적계획법으로 해결하는 방법 소개
- DNA : 이중 나선구조를 이루는 뼈대와 핵염기로 구성. A-T, C-G
- 돌연변이 : 교환, 삽입, 제거
- 손해 정의 : 틈 비용, 불일치 비용

* <A> 분할정복방법의 DNA 서열 맞춤 방법

- 문제 : 두 개의 동족 DNA 서열의 최적 맞춤을 구하시오
- 입력 : 길이 m인 DNA 서열 x와 길이 n인 DNA 서열 y, 서열은 배열로 표현
- 출력 : 두 서열의 최적 맞춤의 비용

int opt(int i, int j) {
	if (i == m)
		opt_val = 2(n-j);
	else if (j == n)
		opt_val = 2(m-i);
	else {
		if (x[i] == y[j])
			penalty = 0;
		else
			penalty = 1;
		opt_val = min(opt(i+1, j+1) + penalty,
				opt(i+1, j) + 2,
				opt(i, j+1) + 2)
	}
	return opt_val;
}

* <A> 동적계획법의 DNA 서열 맞춤 방법

1. M + 1, N + 1 크기의 2차원 배열. 마지막 행, 마지막 열에 '-' 틈 문자 추가

2. 틈 행과 틈 열을 채워 넣는다.

3. 우측 아래부터 대각원소들을 채워 넣는다.

4. opt(0,0)에서 출발해서 3가지 가능성을 조사 - opt(i,j)=min(opt(i+1,j+1)+penalty, opt(i+1,j)+2, opt(i,j+1)+2)

5. 경로를 찾은 후 맞춤된 서열 구성

5-a. 최적배열의 오른쪽 맨 아래 구성에서 시작하여 표시해둔 경로를 따라간다.
5-b. 배열의 [i][j]칸에 도달하기 위해서 대각선으로 이동할 때 마다, i째 행에 해당하는 문자를 x서열에 넣고, j째 열에 해당하는 문자를 y서열에 넣는다.
5-c. 배열의 [i][j]칸에 도달하기 위해서 위로 이동할 때 마다, i째 행에 해당하는 문자를 x서열에 넣고, 틈 문자를 y서열에 넣는다.
5-d. 배열의 [i][j]칸에 도달하기 위해서 왼쪽으로 이동할 때 마다, j째 열에 해당하는 문자를 y서열에 넣고, 틈 문자를 x서열에 넣는다.

---