[BOJ-9251][C++] LCS

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.1 초 (하단 참고)	256 MB	62233	25245	18538	40.216%

문제

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

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

 

입력

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

 

출력

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

 

예제 입력 1

ACAYKP
CAPCAK

 

예제 출력 1 

4

 

알고리즘 분류

• 다이나믹 프로그래밍
• 문자열

 

시간 제한

• Java 8: 0.4 초
• Python 3: 2 초
• PyPy3: 2 초
• Java 8 (OpenJDK): 0.4 초
• Java 11: 0.4 초
• Kotlin (JVM): 0.4 초
• Java 15: 0.4 초

 

문제 출처

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

9251번: LCS

 

---

 

문제 해결 방법

• 가능한 수열을 하나하나씩 비교하면 시간 초과가 발생하므로, DP를 이용하여 풀어야 하는 문제이다.
• 비교해야 할 문자열이 2개 이므로(@A@, @B@), 2차원 DP 테이블을 생성해준다.

int dp[a][b];

• 2차원 DP 테이블의 각 값의 의미는 현재 행(@a@)까지의 문자열과 현재 열(@b@)까지의 문자열 사이의 LCS 길이이다.

 

예제를 이용하여 문제 해결 방법 알아보기

• 문제에서 주어진 @입력 예제 1@의 값(@A@, @B@)을 2차원 표(@dp@)를 이용하여 풀어보면 다음과 같다.

 

① @dp[0][x]@ (0 ≤ @x@ ≤ 6)의 경우

• LCS를 구할 수 없으므로 모두 @0@으로 채워준다.

B \ A	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C
A
P
C
A
K

 

② @dp[1][x]@ (0 ≤ @x@ ≤ 6)의 경우

• 문자열 @B@의 @{ C }@와 문자열 @A@의 @{ A, AC, ACA, ACAY, ACAYK, ACAYKP }@의 LCS를 구하면 다음과 같다.
  • C와 A : 0
  • C와 AC : C
  • C와 ACA : C
  • C와 ACAY : C
  • C와 ACAYK : C
  • C와 ACAYKP : C

B \ A	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A
P
C
A
K

 

③ @dp[2][x]@ (0 ≤ @x@ ≤ 6)의 경우

• 문자열 @B@의 @{ CA }@와 문자열 @A@의 @{ A, AC, ACA, ACAY, ACAYK, ACAYKP }@의 LCS를 구하면 다음과 같다.
  • CA와 A : A
  • CA와 AC : A 또는 C
  • CA와 ACA : CA
  • CA와 ACAY : CA
  • CA와 ACAYK : CA
  • CA와 ACAYKP : CA

B \ A	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P
C
A
K

 

④ @dp[3][x]@ (0 ≤ @x@ ≤ 6)의 경우

• 문자열 @B@의 @{ CAP }@와 문자열 @A@의 @{ A, AC, ACA, ACAY, ACAYK, ACAYKP }@의 LCS를 구하면 다음과 같다.
  • CAP와 A : A
  • CAP와 AC : A 또는 C
  • CAP와 ACA : CA
  • CAP와 ACAY : CA
  • CAP와 ACAYK : CA
  • CAP와 ACAYKP : CAP

B \ A	0	A	C	A	Y	K	P
0	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
A
K

 

⑤ @dp[4][x]@ (0 ≤ @x@ ≤ 6)의 경우

• 문자열 @B@의 @{ CAPC }@와 문자열 @A@의 @{ A, AC, ACA, ACAY, ACAYK, ACAYKP }@의 LCS를 구하면 다음과 같다.
  • CAPC와 A : A
  • CAPC와 AC : AC
  • CAPC와 ACA : CA
  • CAPC와 ACAY : CA
  • CAPC와 ACAYK : CA
  • CAPC와 ACAYKP : CAP

B \ A	0	A	C	A	Y	K	P
0	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
K

 

⑥ @dp[5][x]@ (0 ≤ @x@ ≤ 6)의 경우

• 문자열 @B@의 @{ CAPCA }@와 문자열 @A@의 @{ A, AC, ACA, ACAY, ACAYK, ACAYKP }@의 LCS를 구하면 다음과 같다.
  • CAPCA와 A : A
  • CAPCA와 AC : AC
  • CAPCA와 ACA : ACA
  • CAPCA와 ACAY : ACA
  • CAPCA와 ACAYK : ACA
  • CAPCA와 ACAYKP : CAP 또는 ACA

