ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • LCS
    알고리즘 2020. 4. 10. 00:10

    들어가기에 앞서


    부분 문자열?

    ①Substring ? 연속된 부분 문자열

    ②Subsequence ? 연속되지 않은 부분 문자열


    예시로 ACDEF와 ABKEF가 있다고 하자.

    substring = EF

         ACDEF

         ABKEF


    subsequece = AEF

        ACDEF

        ABKEF



    LCS (Longest Common Subsequence, 최장 공통 부분 문자열)

    • 개념 : 두개의 문자열을 비교해 공통 부분 수열을 구하는 알고리즘
    • 사용처 : 염기 서열 유사성 분석 or 음파 담어 검색 등
    • 구현 방법 : DP(동적분석법)으로 특정 범위까지 memoization하고, 다음 범위를 구할때 이전에 저장한 값을 이용해 품.

    예시로 ACAYKP, CAPCAK 문자열의 LCS를 구해보자.

    참고
    * 테이블의 첫번째 열과 첫번째 행은 0으로 채워둔다 (계산의 용이성을 위해)
    * 하나의 문자열을 기준 문자열로 잡고, 다른 문자열을 비교 문자열로 둔다.

    지금은 ACAYKP를 기준 문자열, CAPCAK 비교 문자열로 사용해 보겠다.

    일단 첫번째로 CAPCAK 단어 중 첫번째 단어인 C만 이용해서 ACAYKP와 비교해보겠다.


    ((테이블 안에 들은 수는 공통 부분 문자열의 개수이다.))


    그다음 CAPCAK 중 CA를 비교해보겠다.


    이런식으로 테이블을 작성하다 보면 규칙을 발견할 수 있다.


    (행은 이전 행의 값을 기반으로 계산된다는 점.)

    현재 테이블에 들어갈 수는 

    비교문자가 같을 때 -> 이전까지의 LCS 길이 + 1

                                  즉, 왼쪽 대각선 값 + 1


    비교문자가 다를 때 -> 이전까지의 LCS 길이

                                  즉, 왼쪽과 위쪽 중 큰 값


    규칙을 통해 만들어진 최종적인 테이블을 아래와 같다.



    결과적으로 LCS의 길이를 구할 수 있다. = 4



    그렇다면 길이가 아닌 LCS의 해당하는 부분 수열을 구하는 방법은?


    가장 오른쪽 아래부터 시작한다.

    1. 자신과 같은 숫자가 있는 곳으로 이동한다.

    2. 왼쪽과 위쪽에 같은 수가 없다면, 대각선 방향이 현재 값 -1인지 보고 그 수로 이동한다.

       (비교 문자가 같을때 왼쪽 대각선에서 +1 했으니, 이제는 반대로 가는 것이다.)


    이를 계속 반복하다 0을 만나면 그만한다.



    ACAYKP, CAPCAK 문자열의 LCS는 ACAK 이다.




    실제  LCS 구현 코드는 아래에 있다


    [백준] 9252 LCS2 문제의 정답


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    #include <stdio.h>
    #include <string>
    #include <algorithm>
    #include <iostream>
    #include <vector>
    using namespace std;
     
    string f, s;
    int dp[1001][1001];
     
    int main() {
        cin >> f >> s;
        // 첫번째행과 첫번째열이 0이여야하니깐 계산상 편의를 위해 문자열 앞에 의미없는 걸 붙여둔다.
        f.insert(f.begin(), '0'); 
        s.insert(s.begin(), '0');
        //1. 테이블 채우기
        for (int i = 1; i < f.length(); i++) {
            for (int j = 1; j < s.length(); j++) {
                if (f[i] == s[j]) { // 문자가 같다면, 왼쪽 대각선 값 + 1
                    dp[i][j] = dp[i - 1][j - 1+ 1;
                }
                else {//문자가 다르면, 왼쪽과 위쪽 값 중 큰 값
                    dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        printf("%d\n", dp[f.length()-1][s.length()-1]);
        vector <char> temp;
        //2. 문자열 구하기
        int i = f.length() - 1;
        int j = s.length() - 1;
        while (dp[i][j] != 0) {
            //같은 숫자있다면 이동
            if (dp[i][j] == dp[i][j - 1]) {
                j -= 1;
            }
            else if (dp[i][j] == dp[i - 1][j]) {
                i -= 1;
            }
            else if (dp[i][j] == dp[i - 1][j - 1+ 1) {
                temp.insert(temp.begin(),f[i]); //거꾸로 삽입되지 않기 위해, 처음에 계속 삽입
                i -= 1;
                j -= 1;
     
            }
        }
        for (int i = 0; i < temp.size(); i++) {
            printf("%c", temp[i]);
        }
     
        return 0;
    }
    cs


    '알고리즘' 카테고리의 다른 글

    에라토스테네스의 체  (0) 2020.07.16
    MST  (0) 2020.05.16
    brute force  (0) 2020.03.26
    Lazy propagation  (0) 2020.03.17
    Segment Tree  (0) 2020.03.17

    댓글

Designed by Tistory.