LCS (최장 공통 부분 수열)

코테 보다가 나온 것이기에 정리한다...

 

LCS (Longest Common Subsequence)는 주어진 여러 개의 수열 중에서 모두의 부분수열이 되는 수열들 중 가장 긴 것을 찾는 것이다. 

예시를 보자면,

ACAYKP의 부분수열은 

{A}, {C}, {A}, {Y}, {K}, {P}, {A, C}, {A, A}, {A, Y}, ... {A, C, A, Y, K, P} 이고, 

 

CAPCAK의 부분수열은 

{C}, {A}, {P}, {C}, {A}, {K}, {C, A}, {C, P}, {C, C}, ... {C, A, P, C, A, K}이 있는데

 

각각의 부분수열 중에서 서로 같은 부분수열이 있을 것이다.

그중 가장 긴 것을 찾으면 되는데 위의 예시의 답은 길이가 4인 {A, C, A, K} 이다.

---

대표적인 문제는 아래와 같다. 

https://www.acmicpc.net/problem/9251

9251번: LCS

 

 

 

 

🕹️ LCS (최장 공통 부분 수열) 알고리즘 과정 

백트래킹을 사용해서 완전탐색을 해도 되지만, 주어진 수열이 길면 시간초과가 발생할 수도 있기 때문에

DP(동적계획법)로 메모이제이션을 사용하여 Top-Down 또는 Bottom-Up으로 구현하면 된다 ! 

 

부분수열 같은 경우 순서가 지켜지기 때문에 각 문자열들의 문자들을 비교하며 서로 같으면 1씩 증가시켜 누적합을 구하면 된다. 

---

백준 문제의 예시를 확인해보자 !

🔹 최장 공통 부분 수열의 길이 

s1 = ACAYKP

s2 = CAPCAK 라고 했을 때, s1을 기준으로 s2와 비교한 결과를 표로 나타내면 아래와 같다. 

 

s1의 'A'와 s2의 문자열 하나하나 증가시키며 비교한 것이다. 

[C, A]는 s1의 'A' 와 s2의 'C'를 비교한 것이고, [A, A]는 s1의 'A'와 s2의 'CA'를 비교하여 공통인 수열이 'A' 하나이기 때문에 1을 적어주었다. 

[K, A]는 s1의 'A'와 s2의 'CAPCAK'를 비교하여 공통인 수열이 이전과 마찬가지로 'A' 하나이기에 1이 된 것이다. 

 

 

표를 다 채워보면 아래와 같다. 

 

여기서도 하나 예를 들어보면, 5번째 열과 5번째 행에 위치하는 [A, K] 같은 경우 s1의 'ACAYK'와 s2의 'CAPCA'를 비교한다.

공통인 수열이 'ACA'이기 때문에 3의 값을 가지게 된다. 

---

표를 채우다 보면 규칙을 찾을 수 있다 !

 

세로방향 즉, 열을 채우다보면 같은 원소가 존재하면 이전 열 (또는 행)에 +1한 값이 LCS 길이가 된다. 

(0, 1)은 'AC'와 'C'를 비교한 결과 값인 1이다. 

(1, 2)는 'ACA'와 'CA'를 비교한 결과 값인 2이다. 

➡️ {C}, {A, C}에서 'A'라는 공통 원소가 추가되면서 +1이 되어 2의 값을 얻게 되었다. 

 

👉 즉, x번째 원소와 y번째 원소가 같다면 (x-1, y-1)에 있는(대각선에 존재하는) 값 +1을 해주면 된다 ! 

같지 않다면 이전 행 또는 열의 원소 중 큰 값을 가져오면 된다 .!

 

 

 

 

---

✨ 24.03.11 내용 추가 !!

🔹 최장 공통 부분 수열 출력하기 

앞서 본 내용은 최장 공통 부분 수열의 길이를 알 수 있지만 그러한 부분 수열이 어떤 것인지는 표로 한 눈에 알아보기 힘들다.

최장 공통 부분 수열에 해당하는 부분 수열을 출력하는 방법을 알아보자. 

 

👉 위에서 구한 표를 이용하여 역방향으로 이동하면서 LCS의 글자를 역순으로 찾으면 된다.

방법은 다음과 같다.

1. 첫번째 행, 열까지 거슬러 올라간다.
2. X와 Y 현재의 글자가 같으면 (노랑색 동그라미) LCS에 포함시키고 위쪽 대각선 방향으로 거슬러 올라간다.
3. 같지 않으면 위쪽 또는 왼쪽 칸의 값 중 큰 값을 따라 이동한다. 

코드로 간단하게 나타내면 아래와 같다. 

while(i>0 && j>0){

	if(X[i-1]==Y[i-1]){
    	LCS[LCSLength] = X[i-1];
        // 위쪽 왼쪽으로 향하는 대각선으로 거슬러 올라감.
        i--;
        j--;
        LCSLength--;
    }
    
    else if(LCSTable[i-1][j] > LCSTable[i][j-1] i--;
    else j--;
}

 

 

 

 

 

👩‍💻 LCS 구현 코드 

public class Main{
	
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String str1 = br.readLine();
		int len1 = str1.length();
		String str2 = br.readLine();
		int len2 = str2.length();
		
		int[][] dp = new int[len1+1][len2+1];
		
		for(int i = 1; i <= len1; i++) {
			char C = str1.charAt(i-1);
			for(int j = 1; j <= len2; j++) {
            
            	// (i-1)과 (j-1) 번째 문자가 서로 같다면  
				if(C == str2.charAt(j-1)) {
                	// 대각선 위 (i-1, j-1)의 dp에 +1 한 값으로 갱신 
					dp[i][j] = dp[i-1][j-1] + 1;
				}
                
                else {
                	// 같지 않다면 이전 열(i-1)과 이전 행(j-1)의 값 중 큰 것으로 갱신  
					dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
				}
			}
		}
		System.out.println(dp[len1][len2]);
	}
}

 

 

 

참고

https://st-lab.tistory.com/139