Dynamic Programming (1)

쉬운 문제로 시작해보자.

Fibonacci Number

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

• Recursion
• Memoisation
• Dynamic Programming

전체 입력을 잘라 부분만 재귀로 호출하는 방법으로, 부분 문제에 대해서 전체인 것처럼 생각해 독립적으로 문제를 풀 수 있는 문제에 대해 적용한다. 그러나 그래프같은 경우는 절반만 본다고 해서 답을 찾을 수 있는게 아니기 떄문에 재귀를 잘 사용하지 않는다.

예를 들어 merge sort는 배열을 잘라 왼쪽만 sorting할 수 있다. 왼쪽을 sorting할 때 오른쪽 배열의 값에 영향을 받지 않기 떄문이다. 반면 그래프는 다 엮어있기 때문에 그럴 수가 없다.

독립적인 부분문제의 답을 가지고 전체의 답을 만든다는 점에서는 divide and conquer와 비슷하다. 그러나 핵심적인 파트는 다름. DP는 “재사용”을 함. 성능 개선 포인트가 다르다.

By Recursion

int Fibonacci(int n) {
    if(n < 2) return 1;
    return Fibonacci(n-1) + Fibonacci(n-2);
}

정의 그대로 코드로 옮긴 것이니까 맞는 답이지만, 문제는 느리다는 것이다.

F(7)을 계산해보자.

F(7) 
= F(6) + F(5)
= (F(5) + F(4)) + (F(4) + F(3))
= ((F(4) + F(3)) + (F(3) + F(2))) + ((F(3) + F(2)) + (F(2) + F(1)))
= ... = 1 + 1 + ... + 1

걸리는 시간은 1의 개수, 즉 F(7)에 비례한다. 그럼 F(n)이 대략 얼마쯤인지 구해보자.
E(n) = E(n-2) + E(n-2), G(n) = G(n-1) + G(n-1)이라 정의하면 E(n) <= F(n) <= G(n)가 성립한다. 이때 E(n) ≈ 2^(n/2), G(n) ≈ 2^n이므로 F(n)도 지수함수처럼 매우 빠르게 증가함을 알 수 있다. 그래서 n이 조금만 커져도 시간이 엄청나게 오래 걸린다.

위에서 F(7)을 계산한 과정을 보면, 같은 값이 불필요하게 여러 번 계산되는 현상을 발견할 수 있다. 예를 들어, F(6) + F(5)에서의 F(5)와 (F(5) + F(4)) + (F(4) + F(3))의 F(5)는 같은 값이다. 이미 계산한 값을 또 계산할 필요는 없지 않는가?

어딘가에 적어두고 체크하면 안될까?

By Memoisation

int FF[1000]; // 피보나치 값들을 적어둘 배열

void init () {
    FF[0] = FF[1] = 1;
    for(int i = 2; i < 1000; i++) FF[i] = -1;
}

int Fibonacci(int n) {
    if(FF[n] != -1) return FF[n];
    
    FF[n] = FF[n-1] + FF[n-2];
    return FF[n];
}

F(7)을 구해보자. FF[2]부터 FF(7)까지 -1이므로 계속 FF[n-1] + FF[n-2]를 부르다가 F(2)를 계산할 때 최초로 FF[1] = 1, FF[0] = 1이므로 F(2) = 2가 되고 이를 FF[2]에 기록한다.

그리고 F(3)을 계산하는데 FF[1]의 값은 기록해 두었으므로 FF[2]와 FF[1]은 이미 기록해 두었으므로 더하기만 하면 된다.

이러한 방식으로 F(7)을 계산하면 재귀에서 동일한 호출을 1번만 하므로시간을 획기적으로 줄일 수 있다.

시간은 얼마나 걸릴까?

모든 값들은 한 기록되고 두 번 사용된다. 실제 값들에서 dependency를 보면,

FF[5]는 FF[6]과 FF[7]을 계산할 때 총 두 번 읽어진다. 따라서 **O(N)**의 시간이 걸린다.

Memoisation는 DP와 개념이 거의 비슷하지만, 재귀를 호출하기 때문에 DP보다는 느릴 수 있다(O notation상으로는 같음).

주로 memo하는 배열이 어떤 순서로 채워질 지 모를 때 memoisation을 사용한다. 다르게 말하자면 배열이 채워지는 순서를 알면 재귀를 부르지 않아도 되기 때문에 더 빠르게 답을 구할 수 있다는 것이다.

Dynamic Programming

int FF[1000];

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

