LCS의 개념과 LCS 알고리즘 소개

서여·2025년 2월 27일
DPJavaLCSalgorithm

Algorithm

목록 보기
1/3
post-thumbnail

목차

  1. 최장 공통 부분 수열(LCS)이란?
  2. LCS 길이 구하기
  3. LCS 구하기
  4. 구현 코드
  5. 마무리

1. 최장 공통 부분 수열(LCS)이란?

최장 공통 부분 수열(Longest common subsequence, 이하 LCS)은 수열 A, B가 주어졌을 때, A, B에서 공통적으로 발견될 수 있는 가장 긴 수열을 의미합니다. 이때 수열은 '특정 순서로 숫자를 나열한 것'을 의미합니다. 따라서 대부분 LCS 문제들은 문자열로 수열을 입력을 받습니다.

LCS의 간단한 예시를 드리겠습니다.

예시 1)
수열 A: AC
수열 B: C

수열 A, B의 LCS는 C 입니다. A와 B 모두 C를 가지고 있기 때문입니다. 여기서 알 수 있는건 수열 A, B의 길이는 서로 달라도 된다는걸 알 수 있습니다.

그 다음 예시를 알아보겠습니다.

예시 2)
수열 A: ABC
수열 B: BAC

수열 A, B의 LCS는 BC 입니다. 이처럼 중간에 다른 수가 있더라도 순서만 지켜진다면 LCS라고 부를 수 있습니다.

마지막 예시입니다.

예시 3)
수열 A: ACDBE
수열 B: ABCDE

예시 3)
수열 A: ACDBE
수열 B: ABCDE

수열 A, B의 LCS는 ACE 이거나 ABE일 수 있습니다. 이처럼 LCS의 값은 하나가 아닐 수도 있습니다.

위의 세 예시를 곱씹다보면 LCS의 정의와 고려해야 할 점에 대해 알 수 있습니다.

2. LCS 길이 구하기

이제 본격적으로 LCS의 길이를 구해보겠습니다. 구하기에 앞서 길이를 구해야 하는 이유는 문제를 풀기 위해서... 입니다..^^ 이거 풀면 티어 많이 오릅니다. 다들 파이텡

사실 LCS는 유전자 서열 분석, 버전 관리 시스템, 텍스트 유사도 검사 등 다양한 분야에서 사용되고 있으니 알고 계시면 좋습니다.

LCS는 기본적으로 DP를 이용하여 해결할 수 있습니다. 백준 9252번 LCS 2 문제를 고민하고 오시면 더 와닿으실 것 같습니다.

LCS의 길이를 구하기 앞서, 임의의 메서드를 정의하겠습니다.

  • LCS(i, j) = A[1 ... i]와 B[1 ... j]의 LCS의 길이

LCS(i, j)의 값을 계산하기 위해 고려해야 할 점이 있습니다. 바로 A[i], B[j]의 값의 동일성 유무입니다.

A[i]와 B[j]의 값이 같을 때는 단순히 A[1 ... i - 1], B[1 ... j - 1] 까지의 수열에 A[i]와 B[j]가 추가된 것이므로, LCS(i-1, j-1)에 1을 더해주면 됩니다.

이때 다른 LCS()를 고려하지 않는 이유는 A[i]와 B[j]보다 작은 수열 중 가장 큰 LCS()의 값은 LCS(i - 1, j - 1) 하나 밖에 없기 때문입니다. LCS(i - 1, j)나 LCS(i, j - 1)의 값을 고려하게 된다면 상황이 중복으로 카운트 되어 정확한 값이 나오지 않습니다. (제가 이렇게 해서 틀렸습니다..)

다음은 A[i]와 B[j]의 값이 다를 때의 경우입니다. 이 경우에는 A[1 ... i]와 B[1 ... j - 1]의 LCS의 길이, A[1 ... i - 1]와 B[1 ... j]의 LCS의 길이 중 더 큰 값을 넣어야 합니다.

이유는 A[i]와 B[j]의 값이 같지 않기 때문에, 다른 곳에서 LCS의 길이를 가져와야 하는데, 가져올 명분이 있는 LCS()는 A[i] 혹은 B[i]를 포함하고 있는 수열이어야 합니다. 따라서 이를 만족하는 LCS()는 LCS(i, j-1), LCS(i-1, j) 이므로 이 두 값 중 최대값을 LCS(i, j)에 넣으면 됩니다.

