'dp'에 해당되는 글 6건

LCS(Longest Common Subsequence)

백준 9251번입니다. 문제는 이렇습니다.

임의의 두 수열에서 공통적으로 갖고 있는 가장 긴 부분 수열의 길이를 구하는 것이 문제입니다.

예를 들어 다음과 같은 두 수열이 있다고 합시다.

첫번째 수열과 두번째 수열의 공통수열은 다음과 같습니다.

이 외에도 여러가지 공통 수열이 있지만 가장 긴 수열은 4의 길이를 갖고 있는 ACAK입니다. 두 수열에서 LCS는 여러가지가 있지만 그 길이는 같지요.

제약조건

두 수열을 항상 대문자 알파벳으로 주어지고 각 수열의 길이는 1이상 10000이하입니다.

풀이

이 문제는 생각보다 단순합니다. 두 수열의 문자를 비교해 일치하면 동시에 한칸을 옮겨서 그 다음부터 비교하면 되고, 만약 일치하지 않는다면 두 수열중 아무것이나 한칸 옮겨서 그 다음부터 비교하면 됩니다.

위 두 수열의 LCS길이는 AKEPPA 또는 OKEPPA입니다. 그렇기때문에 답은 6이 나오지요. 이 답이 나오는 과정을 살펴보도록 하겠습니다.

빨간색 글자는 현재 비교할 두 문자입니다. 우선 초기상태이므로 A와 O가 비교됩니다. 두 문자가 일치하지 않으므로 A의 다음 문자를 비교하거나 O의 다음 문자를 비교합니다. 저는 일부러 답을 찾기 위해서 최적의 방법을 사용할 것이니 여러분들은 두 수열 중 어떤 수열을 먼저 한칸 더 옮기든지 상관없다는 것만 아시면 됩니다.

첫번째 수열의 비교 문자를 한칸 옮기니까 두 수열의 문자가 일치하는 군요. 그렇다면 두 수열의 비교문자를 다음으로 옮겨줍니다.

L과 C는 일치하지 않으므로 두 수열중 비교할 문자를 한칸 뒤로 옮깁니다.

이런식으로 이제 계속 비교하다가 보면 언젠가는 다음과 같은 상황이 발생합니다.

이제 K와 K를 비교할 때가 된거죠. K는 두 수열이 두 수열의 비교문자를 모두 다음 위치로 이동합니다.

E 역시 두 문자가 같으므로 다시 또 한칸 동시에 비교문자를 옮깁니다. 옮기고 난 후 보니까 P와 M은 일치하지를 않지요. 그러니까 둘 중 아무 수열이나 비교할 문자를 한칸 옮겨줍니다. 저는 답을 찾기위해 일부터 아래 수열의 비교문자를 한칸 더 옮기겠습니다.

이제 P는 두 수열 모두 같으니 다음 칸으로 옮겨줍니다. 계속 이런식으로 답을 찾으면 결국 다음과 같은 LCS가 나오게 되는 것이죠.

이 LCS는 OKEPPA이고 길이가 6인 것을 알 수 있습니다. 따라서 답은 6이 되는 겁니다.

DP적용

이렇게 답은 찾았는데요. 길이가 10000인 두 수열을 이런식으로 계속 비교하다가는 시간안에 답을 찾기가 힘듭니다. 우리가 자세히 살펴본다면 DP를 적용할 수 있다는 사실을 알 수 있는데요. 만일 수열에서 순서가 A와 O를 비교했는데 아래 배열의 비교 문자를 옮긴다면 A와 C를 비교하게되어 O를 빠뜨리고 가지요. 분명 O는 일치하는 문자임에도요. 

[1][2][3][4][5][6][7][8][9][10]

A O L D M K E P P A

[1][2][3][4][5][6][7][8][9][10]

O C A C K E M P P A

그래서 결국 KEPPA까지만 일치하게 된 상황에서 각 인덱스는 [6][5]입니다. 

따라서 [6][5]에서 가장 긴 수열은 5라고 기억하지요. 그리고 다시 이전으로 돌아가서 비교해야합니다. 그때는 순서를 바꿔 O가 일치하는 상황이 되죠.

[1][2][3][4][5][6][7][8][9][10]

A O L D M K E P P A

[1][2][3][4][5][6][7][8][9][10]

O C A C K E M P P A

