[알고리즘] 11. Dynamic Programming (1)

1. Fibonacci Number

[Ver 1] 단순 재귀: 이 경우 n이 커질수록 중복 호출되는 경우가 많아져서 시간 복잡도가 지수적으로 증가한다.

[Ver 2] 메모이제이션: 계산 결과를 미리 저장해두고 계산한 적이 있다면 재귀 없이 리턴한다.

[Ver 3] DP: 재귀 없이 단순히 반복문으로 피보나치 수열을 구할 수 있다. (DP 배열에 이미 계산이 되어 있다고 확신)

int DP[1000];

int Fi(int n) {
	DP[0] = DP[1] = 1;
	for (int i=2; i<=n; i++)
		DP[i] = DP[i-1] + DP[i-2];
	return DP[n];
}

 

2. Select Working Days 

문제 정의: N일 동안 각 날짜마다 Pay가 주어진다. 연속으로 일을 할 수 없을 때, N일간 Total Pay를 최대화할 수 있는 방법을 구해보자.

Idea: $k\ (k \le n)$일까지 벌 수 있는 가장 큰 금액을 $k$일에 일을 했을 경우와 안 했을 경우로 나눠서 구하면 된다.

• $k$일에 일을 안한 경우: $max$($k-1$일애 일한 경우, $k-1$일에 일을 안한 경우)
• $k$일에 일을 한 경우: $k-1$일에 일을 안한 경우 + $k$일 Pay

int D[n+1][2]; // 0행은 마지막 날 일을 안한 경우 / 1행은 마지막 날 일을 한 경우
D[1][0] = 0; D[1][1] = a[1];

for (i=2; i<=n; i++){
	D[i][0] = max(D[i-1][0], D[i-1, 1]);
	D[i][1] = D[i-1][0] + a[i];
}

 

3. Matrix Multiplication

문제 정의: 행렬들을 곱하는 순서에 따라 걸리는 시간이 달라진다. 행렬 $M_1, M_2, ..., M_n$ 들을 곱한 결과를 구하는 데 걸리는 시간을 줄이는 것이 목표이고, 각 행렬들의 크기는 $M_k = d_{k-1} \times d_k$ 이다. 즉, 행렬 $M_i$번 부터 $M_j$번 까지 곱하는데 걸리는 비용을 $C_{ij}$ 라 하면, 목표는 $C_{1N}$을 구하는 것이다.

Idea: $j-i$의 값이 작은 것부터 C를 계산하면 된다. j-i가 1일 때는 비용이 0이다. j-i가 2일 때는 두 행렬의 곱이므로 $C_{i\ i+1} = d_{i-1}d_id_{i+1}$ 이다. j-i가 3 이상일 때는 행렬 그룹을 2개로 나눴을 때 가장 비용이 작은 그룹끼리 곱한 것을 택하면 된다. (각 행렬 그룹 내의 행렬들의 곱은 j-i가 더 작았을 때 구해놓은 상태)

int D[n + 1][n + 1]; // D[i][j] = C(i->j)

for (i = 1; i <= n; i++)
	D[i][i] = 0;
for (s=1; s<=n-1; s++)
	for (i = 1; i <= n - s; i++) {
		minval = INF;
		for (k = i; k <= i + s - 1; k++)
			minval = min(minval, D[i][k] + D[k + 1][i + s] + d[i - 1] * d[k] * d[i + s]);
		D[i][i + s] = minval;
	}

 

4. Maximum Subarray

문제 정의: 연속적인 Subarray 중 합이 최대가 되는 Subarray의 합을 구해보자. (아래 풀이에서 Step에서는 기본적으로 크기가 0인 배열 (공집합 배열)은 허용하지 않는다고 가정한다.)

Idea 1

인덱스 i번에서 끝나는 Maximum Subarray를 계산한다.

• Base: i = 0이면 첫번째 항이 답
• Step: i일 때 답이 $S[i]$ 라고 하자. $S[i+1] = max$($S[i] + A[i+1]$, $A[i+1]$)
• (단, 공집합 배열을 허용하면 $S[i+1] = max$($S[i] + A[i+1]$, $0$))

 

Idea 2

인덱스 i번 차례에서 자신을 포함하는 경우와 포함하지 않는 경우로 나눠서 계산한다. 즉, i번 칸을 포함하는 것 중 제일 큰 것과 i번 칸을 포함하지 않는 왼쪽 전체 중에서 제일 큰 것을 나눠서 구하면 된다.

• i일 때 답이 $S[i]$ 라고 하자.
• i+1일 때 자신을 포함하는 경우: $S[i+1] = max$($S[i] + A[i+1]$, $A[i+1]$)
• i+1일 때 자신을 포함하지 않는 경우: $S[i+1] = max$($S[i]$, i+1번을 포함하는 경우의 답)
• (단, 자신을 포함하지 않는 경우에서 공집합 배열을 허용하면 $S[i+1] = max$($S[i]$, 0))

 

Idea 3

Prefix Sum을 이용하여 풀 수 있다. 

• 부분합 $P_i$를 $A_i$까지 더한 합이라고 하자. 그럼 i번에서의 정답은 $max$($P_i - P_{i-1}$, $P_i - P_{i-2}$, ..., $P_i - P_{0}$) 이다. 즉, $min$($P_{i-1}, P_{i-2}, ..., P_0$)을 찾아서 빼면 된다.

 

5. Floyd-Warshall Alg.

문제 정의: 모든 노드의 쌍들마다 최단 경로를 구해보자. 쉬운 방법으로는 Dijkstra 알고리즘을 n번 돌리기가 있다.

Idea: 각 노드별로 번호를 부여했다고 가정하자. i->j로 가는 최단경로를 구할 건데, ${1, 2, ..., k}$번 노드 중에서만 거쳐가는 최단 경로를 찾으면 된다. 이 과정을 k: 0부터 N까지 반복한다. 즉, 구하고자 하는 것은 모든 (i, j) 쌍에 대하여 1번부터 n번 노드 중에서만 거쳐서 갈 수 있는 최단경로이다.

 

Computing: k일 때 노드 k를 쓰는 경우와 노드 k를 쓰지 않는 경우로 나눠서 더 짧은 경로를 구하면 된다.

• 노드 k를 쓰지 않는 경우: $D[k][i][j] = D[k-1][i][j]$
• 노드 k를 쓰는 경우: $D[k][i][j] = D[k-1][i][k] + D[k-1][k][j]$ - k 이전까지 경로 + k 이후의 경로로 연결

int D[n + 1][n + 1][n + 1];

for (i = 1; i <= n; i++)
	for (j = 1; j <= n; j++)
		D[0][i][j] = W[i][j];

for (k = 1; k <= n; k++)
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			D[k][i][j] = min(D[k - 1][i][j], D[k - 1][i][k] + D[k - 1][k][j]);

-------------------------------------------------------------------------------
// 2차원 배열로 성능 향상 - 가능한 이유: D[k][i][k] == D[k-1][i][k]

int D[n + 1][n + 1];

for (i = 1; i <= n; i++)
	for (j = 1; j <= n; j++)
		D[i][j] = W[i][j];

for (k = 1; k <= n; k++)
	for (i = 1; i <= n; i++)
		for (j = 1; j <= n; j++)
			D[i][j] = min(D[i][j], D[i][k] + D[k][j]);