[알고리즘] 최장 공통 부분 수열(LCS) - 코딩밥상

최장 공통 부분 수열(Longest Common Subsequence)이란?

 '공통 부분 수열'은 말 그대로 두개 이상의 수열 사이에 공통으로 존재하는 부분 수열을 말합니다. 따라서 '최장 공통 부분 수열(LCS)'은 여러개의 공통 부분 수열 중 가장 긴 부분 수열을 말합니다. 이 LCS 알고리즘은 두 데이터를 비교할 때 아주 유용합니다. 

 

 LCS 문제를 동적 계획법으로 풀기 전에 이 문제가 최적 부분 구조로 이루어져 있는지 먼저 확인해야겠네요. 

X = {x1,x2,x3,...,xi} 와 Y = {y1,y2,y3,...,yj}인 두 문자열이 있다고 하고, 이 두 문자열을 매개 변수로 받아 이들 사이에서 나올 수 있는 LCS의 '길이'를 구하는 함수를 LCS( )라고 하면, 다음과 같은 점화식을 세울 수 있습니다.

X 와 Y가 모두 길이가 0이면 0

X 와 Y가 끝의 문자가 같으면 기존 값에 +1

X 와 Y가 모두 길이가 0이 아니고 끝의 문자가 다르면 각 전 단계의 리턴값이 더 큰 값 

typedef struct structLCSTable{
    int **Data;
}LCSTable;

int LCS(char* X, char* Y, int i, int j, LCSTable* Table){
    if(i==0 || j==0){
        Table->Data[i][j] = 0;
        return Table->Data[i][j];
    }
    else if(X[i-1] == Y[j-1]){
        Table->Data[i][j] = LCS(X, Y, i-1, j-1, Table) + 1;
        return Table->Data[i][j];
    }
    else{
        int A = LCS(X, Y, i-1, j, Table);
        int B = LCS(X, Y, i, j-1, Table);
        
        if(A>B) Table->Data[i][j] = A;
        else Table->Data[i][j] = B;
        
        return Table->Data[i][j];
    }
}

 하지만 위 코드는 점화식을 그대로 구현했을 뿐입니다. 따라서 재귀문을 호출하는 분기문 블록을 두 군데 갖고 있기때문에 수행 시간은 지수적으로 증가하게됩니다. O(2^(n+m))

---

동적 계획법(DP) 기반으로 LCS 구현하기

위에서 점화식도 구했겠다 이제 이 문제는 최적 부분 구조로 되어있음을 알았기 때문에 먼저 구한 점화식을 이용하여 동적 계획법(DP)으로 이 문제를 해결 해보겠습니다.

 

 LCS문제에서는 2차원 테이블에서 가장 오른쪽 밑이 구하고자 하는 값이 되겠습니다.

i 또는 j가 0일 경우엔 테이블 값은 무조건 0이겠네요.

그 다음부터는 테이블의 1번 행과 1번 열부터 LCS 길이를 구해 채워나가면 됩니다.

 점화식을 이용하여

X[i]와 Y[j]가 같은 경우 => Table[i, j]에 Table[i-1, j-1]+1 을 대입하면 되고

i,j가 모두 0보다 크고 X[i]와 Y[j]가 다른 경우 => Table[i-1, j]나 Table[i, j-1]중 큰 값을 Table[i,j]에 대입하면 됩니다. 

 

예제로 X = "GOOD MORNING.", Y = "GUTEN MORGEN." 를 DP기반 LCS테이블을 만들어 보면

 



다음과 같은 테이블이 완성이 됩니다.

점화식의 두 번째에 해당하는 경우 왼쪽 대각선의 테이블 값에 +1 해준 값이 대입 되고

점화식의 세 번째에 해당하는 경우 위쪽이나 왼쪽 테이블 값 중 더 큰 값이 대입이 됩니다.

 