이렇게 [6][5]까지 비교한다면 이미 기억해두었으니 제차 끝까지 비교하지 않고 [6][5]까지의 값 5를 반환하기면 하면 됩니다. 그리고 O는 일치했으므로 1을 더하는것이죠. 그래서 답이 6이 됩니다. 이렇게 DP를 적용해서 시간을 줄일 수 있습니다.

구현

다음의 코드는 LCS의 길이를 구하는 코드입니다. 위의 설명을 잘 이해했다면 코드 역시 이해하기가 훨씬 쉬울거에요.

#include <stdio.h>
#include <string.h>

#define MAX(a,b) a>b ? a:b
#define _CRT_SECURE_NO_WARNINGS
char a[1001], b[1001];
int n, m;
int dp[1001][1001];
int solve(int pos1, int pos2) {
	if (pos1 == n || pos2 == m) return 0;
	if (a[pos1] == b[pos2])
		return 1 + solve(pos1 + 1, pos2 + 1);

	int ret = 0;
	if (dp[pos1][pos2] != -1) return dp[pos1][pos2];
	ret = MAX(solve(pos1 + 1, pos2), solve(pos1, pos2 + 1));
	return dp[pos1][pos2] = ret;
}
int main() {

	scanf("%s %s", a, b);
	n = strlen(a); m = strlen(b);
	memset(dp, -1, sizeof(int) * 1001 * 1001);
	int ret = solve(0, 0);
	printf("%d\n", ret);
}

pos1은 첫번째 수열의 비교할 문자 위치, pos2는 두번째 수열의 비교할 문자위치를 말합니다. 만약 pos1과 pos2이 하나라도 수열 끝까지 갔다면 종료되는 것이죠. 이것이 기저 사례입니다.

앞서 말한것과 같이 첫번째 수열의 pos1위치의 문자와 두번째 수열의 pos2위치 문자와 비교해서 같다면 LCS의 길이 1을 더해주고 비교할 문자의 위치 pos1,pos2를 한 칸 증가시켜줍니다.

만약 일치하지 않는다면 둘 중 하나의 수열 비교문자(pos1 또는 pos2)만 한칸 증가시키고 둘 중 가장 큰 값을 반환하면 되죠.

나중에 return할때 메모이제이션으로 값을 업데이트 시키는 것은 잊지 말고 말이죠.

배낭 알고리즘(Knapsack algorithm)

알고리즘에서 DP를 배울때 등장하는 유명한 문제가 있습니다. 제목과 같이 바로 배낭알고리즘이지요. 배낭알고리즘도 여러가지가 있지만, 우리는 조건이 가장 간단한 0/1 배낭 알고리즘 문제를 알아보도록 하겠습니다.

상황은 이렇습니다.

어떤 REAKWON이라는 이름의 도둑놈이 있습니다. 이 도둑은 새벽 늦은 시간 도둑질을 하기 위해서 남의 집에 들어가는데 까지는 성공했습니다. 그리고 훔쳐갈 물건들을 담기 위해 배낭도 챙겼지요. 데헷

하지만 이 도둑은 안타깝게도 아이큐가 70입니다. 배낭의 용량은 한정되어 있고 무거우면 들고갈 수도 없으므로 가장 값어치가 비싸고, 무게가 적은 물건들을 최대한 많이 담아가야합니다.

하지만 조건이 있습니다.

1) 물건을 부분적으로 담을 수는 없습니다.

2) 물건들은 모두 한개씩만 있습니다. 예를 들어 똑같은 반지가 2개일 수 없다는 이야기입니다.

도둑은 현재 15의 무게를 담을 수 있는 배낭을 가지고 있습니다. 그리고 아래와 같이 그 집의 물건이 있지요. 

이 상황에서 도둑이 훔쳐갈 수 있는 최대의 값을 구하는 것입니다.

어떻게 도둑을 도와줄것인가?

아 그냥 무게가 가장 적은거 순서대로 훔쳐가면 되지 않을까요?

라고 생각하신다면 다시 한번 생각해봅시다.

위의 물건들을 가장 작은 무게가 나가는 것을 훔쳐가게 된다면 items[4], items[2], items[3], items[0]만 가져갈 수 있고, 총 가치는 21이 되고 총 용량은 14가 됩니다.

하지만 items[0], items[1], items[4]를 선택한다면 총 가치는 23이 되고, 용량은 15로 더 비싼물건을 훔칠 수 있습니다.

그렇기 때문에 무게가 덜 나가는 순으로 정렬해서 문제를 해결할 수가 없는것이죠.