B \ A	0	A	C	A	Y	K	P
0	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

 

⑦ @dp[6][x]@ (0 ≤ @x@ ≤ 6)의 경우

• 문자열 @B@의 @{ CAPCAK }@와 문자열 @A@의 @{ A, AC, ACA, ACAY, ACAYK, ACAYKP }@의 LCS를 구하면 다음과 같다.
  • CAPCAK와 A : A
  • CAPCAK와 AC : AC
  • CAPCAK와 ACA : ACA
  • CAPCAK와 ACAY : ACA
  • CAPCAK와 ACAYK : ACAK
  • CAPCAK와 ACAYKP : ACAK

B \ A	0	A	C	A	Y	K	P
0	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

 

---

 

규칙 발견하기

• 위의 과정을 통해 다음의 2가지 규칙을 발견할 수 있다.

 

① 해당 칸의 가로 축과 세로 축의 문자가 같을 경우

• 해당 칸의 왼쪽 대각선 값에 1을 더해준 값으로 업데이트 해준다.

B \ A	0	A	C	A	Y	K	P
0	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

• 이것을 코드로 표현하면 다음과 같다.

if (a[i - 1] == b[j - 1]) {
    dp[i][j] = dp[i - 1][j - 1] + 1;    // 왼쪽 대각선에 있는 값 + 1로 업데이트
}

 

② 해당 칸의 가로 축과 세로 축의 문자가 다를 경우

• 해당 칸의 왼쪽과 위의 값 중에서 큰 값으로 업데이트 해준다.

B \ A	0	A	C	A	Y	K	P
0	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

•  이것을 코드로 표현하면 다음과 같다.

else {    // if (a[i - 1] != b[j - 1]) {
    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);    // 해당 칸의 왼쪽 값에 있는 값과 위에 있는 값 중 큰 값으로 업데이트
}

 

• 따라서 문제 해결을 위한 코드는 다음과 같다.

int Solution(string a, string b) {
    int lenA, lenB;
    
    lenA = a.size();
    lenB = b.size();

    for (int i = 1; i <= lenA; i++) {
        for (int j = 1; j <= lenB; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[lenA][lenB];
}

 

코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

string A, B;
int dp[1001][1001];

void Input() {
    cin >> A >> B;
}

int Solution(string a, string b) {
    int lenA, lenB;
    
    lenA = a.size();
    lenB = b.size();

    for (int i = 1; i <= lenA; i++) {
        for (int j = 1; j <= lenB; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[lenA][lenB];
}

void Output() {
    cout << Solution(A, B) << '\n';
}

void Solve() {
    Input();
    Output();
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Solve();

    return 0;
}

 

채점 결과

 

참고

• [단계별로 풀어보기] > [동적 계획법 1]
• 골드V

 

최장 공통 부분 수열(LCS; Longest Common Subsequence)

개념

• 동적 계획법(DP)으로 풀 수 있는 유명한 알고리즘 문제
• 주어진 여러 개의 수열 모두의 부분 수열이 되는 수열들 중에 가장 긴 것을 찾는 문제
• 컴퓨터 과학에서 고전으로 통하는 문제이며, 생물 정보학에서도 많이 응용되고 있는 문제이다.
• 연속되어 있는 공통 문자열을 찾는 최장 공통 부분 문자열(Longest Common Substring) 문제와 혼동해서는 안 된다.

 

점화식

$$LCS(X_{i}, Y_{i}) = \begin{cases} 0 & \text{if i = 0 or j = 0} \\ LCS(X_{i - 1}, Y_{j - 1}) + 1 & \text{if } x_{i} = y_{j} \\ \text{longest}(LCS(X_{i}, Y_{j - 1}), LCS(X_{i - 1}, Y_{j})) & \text{if } x_{i} \ne y_{j} \end{cases}$$

 

알고리즘($O(n \times m)$)

int LCS(string a, string b) {
    int n, m;
    
    n = a.size();
    m = b.size();

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (a[i - 1] == b[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            }
            else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    return dp[n][m];
}

 

참고 사이트

• https://ko.wikipedia.org/wiki/%EC%B5%9C%EC%9E%A5_%EA%B3%B5%ED%86%B5_%EB%B6%80%EB%B6%84_%EC%88%98%EC%97%B4

최장 공통 부분 수열 - 위키백과, 우리 모두의 백과사전