[알고리즘 이론] LCS(Longest Increasing Subsequence) 최장 증가 부분 수열

이론

1. LCS이란?

 LCS 개념을 이해하기 전에 기본적으로 DP(동적 계획법)또는 이분탐색을 알아야 된다. DP 에 관련 내용은 아래 사이트에 참조하면된다.

https://jih3508.tistory.com/89

[알고리즘 이론] 동적계획법(Dynamic Programming, DP)

 LCS는 2개의 문자열에서 비교해서 공통으로 길이가 가장 큰 열을 말한다. 예시로 ABCDEFG와 BDFGEH에서 가장 길이가 긴 수열은 BDFG가 될 수가 있다. 두 개의 문자열을 비교해서 처음부터 끝까지 수열로 공통으로 되어 있는 것을 구하면된다. 구현도 어떻게 보면 하기가 쉬울거 같은데 기본적으로 브루드포스로 구할 경우 두 개의 문자열의 길이가 N, M이라고 할때 시간 복잡도는 O(N^M)이 될 수가 있다. 모든 경우의 수와 조합을 구하여야 하기때문에 처리하는 시간이 길어서 이 문제를 해결하기 위해서 동적계획법(DP)알고리즘 방법으로 설명 할 것이다.

 

2. DP로 길이 구현 하는 방법

 LCS에 대한 기본적인 개념을 설명 했는데 이번에는 구현 하는 방법을 설명 하겠다. 일단 두 문자열을 길이가 N, M이라고 했을때 먼제 2차원 배열을 N + 1, M + 1로 먼저 크기로 만들고 시작해야 한다.  그 이유는 아래 그림 처럼  문자 하나당 다른 문자열을 비교하면서 진행 해야 되기 때문이다.

 

과정은 아래를 보면 된다.

1. 배열/ 리스트 [N + 1][M + 1]로 먼저 선언하고 각 행의 0번째 인덱스, 0번째 행 0으로 초기화 한다.
2. 2중 반복문을 돌린고 아래 조건에 따라 연산한다.(1행, 1열 부터 시작 한다., 좌표를 (x, y)로 한다.)
   1. 같을 경우 [x-1][y-1] + 1 해준다.
   2. 다를 경우 [x-1][y], [x][y-1]중 큰 값으로 한다.
3.  [x][y]를 출력하면 가장 긴 수열이 나온다.

아래 예시를 보면서 설명하겠다.

 

1.   2차원 배열을 만들고 0번 행과 0번째 인덱스 0으로 초기화 한다.

2.   B에서 한 문자씩 비교한다.

 2번째에서 같은 문자이기 때문에 (0, 1)값을 더한다. 그 다음 문자열 탐색하면 같은 수가 없기때문에 1로 채운다.

3.   D에서 한 문자씩 비교한다.

 두번째 열에서 (2, 1)과 (1, 2)중 큰 값을 넣으면 된다.

 4번째에서 같은 문자가 있어서 (1, 3)에서 1을 더하면된다. 그 다음에는 탐색에서 같은 문자가 없기 때문에 2로 기입한다.

4.   F에서 한 문자씩 비교한다.

 

 두번째 열에서 (3, 1)과 (2, 2)중 큰 값을 넣으면 된다.

 4 번째에서 (3, 3), (2, 4)중 큰 값을 넣으면 2가 들어간다.

 6번째에서 같은 문자가 있어서 (2, 5)에서 1을 더하면된다. 그 다음에는 탐색에서 같은 문자가 없기 때문에 3으로 기입한다.

5.  G에서 한 문자씩 비교한다.

 두번째 열에서 (4, 1)과 (3, 2)중 큰 값을 넣으면 된다.

 4 번째에서 (4, 3), (3, 4)중 큰 값을 넣으면 2가 들어간다.

 6 번째에서 (4, 5), (3, 6)중 큰 값을 넣으면 3이 들어간다.

 7번째에서 같은 문자가 있어서 (2, 5)에서 1을 더하면된다.

 

6.  E에서 한 문자씩 비교한다.

 두번째 열에서 (5, 1)과 (4, 2)중 큰 값을 넣으면 된다.

 4 번째에서 (5, 3), (4, 4)중 큰 값을 넣으면 2가 들어간다.

 5 번째에서 같은 문자라서 (4, 4)에서 1을 더하면된다.

 7번째에서 (5,6), (4, 7)중 큰 값을 넣으면 4가 들어간다.

 

7.  H에서 한 문자씩 비교한다.

 H에서 같은 문자가 없기 때문에 위에거 그대로 옮긴다. 그 다음에 (6, 7)이 가장 큰 값이 된다. 그럼 4가 된다.

Code

 위에 내용을 코드로 작성하면 아래처럼 나온다.

Python

dp = [[0] * (len(y) + 1) for _ in range(len(x) + 1)]

for i in range(1, len(x) + 1):
    for j in range(1, len(y) + 1):
        if x[i-1] == y[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

Java

int xLegth = X.length;
int yLegth = Y.length;

int[][] dp =  new int[xLegth + 1][yLegth + 1];
Arrays.stream(dp).forEach(array -> Arrays.setAll(array, x -> 0));

for(int i = 1; i <= xLegth; i++) {
    for(int j = 1; j <= yLegth; j++) {
        if(X[i - 1] == Y[j - 1]) {
            dp[i][j] = dp[i-1][j-1] + 1;
        }else {
            dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
        }
    }
}

 

 

문자열 길이는 구했지만 가장 긴 문자열을 구해야 한다. 구하는 방법은 추후에 올리겠다.

시간 복잡도

 2차원 배열을 탐색하면 시간 복잡도는 O(N ^ 2)이 된다.