'메모이제이션'에 해당되는 글 2건

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할때 메모이제이션으로 값을 업데이트 시키는 것은 잊지 말고 말이죠.

동적계획법(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이라는 값이 들어있을 겁니다. 그렇지 않을까요? 이해 되십니까?