[백준] 9251번 C/C++ 풀이 _ LCS

출처 : https://www.acmicpc.net/problem/9251

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	7645	3240	2400	41.746%

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를 출력한다.

예제 입력

ACAYKP
CAPCAK

예제 출력

힌트

출처

문제를 만든 사람: baekjoon

알고리즘 분류

다이나믹 프로그래밍

>> 해결 방법

문자열 관련한 문제는 지식이 너무 부족한 것 같다.
문제를 보고 결국 풀 수 없어서 답을 보고 말았다.

포스팅 하단의 출처들을 이용하여 이해하는 것도 도움이 될 것이다.

기존에는 문자열을 이용할 때, 가능한 수열을 전부 각각 만들어서 하나하나 비교했다.
이럴 경우에는 시간 복잡도가 O( 2ⁿ * 2^m ) 이 되어버려서 너무 속도가 느려진다.

하지만 LCS의 경우에는 속도가 매우 빨라진다.
문자열의 길이가 n, m 일때, 시간 복잡도는 O(nm)이다.

원리는 다음과 같다.

두 문자열 ACAYKP과 CAPCAK가 있다.

아래의 표를 채워가면서 진행해보자.
첫 라인은 전부 0으로 채워준다.

0	A	C	A	Y	K	P
0	0	0	0	0	0	0
C
A
P
C
A
K

왼쪽부터 차례대로 값을 채워나가는데, 규칙은 아래와 같다. (원래 가로도 0인 행렬을 A 앞에 추가해야 하는데 실수로 빼먹었다. )

만약, 비교하는 위치의 문자가 서로 같으면 
    현재 위치의 값 = 왼쪽 대각선 값 + 1  (배열 범위를 벗어났으면 0이라고 가정 )
다르다면  
    현재 위치의 값 = MAX{왼쪽 값, 위쪽 값}

CAPCAK 는 한 글자씩 증가하면서, ACAYKP와 비교한다.
따라서, 이번에는 C만 이용해서 비교해보자.
처음에는 A와 C가 다르기 때문에 0이 된다.

0	A	C	A	Y	K	P
0	0	0	0	0	0	0
C	0
A
P
C
A
K

다음에는 C가 동일하기 때문에 좌대각 + 1 을 적용한다.

0	A	C	A	Y	K	P
0	0	0	0	0	0	0
C	0	1
A
P
C
A
K

규칙을 적용하여 한 열을 채워보았다.

0	A	C	A	Y	K	P
0	0	0	0	0	0	0
C	0	1	1	1	1	1
A
P
C
A
K

규칙을 계속해서 적용하면 아래와 같은 형식이 나온다.

0	A	C	A	Y	K	P
0	0	0	0	0	0	0
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

일단 표를 채워봤는데 어떻게 읽어야 할까??

표를 읽는 법은 다음과 같다.

! 행에서 현재까지 나온 문자열과 열에서 현재까지 나온 문자열 사이의 LCS 길이 !

예시를 들어보자.

0	A	C	A	Y	K	P
0	0	0	0	0	0	0
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

위의 색칠된 영역은 어떻게 읽어야 할까??
ACAY와 CA 사이의 최장공통수열(LCS)의 길이는 2이다.

최장 공통 수열 자체를 알기 위해서는 숫자가 변화한 지점을 아래와 같이 체크해준다.
각각의 행과 열에는 하나의 체크만이 있어야 한다(모든 모양은 계단형태로 나온다.)

가장 큰 숫자가 가장 먼저 변한 지점에서 부터 시작해서, 숫자를 한 개씩 줄여가면서 좌 대각방향에서 가장 먼저 숫자가 바뀐 지점을 또 선택한다. 이와 같은 과정을 반복하여 1까지 선택해준다.

그러면 색칠된 부분의 글자를 순서대로 읽어서 CA를 구할 수 있고, ACAY와 CA 사이의 LCS가 CA인 것과 동일하다.

0	A	C	A	Y	K	P
0	0	0	0	0	0	0
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

아래의 예시에서는 ACAYK 와 CAPCAK 사이의 LCS를 구하는 것이다.

0	A	C	A	Y	K	P
0	0	0	0	0	0	0
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C	1	2	2	2	2	3
A	1	2	3	3	3	3
K	1	2	3	3	4	4

(1) 4가 가장 크기 때문에, 가장 먼저 4가 바뀐 지점을 선택한다.
(2) 4-1 = 3 이기 때문에, 3이 가장 먼저 나온 지점을 좌대각 방향에서 선택한다.
(3) 3-2 = 2 이기 때문에, 2가 가장 먼저 나온 지점을 좌대각 방향에서 선택한다.
(4) 2-1 = 1 이기 때문에, 1이 가장 먼저 나온 지점을 좌대각 방향에서 선택한다.

위와 같은 경우에는 (3) 까지 수행하고 나면, 좌대각 A, P 중에서 A 가 더 위에 있기 때문에 A를 선택한다.
그러면 ACAK 가 나오고, 이는 ACAYK 와 CAPCAK의 LCS 이다.

위에서 언급한 계산이 왜 나오게 되는 것일까??

표의 값을 구할 때 같은 문자가 나오면 이전까지의 LCS의 길이에 +1을 한다. 여기에서 이전까지의 LCS의 길이란 왼쪽값이 아니라 대각선(왼쪽 위)값을 말한다. 이는 두 문자열에서 해당 두 문자를 비교하기 전의 LCS의 길이에 +1을 하기 위해서 이다.

또한 비교한 문자가 다르다면, 비교한 문자가 포함되어 있는 직전 LCS, 즉 표에서는 위와 왼쪽 값중 큰 값이 오게된다. 예를 들면 아래의 표에서 [P,Y]의 값은 'CAP'와 'ACAY'를 비교한 값이 오게 되고, 'P'와 'Y'는 다르기 때문에 'CA'와 'ACAY'의 LCS의 길이와 'CAP'와 'ACA'의 LCS의 길이중 큰 값이 오게된다.

0	A	C	A	Y	K	P
0	0	0	0	0	0	0
C	0	1	1	1	1	1
A	1	1	2	2	2	2
P	1	1	2	2	2	3
C
A
K

>> 소스 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include<cstdio>
#include<algorithm>
using namespace std;
char s1[1002], s2[1002];
int dp[1001][1001], i, j;
int main() {
    scanf("%s %s", s1 + 1, s2 + 1);
    for (i = 1; s1[i]; i++)
        for (j = 1; s2[j]; j++)
            dp[i][j] = max({ dp[i][j - 1], dp[i - 1][j],
                             dp[i - 1][j - 1] + (s1[i] == s2[j]) 
                           });
    printf("%d", dp[i - 1][j - 1]);
    return 0;
}
Colored by Color Scripter
cs