그래서 단순 무식하게 한번 접근해봅시다.

도둑은 그 물건을 훔쳐갈 수 있느냐, 훔쳐갈 수 없느냐 이 둘만 고려합니다. 

1) 훔쳐갈때 

만약 어떤 물건을 훔쳐갈 수 있다고 한다면 현재 무게가 그 물건의 무게만큼 무거워지요. 하지만 배낭 용량을 초과할 수는 없습니다. 그럴땐 그 물건을 배낭에 담을 수가 없습니다.

현재 그 물건들을 배열로 표현(items)하고, 어떤 물건을 고려 할때 그 아이템의 인덱스를 pos라고 합시다. 그리고 현재 용량을 capacity라고 해봅시다. V는 그 물건의 가치, W는 그 물건의 용량이라고 친다면 우리는 이런 식을 쓸 수 있습니다.

 knapsack(pos + 1, capacity - items[pos][W]) + items[pos][V]

knapsack이라는 함수는 현재 물건 이후 가장 큰 값을 반환합니다. 그러니까 당연히 용량(capacity)는 그 물건의 무게(items[pos][W])만큼 줄어들 것이고, 그 반환된 가장 큰 값에서 현재 물건의 가치를 더함으로써 지금 이 물건을 훔쳤을때 얻을 수 있는 값을 얻을 수 있습니다.

2) 훔쳐가지 않을 때

그리고 또 그냥 그 물건을 안가져갈 수도 있습니다. 그럴때는 현재 무게가 그대로 유지되면서 다음 물건을 고려하는 겁니다.

그러니 아래의 식이 가능합니다.

knapsack(pos + 1, capacity )

1)훔쳐갈 경우와 2)훔쳐가지 않을 경우 중에서 가장 큰 값이 우리가 원하는 답이 되는 것이죠.

코드

이런 프로그램을 구현한 것이 바로 아래 소스 코드입니다.

#include <stdio.h>
#define W 0
#define V 1
#define N 5
#define MAX(a,b) a>b ? a:b;

int items[N][2] = {
	,
	,
	,
	,
	
};

int knapsack(int pos,int capacity) {
	if (pos == N) return 0;
	
	int ret = 0;
	if (items[pos][W] <= capacity) //지금 pos의 물건을 훔칠 수 있을때
		ret = knapsack(pos + 1, capacity - items[pos][W])
		+ items[pos][V];
        //지금 pos의 물건을 훔치지 않을때와 ret 중에 큰 값
	ret = MAX(ret, knapsack(pos + 1, capacity)); 
	return ret;
}
int main() {
	int capacity = 15;
	printf("knapsack(%d,%d)=%d\n",0,capacity, knapsack(0, capacity));
	return 0;
}

답은 원하는 결과대로 나옵니다.

허나 이런 무식한 해결방법을 원한 것을 아닙니다.

만약 물건의 수가 많게 된다면 답을 구하기 전에 도둑은 감방으로 직행하게 될 것입니다. knapsack함수는 분명 같은 값을 여러번 중복해서 계산합니다. knapsack(pos,capacity)에서 같은 pos와 같은 capacity가 이전에 계산했었음에도 불구하고 또 다시 한번 더 계산한다는 것이죠.

그래서 DP가 사용됩니다. 단지 계산된 결과를 기억하고 있다가, 같은 계산을 수행할때 바로 값을 반환해주면 됩니다.

아래의 수정된 코드처럼 말입니다.

#include <stdio.h>
#include <stdlib.h>
#define W 0
#define V 1
#define N 5
#define MAX_CAPACITY 1000
#define MAX(a,b) a>b ? a:b;

int dp[N][MAX_CAPACITY];
int items[N][2] = {
	,
	,
	,
	,
	
};

int knapsack(int pos,int capacity) {
	if (pos == N) return 0;
	
	int ret = dp[pos][capacity];
	if (ret != -1) return ret;
	if (items[pos][W] <= capacity)
		ret = knapsack(pos + 1, capacity - items[pos][W])
		+ items[pos][V];
	ret = MAX(ret, knapsack(pos + 1, capacity));
	return dp[pos][capacity]=ret;
}
int main() {
	int capacity = 15;
	memset(dp, -1, sizeof(dp));

	printf("knapsack(%d,%d)=%d\n",0,capacity, knapsack(0, capacity));
	return 0;
}