지금까지 설명한걸 간단히 정리해보겠습니다.

LCS의 길이 점화식

  • LCS(0, 0) = 0
  • A[i] == B[j] → LCS(i, j) = LCS(i-1, j-1) + 1
  • A[i] != B[j] → LCS(i, j) = max(LCS(i-1, j), LCS(i, j-1))

3. LCS 구하기

LCS의 길이를 구했지만 아직 LCS를 구하진 못했습니다. LCS를 구하는 방법은 LCS(i, j)의 결과를 역추적 하는 것입니다. 백준 9252번의 예제를 가지고 설명하겠습니다.

백준 9252 예제)
수열 A: ACAYKP
수열 B: CAPCAK

아래는 예제의 LCS() 결과표입니다. - 표시는 수열의 길이가 0일때 입니다.

역추적은 LCS(A.length, B.length)부터 시작합니다. 역추적의 방식은 LCS의 길이를 구했던 경우처럼 A[i]와 B[j]의 동일성 유무로 나누어 추적할 수 있습니다.

A[i]와 B[j]의 값이 같다면 A[i]의 값을 저장하고, LCS(i-1, j-1)로 이동하면 됩니다.

A[i]와 B[j]의 값이 다르다면 LCS(i - 1, j)와 LCS(i, j - 1) 중 더 큰 값으로 이동하면 됩니다. 만약 두 값이 같다면 아무데나 가도 괜찮습니다.

LCS의 길이 점화식을 역으로 추적하는 것이기 때문에 복잡하게 생각하지 않으셔도 됩니다.

아래는 역추적의 경로입니다.

초록색은 A[i] != B[j] 일때, 빨간색은 A[i] == B[j] 일때 입니다.
그리고 회색은 초록색일때(A[i] != B[j] 일때) 더 작거나 선택받지 못한 값입니다.

역추적의 종료 조건은 i 또는 j가 0이 되었을 때 입니다.

지금까지 설명한 걸 간단히 정리해보겠습니다.

LCS 역추적 점화식

  • 시작 위치: lcs = ""(빈 문자열), LCS(A.length, B.length)
  • 종료 조건: i <= 0 || j <= 0
  • A[i] == B[j] → lcs = A[i](B[j]여도 됨) + lcs, LCS(i-1, j-1)로 이동
  • A[i] != B[j] → max(LCS(i-1, j), LCS(i, j-1))로 이동

4. 구현 코드

  • LCS(i, j)의 값을 저장하는 2차원 배열
int[] LCS = new int[A.length + 1][B.length + 1];
  • LCS 길이 구하기 코드
for (i = 1; i <= A.length; i++) {
	for (j = 1; j <= B.length; j++) {
		if (A[i - 1] == B[j - 1]) {
			LCS[i][j] = LCS[i - 1][j - 1] + 1;
		} else {
			LCS[i][j] += Math.max(LCS[i - 1][j], LCS[i][j - 1]);
		}
	}
}
  • LCS 구하기 코드
String lcs = "";
i = A.length;
j = B.length;
while (i > 0 && j > 0) {
	if (A[i - 1] == B[j - 1]) {
		lcs = A[i - 1] + lcs;
		i--;
		j--;
	} else {
		if (LCS[i - 1][j] > LCS[i][j - 1]) {
			i--;
		} else {
			j--;
		}
	}
}

5. 마무리

솔직히 DP 진짜 어렵다. 원래 예시를 들면서 자연스럽게 왜 DP를 써야하는지와 점화식 도출 과정을 설명하려고 했는데 처참하게 실패했다.(누가 나한테 해줬으면..) DP 문제는 동적 계획법을 통해 문제 해결 방법을 떠올리기 어렵다. 따라서 점화식 도출 과정을 이해하려고 노력하기 보다, 점화식을 이해하려고 노력하는게 더 좋은 접근일 것 같다.

감사합니다☺️

참조

profile
서여
안녕하세요:) 아키텍트가 되고 싶은 백엔드 개발자 지망생입니다.
다음 포스트

최소 신장 트리(MST)의 개념과 프림 알고리즘

0개의 댓글