백준 9251번 LCS 문제 풀이 (C++)

백준 9251번 LCS 문제 풀이

 

http://boj.kr/9251

9251번: LCS

 

<2차원 배열 cache를 이용해 푸는 방법>

 

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
#include <cstring>
#include <set>
#include <cmath>
using namespace std;
stringstream ss;
 
char a[1001], b[1001];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> a >> b;
    int a_l = strlen(a);
    int b_l = strlen(b);
 
    int **dp = new int*[a_l+1];
    for (int i = 0; i < a_l+1; ++i) {
        dp[i] = new int[b_l+1]();
    }
 
    for (int r = 1; r <= a_l; ++r) {
        for (int c = 1; c <= b_l; ++c) {
            if (a[r-1] == b[c-1]) {
                dp[r][c] = dp[r-1][c-1] + 1;
            }
            else {
                dp[r][c] = max(dp[r][c], dp[r-1][c]);
                dp[r][c] = max(dp[r][c], dp[r][c-1]);
            }
        }
    }
    cout << dp[a_l][b_l];
 
    for (int i = 0; i < a_l+1; ++i) {
        delete []dp[i];
    }
 
    cout << ss.str();
    return 0;
}
 

풀이 과정

 

문자열 a, b를 입력받은 후, 두 문자열의 길이를 구해 각각을 int형 변수 a_i, b_i에 저장한다.

메모이제이션을 수행할 배열의 크기가 최대 1000*1000이므로, stack overflow exception을 방지하기 위하여 동적으로 메모리를 할당해준다.

 

C++는 가비지 컬렉터가 없는 언어이다. 사용이 끝났을 때 할당한 메모리를 바로 회수할 수 있도록 자원을 동적 할당해주는 new 명령어를 작성함과 동시에 습관적으로 delete 명령어를 작성하도록 한다.

 

2차원 메모이제이션 배열의 범위 체크를 생략하기 위해서 배열의 row, column 첫 부분에 각각 한 줄씩 추가해주었다.

그 때문에 r=1 부터 r<=a_i, 그리고 c=1부터 c<=b_i까지 dp를 탐색하도록 코드가 짜여있다.

 

다음은 메모이제이션을 위한 배열의 정의를 풀어 설명한 것이다.

 

dp[r][c] = a배열의 r-1번째 index, b배열의 c-1번째 index까지 고려했을 때의 LCS (최장 공통 부분 수열)

 

 

그리고 다음은 그 배열을 구현하기 위한 구체적인 방법을 설명한 것이다.

 

dp[r][c]= case 1) 현재 관찰 중인 두 문자가 같을 경우 바로 그 직전까지의 문자쌍(r-2번째, c-2번째)에 1을 더한 것. dp[r-1][c-1] = dp[r-2][c-2] + 1   현재 관찰 중인 문자쌍(r-1, c-1)의 이전 영역 중 최대한의 LCS를 담고 있는 영역은 dp[r-2][c-2]이기 때문. dp[r-2][c-1] 혹은 dp[r-1][c-2]는 dp[r-1][c-1]과 연관성이 있으므로 채택할 수 없다.     case 2) 현재 관찰 중인 두 문자가 같지 않을 경우 이차원 dp배열의 바로 위 값과 바로 왼쪽 값 중 더 큰 값을 채택한다. dp[r-1][c-1] = max(dp[r-2][c-1], dp[r-1][c-2])   "r-1번째 index와 c-1번째 index까지 고려한 LCS의 길이"는 "r-2번째 index와 c-1번째 index까지 고려한 LCS의 길이" 보다 크고, "r-1번째 index와 c-2번째 index까지 고려한 LCS의 길이"보다 반드시 크기 때문이다.

 

 

 

---

 

 

<1차원 배열 cache를 이용해 푸는 방법>

 

#include <iostream>
#include <sstream>
#include <vector>
#include <algorithm>
#include <string>
#include <utility>
#include <cstring>
#include <set>
#include <cmath>
using namespace std;
stringstream ss;
 
char a[1001], b[1001];
int dp[1000];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> a >> b;
    int a_l = strlen(a);
    int b_l = strlen(b);
    int mx = 0;
 
    for (int i = 0; i < a_l; ++i) {
        int cur = 0;
        for (int j = 0; j < b_l; ++j) {
            if (dp[j] > cur) {
                cur = dp[j];
            }
            else if (a[i] == b[j]) {
                dp[j] = cur+1;
                mx = max(mx, dp[j]);
            }
        }
    }
    cout << mx << '\n';
    cout << ss.str();
    return 0;
}
 

풀이 과정

 

마찬가지로 a_l, b_l을 정해주고, 메모이제이션을 위한 1차원 배열을 선언한다.

배열의 크기가 작으므로 정적으로 메모리를 할당해주었다. 특별히 다른 함수를 통해 호출할 용도가 아니므로 automatic allocation이 더 적절할 수 있다.

 

dp[j] = 2번째 문자열의 j번째 index의 원소로 끝나는 LCS (최대 공통 부분 수열)

 

a배열의 i번째 index의 원소와 b배열의 j번째 index의 원소가 같을 때에만 dp의 업데이트가 이루어진다.

dp는 하나의 배열이고, 첫 번째 문자열의 문자를 정하는데에 사용되는 i값과 두 번째 문자열의 문자를 정하는 j값이 증가함에 따라 계속적으로 변화한다.

 

위에 쓴 정의를 보면 알 수 있듯이, j번째 index의 원소가 1번째 문자열에 속하지 않을 경우, dp[j]의 값은 정해지지 않을 수도 있다. 이 때는 처음 dp의 값을 0으로 초기화했으므로 0으로 정해진다.

 

int형 변수인 cur은 dp의 왼쪽부터 거쳐온 값 중 최댓값을 저장하는데, 계속 값을 수집하다가 a[i] == b[j]인 케이스에 도달하면 cur+1값을 dp[j]에 저장함으로서, dp[j-1]까지의 최대값 + 1이 dp[j]에 저장되는 역할을 한다.

 

이 때 중요한건 dp[j] > cur 조건문과 a[i] == b[j] 조건문은 독립적으로 적용되어야 한다는 것이다.

전자의 조건문에서 cur값을 업데이트 한 후에 바로 후자의 조건문으로 들어가 cur값을 이용하여 dp를 업데이트하게 되면 의도한 결과와 다르게 코드가 동작한다.

또한 두 조건문의 순서도 중요하다. 두 가지 조건을 다 만족하는 케이스가 발생했을 때, 후자의 조건문을 먼저 수행하게 될 때도 마찬가지로 잘못된 코드가 된다. 이는 중복된 문자열을 체크할 때 발생하는 오류이다.

 

앞서 말한 조건문 두 개의 위치를 서로 바꾸고 다음 케이스를 테스트해보면 이해가 쉬울 것이다.

 

AA ABA