우선 dp라는 2차원 배열을 -1로 셋팅합니다. 그리고 dp[pos][capacity]가 -1이 아니면 바로 그 값을 반환합니다. 배낭문제에서 음수는 나올 수 없습니다. 만약 계산되지 않은 값이라면 계산 후 dp[pos][capacity]에 값을 넣어주는 것입니다. 기억하고 있습니다.

결국 도둑은 가장 비싼 물건들을 훔쳐갈 수 있었지만, CCTV에 걸려 감방에 끌려가게 됩니다. 그걸 도와준 저도 같이 갑니다.

1912번 연속합

문제 해석

수열에서 연속된 수들의 합이 가장 큰 것을 구하는 문제입니다.

10, -4, 3, 1, 5, 6, -35, 12, 21, -1 라는 수열에서 가장 큰 연속은 얼마일까요?

12, 21 부분이 가장 큰 연속합입니다.

연속합의 수들은 한개 이상이라는 점입니다.

음

쉬워보입니다.

처음 시작점을 고정하고 끝점을 하나씩 늘려가면서 시작점과 끝점을 전부 더하는 거죠. 전부 현재의 최대값과 비교해서 크면 그게 최대값이 되는 식으로요.

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
	int n;
	int nums[100001];

	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &nums[i]);

	int ans = -1001;
	for (int start = 0; start < n; start++) {
		for (int end = start; end < n; end++) {
			int sum = 0;
			for (int i = start; i <= end; i++)
				sum += nums[i];
			ans = max(sum, ans);
		}
	}
	printf("%d\n", ans);
}
	

네, 이렇게 제출하면 시간초과랍니다. 하하

입력이 자그마치 10만개가 되거든요.

단순히 이렇게 for루프만 돈다면 문제를 해결할 수가 없습니다.

여기서 간단한 이론(?)이 있는데요.

부분합이라는 개념이 여기 사용됩니다.

우리는 전에 계산한 합을 이용할 수 있다는 거죠.

[0]~[5]까지의 합은 [0]~[4]까지의 합 + 현재의 수를 더하면 된다는 것을 알 수 있습니다.

코드로 본다면 이런 형태이죠.

for (int i = 1; i <= n; i++)
		partialSum[i] = partialSum[i - 1] + numbers[i];

i가 1부터 시작한 이유는 조금 더 보기 편하게 하기 위함입니다. 그러니까 n까지 for루프를 돌아야 됩니다.

그렇다면 [7]~[8]까지의 합만을 구하려면 어떻게 할까요?

partialSum[8]-partialSum[6]을 하게 되면 [7]과 [8]의 부분합만을 구할 수 있습니다.

그럼 1부터 3까지의 합은 partialSum[3]-partialSum[0]이 되겠죠? 인덱스를 왜 1부터 시작하는 지 이유를 알 것 같습니다. 그렇지 않으면 if문을 사용해야합니다.

이제 우리는 위의 코드를 2개의 for문으로 줄일 수 있습니다.

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
	int n;
	int partialSum[100001];

	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		int number;
		scanf("%d", &number);
		partialSum[i] = partialSum[i - 1] + number;
	}
	int ans = -1001;
	for (int start = 0; start <= n-1; start++) {
		for (int end = start + 1; end <= n; end++) {
			ans = max(ans, partialSum[end] - partialSum[start]);
		}
	}
	printf("%d\n", ans);
}
	

부분합을 이용해서 이중 for문으로 문제에 접근할 수도 있지만, 이 역시 시간초과가 됩니다. 아까 말한것 처럼 입력이 10만개이기 때문에 이중 for문 역시 시간초과죠.

여기서 한 번 더 줄일 수 없을까요?

부분합을 이용해서 말이죠. 

그전까지 계산한 부분합 + 지금 숫자가 지금 숫자보다 작다면 부분합은 다시 계산 되어야 한다는 것을 직관적으로 느낄 수 있을까요??

그러니까...

현재의 수를 numbers[i]라고 하고 그 전까지 계산했던 부분합이 partialSum[i-1]라고 할때 , partialSum[i]=max(partialSum[i-1]+numbers[i], numbers[i]) 라고 하는 것 말이에요.

다시말해,

partialSum[i]=max(partialSum[i-1]+numers[i], numbers[i])

                =max(지금까지의 부분합, 현재 수)

라고 하는 것이 이해가 가시나요?

지금까지 구한 부분합이 현재의 수보다 작다면 현재의 수부터 다시 부분합을 계산하는 것이 더 클 거니까요.