피보나치 정의를 그대로 쓴 것 같아 보이지만 여기서의 핵심은 FF[i] = FF[i-1] + FF[i-2];에서 FF[i-1]과 FF[i-2]가 계산된 값이고 믿는 것이다. 왜냐하면 2부터 쭈르륵 봐왔기 때문에.

Select Working Days

• Given pay for each of N days
• Select days to work to maximise total pay
• One rule: you cannot work on consecutive days

| 3 | 5 | 6 | 4 | 8 | 7 | 6 | 10 | |—|—|—|—|—|—|—|—-|

가능한 경우의 수가 너무 많기 때문에 다 시도해 볼 수 없다.

여기서 DP의 전형적인 틀을 볼 것이다.

전체의 가장 좋은 답이 분명 있을 것이다.

뜬금없지만 마지막 날에 일을 할까 안할까?를 생각해보자. 마지막 날에 일을 할 수도, 안 할 수도 있다(아직 모름).

마지막 날에 일을 할 경우 가장 좋은 답과, 마지막 날에 일을 하지 않을 경우 가장 좋은 답을 알고 있다고 가정하자.

그럼 마지막 날에 일을 할 경우와 안하는 경우 중 더 좋은 답이 정답이다.

그럼 이제 마지막 날에 일을 하지 않는 경우를 살펴보자. 위에서와 동일하게 전전날에 일을 할 수도, 안 할 수도 있다.

마지막 날에 일을 하는 경우에는 연속해서 일할 수 없으므로 전전날에 일을 할 수 없다.

마지막 날과 전전날은 앞의 6개 날에 대해 영향을 끼치지 않으므로 6개 날에서 좋은 답을 구하면 전체 정답을 구할 수 있다.

독립적이라는 것을 알았으니 재귀를 사용해 풀 수 있다. 그러나 같은 값이 여러 번 사용되고 앞쪽부터 계산되는 것을 알기에 DP를 사용하면 더 빠르게 답을 구할 수 있다는 것을 알 수 있다.

DP Solution

int W(int a[], int n) {
	// D[i][0]: i번째 날에 일을 하지 않을 때 가장 좋은 답
	// D[i][1]: i번째 날에 일을 할 때 가장 좋은 답
	int D[n+1][2]; 
	
	D[1][0] = 0; 
	D[1][1] = a[1];
	
	for(int 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];
	}
	return max(D[n][0], D[n][1]);
}

A Familiar One: Path Counting

집에서부터 학교까지 가는 최단거리를 계산해보자.

고등학교 확통 시간에 배운 공식을 사용하면 13!/(8! * 5!)로 쉽게 구할 수 있다.

이번에는 집에서 학교까지 가는데 연못이 있다고 해보자. 이럴 때는 문제를 나눠서 보면 된다.

이때 점 1, 2, 3, 4를 지나는 길은 서로 겹칠 수 없다. 그런데 5번을 지날 경우에는 무조건 6번 점을 거치게 되어있다.

이렇게 풀 수 있지만 이건 사람이 푸는 방식이고, 컴퓨터는 이런 방식으로 잘 못 푼다. 대신 계산량은 많지만 쉬운 알고리즘을 짜보자.

길 찾기는 문제는 중요한 문제이다. 실제로 소셜 미디어에서 mutual friend 찾을 때도 이러한 방식을 사용한다.

DP

모든 위치에 대해서 집으로부터 거기까지 오는 길의 개수를 적는다. 확통 문제 풀 때 11111 방식.

입력으로 주어진 자리마다 그대로 계산하니까 굉장히 이해하기 쉬운 알고리즘이다. 다음에 볼 matrix multiplication은 칸마다 보는게 아니라 좀 헷갈린다..

Matrix Multiplication

• Multiply a sequence of N matrices M1*M2*...*MN
• Size of Mi is d(i-1) by d(i)

위의 counting path와는 다르게 모든 input마다 값을 계산하는게 아니다. 대신 matrix의 범위에 대해 계산을 한다. 값들을 어떤 순서로 계산하기를 위해 알기 위해서는 한 값을 알기 위해 뭐가 필요한지를 생각해보면 된다.

3*2와 2*4 와 4*2 사이즈의 행렬을 곱할 때의 계산량을 따져보자. 왼쪽 두 행렬을 먼저 곱하면 3*2*4 + 3*2*4 = 48 , 오른쪽 두 행렬을 먼저 곱하면 3*2*2 + 2*4*2 = 28이므로 오른쪽 두 행렬을 먼저 곱하는 것이 낫다.

DP Solution

• Compute optimal cost for all possible Mi * ... * Mj
• That is, if the calculation looks like ... * (Mi * ... * Mj) * ..., the cost inside does not depend on how calculations are done outside!

