[Algorithm] LCS (Longest Common Subsequence, 최장 공통 부분 수열)

❓ LCS 란?

---

여러 개의 수열 모두의 부분 수열이 되는 수열들 중에 가장 긴 것

 

 

❓ LCS 

---

예를 들어 ABCDE와 ACBDE의 LCS를 찾는다고 가정해 보자

 

현재 위치가 (x, y)이고

1) 문자가 같다면 (x-1, y-1) +1을 저장한다.

2) 문자가 같지 않다면 (x-1, y)와 (x, y-1) 값 중에서 큰 값으로 저장한다.

 

배열의 마지막 값이 LCS의 길이가 된다.

LCS를 찾기 위해서는 배열의 가장 오른쪽 아래부터 탐색을 시작한다. 

if) 현재 값과 위의 값이 같다면 위로 이동

else if) 현재 값과 왼쪽 값이 같다면 왼쪽으로 이동

else) 현재 값을 LCS값으로 저장 후 왼쪽 위 대각선으로 이동

 

❓ LCS 코드

---

public class Main { // LCS

	public static void main(String[] args) {

		for (int i = 0; i < b.length(); i++) {
			for (int j = 0; j < a.length(); j++) {
				if (a.charAt(j) == b.charAt(i)) {
					arr[j][i] = arr[j - 1][i - 1] + 1;
				} else {
					arr[j][i] = Math.max(arr[j - 1][i], arr[j][i - 1]);
				}
			}
		}
	}
}