[BaekJoon/백준] 9251번 | 복습 1회 완료 (★)

LCS (Longest Common Subsequence)

최장 공통 수열을 구하는 문제.

 

벽을 느껴서 다른 분의 풀이를 참고했다.

 

풀이는 이렇다. (예제 입력을 통한 설명)

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

ACAYKP 와 CAPCAK 의 입력을 받아들인다. 문자열의 최대길이는 1000이므로 1000를 선언해준다.

char str1[1000];

char str2[1000];

 

그리고 위 표는 dp 배열인데, 위 그림에서 보듯이 dp를 다룰 배열은 전체 크기 + 1로 놓는다.

int dp[1001][1001];

이유는, 계산과정에서 비롯된다.

 

계산은 이렇게 한다.

각 행 / 열은 우선, 기준점이 달라진다. str1에 대한 계산값이냐 str2에 대한 계산값이냐의 차이이다.

 

그리고 이 계산은 LIS인 최장증가수열 방식과 비슷한 느낌이다.

 

각 행 / 열을 i, j라고 봤을 때

dp[i][j]는 i, j 자리까지의 최장공통수열의 값을 갖고 있다. (최댓값이겠죠?)

 

1. 각 부분에서 문자가 동일할 때 dp[i][j] = dp[i - 1][j - 1] + 1이다.

dp[i - 1][j - 1]은, 이전 까지의 LCS값을 담고 있다. 각 문자열에서 i j 문자를 비교하기 전 i - 1 j - 1까지의 LCS 값에서 1을 증가해주는 것.

현재 문자가 동일하다면 LCS값을 이전 값에서 하나 늘려주는게 맞으므로 이런 계산이 나온다.

ex) AC PC가 있을 때, A P 까지는 0이지만 C C 에서 같으므로, A P 까지의 0에서 + 1.

 

 

2. 각 부분에서 문자가 동일하지 않을 때 dp[i][j] = MAX(dp[i - 1][j], dp[i][j - 1])이다.

 

위 표에서 이 부분을 확인해보자.

ACAYK

CAPCA

K와 A가 만나는 부분에 이런 표가 있다

	Y	K
C	2	2
A	3	3

편의상 i j 대신, 각 문자인 K A라고 놓게 되면

dp[K][A]의 값은 3이다. 즉 ACAYK 와 CAPCA 값의 K A 위치까지의 LCS는 3이다. 최장 공통 수열. 즉 최댓값이다.

위에서 말했듯, str1에 대한 기준과 str2에 대한 기준에 대한 수열 값이 있을 테고, K A에 대한 같은 비교라도 최장 공통 수열은 그 둘 중 최댓값을 선택해야 한다.

 

 

쉽게 말하면 K A는 같지 않으므로,

 

ACAY

CAPCA

까지의 둘의 최장 공통 수열 값

 

그리고

 

ACAYK

CAPC

까지의 둘의 최장 공통 수열 값

중 큰 값을 dp[K][A]의 값(최장 공통 수열 값)으로 채택한다.

 

---------------------------------------------------

이해가 안되는 분들이 있을까봐 추가 설명

 

ACAYK

CAPCA 의 dp[K][A]값을 구하는 방법은

 

 

ACAY 'K' 를 기준으로

CAPC 'A' 를 비교하고 있다고 보면,

A를 봤는데, K와 같지 않다.

 

따라서

 

ACAY 'K'

CAP 'C'  까지 비교했던 값(2)을 그대로 사용한다.

 

그리고 반대로

CAPC 'A'를 기준으로

ACAY 'K'를 비교하고 있다고 보면,

K를 봤는데, A와 같지 않다.

 

그러면 ACAYK에서 K 이전의 비교였던

CAPC 'A'

ACA 'Y' 까지 비교했던 값(3)을 그대로 사용한다.

 

dp[K][A]는 이렇게 두 값 2 3 중 최댓값인 3을 채택한다.

 

 

하나만 더 예를 들자.

 

ACAYKP

CAPC

둘을 비교하면서 dp[K][P] 자리의 값을 탐색하고 있다.

P != C 이므로, 이전 값에서 가져와야 한다.

 

 

ACAYK

CAPC

의 최장 공통 수열값 : CA = 2

 

ACAYKP

CAP

의 최장 공통 수열값 : CAP = 3

 

dp[P][C] 번째 자리는 어차피 다르므로, 이 이전값들 중 최댓값을 최장 공통 수열값으로 그대로 사용하는 것.

---------------------------------------------------

 

그니까, 같을 경우에는 AXC PQC 가 있을 때 str1과 str2의 C가 같으므로

두 문자열의 두 문자 전의 최장 공통 수열 값인 AX PQ 까지의 기존 최장 공통 수열값 + 1을 넣는 것이고

(dp[i][j] = dp[i - 1][j - 1] + 1)

다를 경우에는, 행 / 열 각각의 경우의 이전의 최장 공통 수열 값 중 최댓값을 가져오는 것이다.

 

그리고 다를 경우는 아래와 같다.

str1에서 ~~K, str2에서 ~~A라는 문자를 비교할 차례라고 보자.

이 경우는 두 가지가 있다. str1을 기준으로 str2를 비교하는 경우, 그리고 str2를 기준으로 str1을 비교하는 경우.

즉 두 경우에서 최댓값을 가져와야 dp[K][A]에서의 최장 공통 수열 값을 얻어올 수 있다.

(dp[i][j] = MAX(dp[i - 1][j], d[[i][j - 1]))

 

내 설명이 조금 어려웠는데.. 아마 아래 참고 블로그 글 두 개만 읽어도 이해가 될 것이다..ㅜ

 

내 소스

#include <stdio.h>
#include <string.h>
#define MAX(a,b) ((a>=b))?a:b;

char str1[1000], str2[1000];
int dp[1001][1001];
int len1, len2;

int main() {
    scanf("%s", str1);
    scanf("%s", str2);
    
    len1 = strlen(str1);
    len2 = strlen(str2);
    
    for(int i = 1; i <= len1; i++) {
        for(int j = 1; j <= len2; j++) {
            if(str1[i - 1] == str2[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = MAX(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    
    printf("%d", dp[len1][len2]);
}

주의할 점은, 문자열 비교에서 str1[i] == str2[j] 가 아니라 str[i - 1] == str2[j - 1]을 사용했다는 것..

이유는 알다시피 코드에서 dp 배열은 1부터 시작하는데, 문자열은 0부터 시작하게끔 구성되어 있기 때문이다.

 

 

참고

twinw.tistory.com/126

tunsi-niley.tistory.com/3

melonicedlatte.com/algorithm/2018/03/15/181550.html

 

---

2021.02.25 복습

다시 풀어보았다. LCS(최장 공통 부분 수열)는 진짜 어렵다.. 처음 풀 때도 벽을 느껴 다른 분의 설명을 보고 위 처럼 열심히 정리했는데,

그새 까먹었다.. 아예 기억이 나지도 않고 어떻게 풀었는지 기억도 안 나서 풀이를 봤다.. 진짜 어렵긴 하다.

 

두 번 다 못풀었기에, 제목에 별을 달았다.. 중요한 문제이므로 다시 또 봐야겠다.