이것만 이해가 간다면, 다음의 코드는 이 과정을 배열없이 구현했다라는 것을 알 것입니다.

#include <cstdio>
#include <algorithm>

using namespace std;

int main() {
	int n, partialSum = 0, maxPartialSum = -1001;
	scanf("%d", &n);

	for (int i = 1; i <= n; i++) {
		int number;
		scanf("%d", &number );
		partialSum = max(number, number + partialSum);
		maxPartialSum = max(partialSum, maxPartialSum);
	}

	printf("%d\n", maxPartialSum);
	
}
	

코드가 무척이나 짧아졌습니다.

문제의 답은 maxPartialSum입니다. 

코드에서 이 부분을 보세요.

partialSum = max(number, number + partialSum);

number는 현재의 수를 말하는 것이고, partialSum은 이전까지 계산했던 부분합을 의미합니다.

현재의 수와 이전까지 계산했던 부분합 + 현재의 수가 현재의 수보다 작다면 부분합은 다시 현재의 수부터 시작입니다.

이후 이 부분합(partialSum)과 지금까지 부분합의 최대값(maxPartialSum)을 비교해서 큰 값이 다시

maxPartialSum이 되는 것입니다.

1463번 1로 만들기

문제 해석

문제는 너무 간단 합니다. 세가지 규칙이 있는데요.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

이렇게 만들어서 1로 만들어라 이겁니다. 12를 최소로 위 규칙을 사용하면 어떤 과정을 거칠 수 있을까요?

12 - 4(1번 규칙 적용) - 2(2번 규칙 적용) - 1(2번 또는 3번 규칙 적용)

이렇게 3번으로 1을 만들 수 있다는 건데요. 

36은 어떻게 구할 수 있을까요?

36 - 12(1번 규칙 적용)

12는 위에서 구했습니다. 감이 오시죠? DP냄새가 나지 않습니까?

#include <cstdio>
#include <string.h>

#define min(x,y) x<=y ? x:y
#define INF 987654321
using namespace std;

int dp[1000001];

int solve(int n) {

	if (n == 1) return 0;
	if (dp[n] != -1) return dp[n];

	int ret = INF;
	if (n % 2 == 0) ret = 1 + solve(n / 2);
	if (n % 3 == 0) ret = min(ret, 1 + solve(n / 3));
        //ret = min(ret, 1+solve(n-1));
	if (n % 6 != 0) 
		ret = min(ret, 1 + solve(n - 1));

	return dp[n] = ret;
}

int main() {

	int n;
	scanf("%d", &n);

	memset(dp, -1, sizeof(dp));
	printf("%d\n", solve(n));
}

n을 규칙대로 3으로 나누어 떨어지면 3으로 나누고, 2로 나누어 떨어지면 2로 나누고, 또는 1을 뺀 규칙을 적용해서 1로 만들어보는 것입니다. 3으로 나누어 떨어지지 않거나, 2로 나누어 떨어지지 않을 땐 1을 빼는 규칙을 적용해줍니다.

왜요?

n을 1로 만들어주는데 있어서 2와 3으로 나누는 것이 유리하다는 것이죠. 어떤 수로 나누는 것이 n을 줄이는 일에 효과적이라는 겁니다. 그래서 1을 최소로 빼주고 될 수 있으면 2와 3으로 나누는 편이 더 좋습니다.  그러니 2와 3의 최소 공배수 6을 이용해서 6으로 나누어 떨어지지 않으면 1을 빼는 것을 시도하는 것입니다.

위 코드의 주석을 해제하고 if문 부분을 주석처리하여 제출해보세요. 결과는 맞지만 효율성에서 차이가 나는게 보일겁니다.

1932번 정수 삼각형

문제가 이해되셨나요?

맨 위 삼각형 꼭지점에 있는 숫자부터 시작해서 아래까지 계속하여 더합니다. 그 중 가장 큰 수를 구하는 것입니다. 

하지만 조건이 걸려있지요! 바로 위에서 아래로 내려올때 대각선 왼쪽, 또는 오른쪽으로 내려오면서 그 숫자를 더하는 겁니다. 

문제에 있는 예제부터 보겠습니다.

#include <stdio.h>
#include <string.h>
#define N 501
#define max(a,b) a>b ? a:b