이렇게 테이블 왼쪽 위부터 오른쪽 아래까지 훑으면서 계산해나가면 X의 길이를 m, Y의 길이를 n이라고 했을 때,

Table[m,n]을 구하는데 O(nm)의 수행시간이 됩니다.

위에서 단순히 점화식을 구현한 것에 비해 엄청난 성능 향상입니다.

 

 

 

 

 

 

이를 코드로 구현해봅시다.

typedef struct structLCSTable{
    int **Data;
}LCSTable;

int LCS(char* X, char* Y, int i, int j, LCSTable* Table){
    int m=0;
    int n=0;
    
    for(m=0; m<=i; m++) Table->Data[m][0] = 0;  //i 또는 j가 0일 때 테이블 값을 0으로 초기화
    for(n=0; n<=j; n++) Table->Data[0][n] = 0;
    
    for(m=1; m<=i; m++){
        for(n=1; n<=j; n++){
            if(X[m-1] == Y[n-1]){   //점화식의 두번째 경우
                Table->Data[m][n] = Table->Data[m-1][n-1]+1;
            }
            else{
                if(Table->Data[m][n-1] >= Table->Data[m-1][n])	//점화식의 세번째 경우
                    Table->Data[m][n] = Table->Data[m][n-1];
                else
                    Table->Data[m][n] = Table->Data[n-1][m];
            }
        }
    }
    return Table->Data[i][j];
}

 여기까지 한 과정은 테이블을 만들어 LCS의 길이를 구하는 과정이었습니다. 테이블을 만드는 과정에서 DP를 사용하여 엄청난 성능 개선을 이루어냈습니다. 

 

하지만 구하고자 하는 것은 LCS의 길이가 아닌 LCS 자체의 문자열이었습니다. 사실 테이블을 만드는데 DP를 사용하고 테이블의 오른쪽 아래에서 왼쪽 위로 올라가면서 각 LCS 요소를 추적하여 LCS 문자열을 얻는 작업은 테이블을 이용한 단순 구현입니다.

이 LCS 추적 알고리즘은 다음과 같습니다.

1. 오른쪽 아래 모서리를 요소 시작 셀로 지정하고, LCS의 요소를 담기 위한 리스트를 하나 준비합니다.
2. 현재 위치한 셀의 값이 왼쪽,위,왼쪽 위(왼쪽 대각선)보다 크면 현재 셀의 값을 리스트의 헤드에 삽입하고 왼쪽 위로 이동합니다.
3. 현재 셀의 값과 왼쪽 셀의 값이 같고 위쪽 셀의 값보다 큰 경우 왼쪽으로 이동합니다.
4. 위 단계에 모두 해당하지 않으면 위쪽으로 이동합니다.

 왼쪽 위 모서리에 도착 할 때까지 각 다음 4단계를 우선값으로 수행합니다.

위에서 완성한 테이블에 대한 LCS추적

void LCS_TraceBack(char* X, char* Y, int m, int n, LCSTable* Table, char* LCS){
    if(m==0 || n==0) return;
    
    if(Table->Data[m][n] > Table->Data[m][n-1]  //현재 셀이 왼,위,왼위 보다 큰 경우(왼쪽 위로 이동)
       && Table->Data[m][n] > Table->Data[m-1][n]
       && Table->Data[m][n] > Table->Data[m-1][n-1]){
        char TempLCS[100];
        strcpy(TempLCS, LCS);
        
        LCS_TraceBack(X, Y, m-1, n-1, Table, LCS);
    }
    else if(Table->Data[m][n] > Table->Data[m-1][n] //현재 셀이 위보다 크고 왼쪽과 같은 경우(왼쪽으로 이동)
            && Table->Data[m][n] == Table->Data[m][n-1]){
        LCS_TraceBack(X, Y, m, n-1, Table, LCS);
    }
    else{   //위 두 경우에 모두 해당하지 않을 때(위로 이동)
        LCS_TraceBack(X, Y, m-1, n, Table, LCS);
    }
}