m(1, 1), m(1, 2), m(1, 3), m(1, 4), …, m(2, 2), m(2, 3), …, m(3, 3), m(3, 4), …, m(n-1, n) –> O(N^2)

쉽게 생각해서 M1 * M2 * M3 * ... * Mn을 구할 때, 어떤 순서로 곱셈을 할 지를 생각해보자. 마지막으로 M1 * M2 * M3과 M4*... * Mn을 곱한다고 할 때, M1 * M2 * M3와 M4*... * Mn 안에서는 어떤 식으로 곱해서 결과가 나오는지는 신경쓰지 않는다. 따라서 전체 비용을 최소화하기 위해서는 M1 * M2 * M3하는데 드는 비용과 M4*... * Mn하는데 드는 비용을 최소화하면 된다. 그리고 이들은 마지막 곱셈을 하는 것과 독립적이기 때문에 따로 구한다.

근데 어떤 연산을 마지막으로 할 때가 전체 비용이 최소가 되는지를 어떻게 아는가? 그래서 다 해보자는 것이다.

다시 돌아와서, Mi * ... * Mj를 계산하는데 드는 비용을 최소화해보자.

D(i, j)=
k=i부터 k=j-1까지 min[ D(i, k) + (D(k+1, j) + d(i-1)*d(k)*d(j)]

k=i: Mi를 마지막에 곱하는 경우
D(i, k): Mi부터 Mk까지 곱하는데 드는 비용

k-i, j - (k+1)는 j-i보다 항상 작다. 그래서 차이가 작은 것부터 계산하면 된다는 것을 알 수 있다.

Code

int M(int d[], int n) {
	int D[n+1][n+1;
	for (i = 1; i <= n; i++) D[i][i] = 0; // Mi부터 Mi까지 곱하는 비용. 0임!
	for (s = 1; s <= n - 1; s++) { // 차이
		for(i = 1; i <= n - s; i++) { // i + s가 n
			minval = INF;
			for(k = i; k <= i + s - 1; k++) {
				minval = min(minval, D[i][k] + D[k+1][n] + d[i-1]*d[k]*d[i+s]);
			}
			D[i][n] = minval;
		}
	}
	return D[1][n];
}

Maximum Subarray

• Find the consecutive subarray with maximum sum
• O(N^3) is easy
• O(N^2) is kind of easy
• O(N)?
• Do we allow subarray with zero elements?

| 3 | -5 | 2 | 4 | -2 | 3 | -6 | 8 | |–|–|–|–|–|–|–|–|

O(N^3) : 모든 가능한 연속된 subarray(N^2/2개)에 대해 계산한다. 각 연산에 걸리는 시간은 O(N).

O(N^2): Prefix sum을 사용. prefix sum은 처음부터 지금까지의 합이다. 계산을 편하게 하기 위해 젤 앞에 0을 넣어줌.

Prefix sum을 사용하면 어떤 구간의 합을 쉽게 구할 수 있다.

그러면 O(N)으로도 maximum subarray를 구할 수 있을까?

(참고로 방법은 같지만, element size가 0이 되는 것을 허용할 때에는 답이 달라질 수 있다. 예를 들어 모든 원소가 음수인 배열의 경우 element size로 0을 허용하면 답은 빈 arrray가 됨.)

Idea 1

• Computer the maximum subarray ending at element i

i번째 인덱스에서 끝나는 subarray의 sum을 구하면 위와 같다.

우리는 dp를 하고 있으니까 다음 자리를 추가해보자.

현재 i번째 인덱스에서 끝나는 subarray 중 maximum subarray의 모든 원소들의 합을 x라 하고, i+1번째 원소의 값을 y라 하자. 그러면 x+y는 세 가지 경우로 나눌 수 있다.

• x+y > 0
  • x+y는 i+1번째 인덱스에서 끝나는 가장 좋은 합이 된다.
• x+y = 0 양쪽에 넣어도 되는 special case.
• x+y < 0
  • 차라리 빈 array가 나으므로 0을 넣어주면 됨,

위의 경우는 element size가 0인 경우를 허용했을 때이고, 허용하지 않을 때는 x+y > y를 기준으로 나누면 된다,

알고연 수업 때 prefix sum을 사용해 푸는 문제를 풀었는데 이 방법을 몰라서 한참 헤맸었다. 이래서 많이 아는게 중요해.. Codeforces 1285B: Just Eat It!

Idea 2

• Compute 2 values for each i
  • Max subarray that contains element i (1)
  • Max subarray that may not contain element i (2)

(1)과 (2)를 동시에 계산한다.