최장 공통 부분 순열

두개의 배열이 제공되었을때 빠르게 공통 부분 순열을 찾을때 사용해 볼 코드이다.

최장 공통 부분 순열이란

[1,2,3]과 [2,3,4] 이 두 배열이 존재할때 가장 긴 부분 순열은 [2,3]으로 이를 최장공통부분순열 이라 한다.

연속된 부분순열을 찾을때

[1,2,3]의 부분순열로 1,2,3,12,23,123만 허용할때 점화식이다.
메모이제이션 되는 배열은 2차원 배열로 두 배열의 길이들로 행과 열을 지정한다.
- N배열은 길이n, M배열은 길이m이라 하자.
- 이차원 배열 dp[n][m]으로 선언
dp[n][m]의 값은 N이 n일때, M이 m인 위치일때 연속으로 같은 부분순열의 길이를 저장한다.
원리는 N과 M이 같은 경우 각 두위치-1인 위치의 값을 +1하여 LCS를 갱신하는 원리.
- N의 n위치와 M의 m위치가 같다면 n-1과m-1의 LCS를 +1을 하면 된다.
점화식은 아래와 같다.

- 두 n과m의 값이 같은 경우 dp[n][m] = dp[n-1][m-1]+1
- 두 n과m이 다른경우 dp[n][m] = 0

점화식에 따라 dp를 채우고, 최대값을 출력하면 연속된 부분순열에서의 LCS의 길이를 알 수 있다.

for(int n=0;n<N;n++) {
    for(int m=0;m<M;m++) {
        if(Ns[n]==Ms[m]) { // 두 값이 같은 경우
            if(n-1<0) {
                dp[n][m]=1;
                continue;
            }
            if(m-1<0) {
                dp[n][m]=1;
                continue;
            }
            dp[n][m]= dp[n-1][m-1]+1;
        }
    }
}

비 연속 부분 순열을 찾을때

[1,2,3]의 부분순열로 1,2,3,12,23,123과, 13도 허용할때 점화식이다.
준비과정은 위의 연속 부분순열과 같지만, 점화식에서 추가 조건이 들어간다.
연속부분순열과 다른점은 n-1,m-1만 사용하기 보다, n-1,m과 n,m-1의 값을 계속 끌어서 최대인 값으로 갱신한다.
점화식은 아래와 같다.

- 두 n과m의 값이 같은 경우 dp[n][m] = dp[n-1][m-1]+1
- 두 n과m이 다른경우 dp[n][m] = max(dp[n-1][m],dp[n][m-1])

for(int n=0;n<N;n++) {
    for(int m=0;m<M;m++) {
        if(Ns[n]==Ms[m]) { // 두 값이 같은 경우
            if(n-1<0) {
                dp[n][m]=1;
                continue;
            }
            if(m-1<0) {
                dp[n][m]=1;
                continue;
            }
            dp[n][m]= dp[n-1][m-1]+1;
        }else{
            if(n-1<0&&m-1<0){
                dp[n][m] = 0;
                continue;
            }
            if(n-1<0) {
                dp[n][m]=dp[n][m-1];
                continue;
            }
            if(m-1<0) {
                dp[n][m]=dp[n-1][m];
                continue;
            }

            dp[n][m]= Math.max(dp[n][m-1],dp[n-1][m]);
        }
    }
}