int triangle[N][N], dp[N][N];
int n;
int solve(int y, int x) {
	if (y>n || x>n ) return -99999999;
	if (y == n) return triangle[y][x];
	if (dp[y][x] != -1) return dp[y][x];
	int ret = 0;
	ret = max(triangle[y][x] + solve(y + 1, x),
		triangle[y][x] + solve(y + 1, x + 1));
	return dp[y][x] = ret;
}
int main() {
	int i;
	scanf("%d", &n);
	for (i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			scanf("%d", &triangle[i][j]);
	memset(dp, -1, sizeof(dp));
	printf("%d\n", solve(1, 1));
	
}

동적계획법(Dynamic Programming)

동적계획법(Dynamic Programming)이라는 것은 알고리즘에서 아주 자주 등장하는 주제입니다. 줄여서 DP라고도 부릅니다.

DP의 특징은 어떤 부분 문제는 두 개 이상의 문제를 푸는 데 사용될 수 있습니다. 그래서 "답을 여러 번 계산하는 대신 한번 만 계산한다!" 입니다.  

개인적으로 DP를 보면 항상 먼저 떠오르는게 바로 재활용이라고 생각합니다. 재활용을 통해서 속도를 빠르게 향상 시킬 수 있는 방법입니다.

어떻게 재활용을 할 수 있을까요? 가장 유명한 피보나치 수열을 한 번 보도록 해봅시다. 피보나치의 정의는 아래와 같습니다. 간단합니다.

이 피보나치 수열을 재귀함수로 정의해보겠습니다. 

int fibo(int n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	return fibo(n - 1) + fibo(n - 2);
}

이런식으로 정의가 될 것 같네요. 여기서 n은 무조건 양수라고 가정하겠습니다. 음수는 귀찮습니다. 만약 fibo(5)라는 값을 계산하려면 어떤 과정을 거칠까요?

fibo(5) = fibo(4) + fibo(3) 라는 것을 알 수 있고 이제 fibo(4)와 fibo(3)을 더해주기만 하면 됩니다.

그럼 왼쪽 fibo(4)부터 차근 차근히 계산을 해보도록 하겠습니다. 노가다로 해보겠습니다.

fibo(4) = fibo(3) + fibo(2) 

이것도 역시 fibo(3), fibo(2)를 계산해야 되겠군요

fibo(3) = fibo(2) + fibo(1) 이 되겠습니다.

fibo(2) = fibo(1) + fibo(0) 이 되어서 fibo(2) = 1이라는 것을 알게 됩니다.

그렇다면 fibo(3) = fibo(2) + fibo(1) 이니까 1+1 해서 fibo(3) = 2라는 것을 알 수 있겠네요.

fibo(4) = fibo(3) + fibo(2) 랍니다. 여러 분, 이제 슬슬 감이 오고 있나요? 노가다 하기 싫습니다.

fibo(4) = 2 + fibo(2)라는 것이 됩니다. fibo(3)을 방금전에 계산했거든요. 그러면 오른쪽 fibo(2)를 구해보도록 합시다.

fibo(2) = fibo(1) + fibo(0) 으로 fibo(2)=1입니다.

그럼 fibo(4) = 2+ 1 = 3 이라는 결과가 나옵니다. 이제 fibo(4) 구한 겁니다.

이제 fibo(3)을 구해볼까요?

이제 손가락이 아파서 못할 거 같고요

fibo(3) 뭐라고 했지요? 아까 계산했는데 말입니다.

2가 나왔죠?

이 같은 노가다를 막기 위한 것이 바로 DP의 큰 역할이라고 할 수 있겠습니다. 만약 위의 저 코드를 통해서 fibo(40)을 계산한다면 얼마나 걸릴까요? 아마 계산했던 결과를 또 계산하고 앉아있으니 오래 걸릴거라는 걸 짐작할 수 있나요?

네, 오래 걸립니다. 우리는 이제 계산된 값을 재활용 합시다. 이렇게요.

int dp[50];
int fibo(int n) {
	
	if (n == 0) return 0;
	if (n == 1) return 1;
	if (dp[n] != -1) return dp[n];
	return dp[n] = (fibo(n - 1) + fibo(n - 2));
}
int main() {
	memset(dp, -1, sizeof(dp));
	printf("fibo(40)=%d\n", fibo(40));
}

어떻습니까? 맨 처음 초기화값은 -1입니다. memset함수에 주목합시다. 이 함수는 dp라는 배열을 -1이라는 값으로 전부 초기화 시키는 역할을 하는 것이랍니다. 처음 계산하는 값이라면 dp[n]에 -1이라는 값이 들어있을 겁니다. 그렇지 않을까요? 이해 되십니까?