[알고리즘:DP] 백준(BOJ) 9251번 LCS

LCS(Longest Common Subsequence)

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

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

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

ACAYKP

CAPCAK

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

ACAYKP

CAPCAK

▶ AAK

ACAYKP

CAPCAK

▶ CAK

ACAYKP

CAPCAK

▶ ACAK

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

제약조건

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

풀이

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

A O L D M K E P P A

O C A C K E M P P A 

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

A O L D M K E P P A

O C A C K E M P P A

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

A O L D M K E P P A

O C A C K E M P P A

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

A O L D M K E P P A

O C A C K E M P P A

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

A O L D M K E P P A

O C A C K E M P P A

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

A O L D M K E P P A

O C A C K E M P P A

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

A O L D M K E P P A

O C A C K E M P P A

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

A O L D M K E P P A

O C A C K E M P P A

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

A O L D M K E P P A

O C A C K E M P P A

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