LCS (Logest Common Subsequence)
LCS (Logest Common Subsequence) — #LCS #LongestCommonSubsequence #개발자의도구들 #코딩테스트 사용된 언어: 코틀린, 혹은 파이썬 순...
#LCS #LongestCommonSubsequence #개발자의도구들 #코딩테스트
- 사용된 언어: 코틀린, 혹은 파이썬
- 순서: 로직, 코드 구현, 코드 분석
이 글이 종착지가 되도록
매우 유명한 알고리즘이다. 풀이법이 유명해서 외우고 다음 문제에 적용하면 된다. 근데 이 풀이법이 직관적으로 이해가 되지 않았다. 여러 레퍼런스를 참고하여 왜 이런 공식이 만들어졌는지에 대해 깊이 있게 정리하였다.
나 역시 다른 이들의 레퍼런스를 참고했지만, 초등학생도 쉽게 이해할 수 있도록 글을 정리하고자 노력하였다.
LCS 알고리즘
Solved ac (class 4 9251. LCS ) 42%
\* 문제 출처: https://www.acmicpc.net/problem/9251
LCS는 두 문자열의 가장 긴 공통 Sequence를 찾는 것이다. Sequence와 substring은 다른 개념인데 아래를 보면 직관적으로 이해할 수 있다.
ABCDEF
👉 substring: ABC, BCD, CDE ...
👉 sequence: ABD, BCE, BCF ...
sequence는 substring과 달리 문자가 연이어 오지 않아도 된다.
LCS는 두 문자열 X, Y에 대하여 Longest Common Sequence를 찾는 알고리즘이다. 예를들어 아래와 같이 두개의 문자열이 주어진다고 가정해보자.
X: ABCBDAB
Y: BDCABA
이때 가장 긴 Sequence를 찾아야 한다. 어떻게 찾을 수 있을까?
접근법 1. Brute force
문제를 이해했으면 당신의 두뇌는 본능적으로 문자열을 만들어 비교하기 시작한다. 아래와 같은 방법으로 생각할 것이다.
가장 최소 단위의 공통 sequence부터 길이를 늘려 하나씩 만들어 나간다.
길이가 1:
X -> A, B, C, D
Y -> B, D, C, A, B
길이가 2:
X -> AB, AC, AD, AA, BC, BB, BD, BA, ...
Y -> BD, BC, BA, BB, DC, DA, DB, ...
길이가 3:
X -> ABC, ABB, ABD ...
Y -> BDC, BDA, BDB ...
이런 방식으로 만들어서 공통된 최장 길이의 sequence를 찾으면 된다. 컴퓨터가 물론 계산을 잘하지만, 문자열이 길어지면 연산 횟수가 급격하게 증가한다. 우리는 좀 더 이성적인 사고 방식이 필요하다.
DP
Dynamic Programming
앞서 해당 문제의 풀이방법은 매우 유명하다고 하였는데, 이 알고리즘은 DP에 속한다. DP를 잘 사용하면 연산량을 압도적으로 줄일 수 있다.
일반적으로 DP는 다음의 절차를 따른다.
1. 해를 분석하여, 부분 문제로 분해한다.
2. 부분 문제의 해로 큰 문제의 해를 표현한다. 👉 보통 이를 점화식이라 한다.
3. 적당한 순서로 DP 테이블을 채운다.
4. 테이블에서 해를 계산하며, 알고리즘의 Correctence를 증명한다.
말이 좀 어려울 수 있지만, 핵심은 문제의 해가 되는 점화식을 찾는 것, 그리고 그 점화식을 통해 테이블을 채우는 것이 전부이다.
DP를 문제에 적용하기 어려운 이유는 해당 문제가 DP로 풀리는지 잘 감이 안잡히기 때문이다. 하지만, 문제를 잘 분석하여, 큰 문제의 해를 구할 때 작은 문제의 값을 참조하도록 구성되어 있다면 DP를 적용해볼만하다.
DP를 적용하기
자, 우리는 다시 문제를 돌아볼 필요가 있다. 우선 brute force에서 해를 어떻게 구했는지 돌아봐야 한다. 길이가 2인 sequence를 구한다고 가정해보자.
X: ABCBDAB
Y: BDCABA
여기서 우리는 본능적으로 X의 두번째 위치까지 AB를 고정하고, Y를 탐색하여 AB가 Y에 속해있는지 비교한다.
그러면 비교하는 순서를 생각해보자.
X: AB 📌
Y: 🔍 BD, DC, DA, CA, DCA, CAB, BDC, BDCA, BDCAB...
이렇게 비교하여 AB가 Y에 속해있는 것을 확인할 수 있다.
여기서 우리는 인사이트를 얻을 수 있는데 BDCAB를 각 y1y2y3y4y5라고 표현하면, y5이전까지의 LCS 길이는 y5를 만나기전까지 최대가 1이라는 것이다.
X: A
Y: BDC
LCS = 0
X: A
Y: BDCA
LCS = 1 => x1과 y4까지의 어떤 순열이든 LCS는 1이다.
X: AB
Y: BCDAB
LC@ = 2 => x2와 y5의 최장길이는 2가 된다.
설명이 조금 어려울 수 있는데 이해가 안된다면 다음 챕터로 바로 넘어가도 된다. 본격적으로 점화식을 세우기 시작하면 이해가 명확해진다.
점화식을 세우기
LCS 알고리즘의 점화식을 명확하게 이해하는 것이 중요하다. 우선 X와 Y를 다시 정의하자.
X는 길이가 n인 문자열이며 x\_i은 i번째 "문자" 이다.
Y는 길이가 m인 문자열이며 y\_j은 j번째 "문자" 이다.
그리고 LCS(i, j)를 다음과 같이 정의한다.
그럼 LCS(2, 5)의 의미는 무엇일까?
X: ABCBDAB
Y: BDCABA
X_2 = AB
Y_5 = BDCAB
즉 AB와 BDCAB의 LCS 길이이다.
위의 예시에서 AB와 BDCAB의 길이는 이전 길이의 영향을 받는 것을 간접적으로 봤다.
두 가지 케이스
LCS(i, j)의 길이는 두 가지 케이스에 따라 각 각 결정된다.
LCS를 판별할 때 마지막 값이 같은 경우와 같지 않은 경우이다.
📌 1. 끝 값이 같은 경우
X: AB
Y: BDCAB
X_2 = Y_5
이 경우 끝값을 무조건 포함하게 되어있다. 끝 값이 같은데 LCS에 포함하지 않을 이유가 없다. 그럼 무조건 LCS 길이는 + 1이된다. 그럼 어떤 값에서 +1이 되는가? 바로 각 각 이전 길이의 LCS값에서 +1이 된다.
= 여기서는 LCS(2 - 1, 5 -1)에서 +1 이 된다.
X = A
Y = BDCA
LCS 값은 1이다.
📌 끝 값이 같지 않은 경우
끝 값이 같지 않은 경우에는 각각의 문자를 선택하거나 선택하지 않을 수 있다. 아래의 경우를 보자
X: ABCBDAB
Y: BDCABA
LCS(3,5)
LCS(3, 5)는 ABC와 BDCAB를 비교한다. X의 끝값 C와 Y의 끝값 B가 같지 않은 상황이다. 이경우 X의 끝값을 포기하거나, Y의 끝값을 포기하여 비교한다. (둘다 선택할 필요는 논리적으로 없다. 끝값이 같지 않기 때문에 LCS에 전혀 영향을 미치지 못한다.)
이미 같지 않기 때문에 LCS(3, 5)는
LCS(2, 5)와 LCS(3, 4) 중 하나의 값과 같다는 것을 알 수 있다.
LCS(2, 5) = AB와 BDCAB => LCS = 2
LCS(3, 4) = ABC와 BDCA => LCS = 1
LCS(3, 5)
-> (AB) C
-> BDC (AB)
LCS(2, 5)의 값과 같다.
결론 적으로 아래 식이 성립한다.
순서대로 채워보기
1. 초기 값 설정
X_0 = 빈 문자열
Y_0 = 빈 문자열
2. 차례대로 넣기
👉 초기값 계산
| X/Y | 0 | B | D | C | A | B | A |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | ||||||
| B | 0 | ||||||
| C | 0 | ||||||
| B | 0 | ||||||
| D | 0 | ||||||
| A | 0 | ||||||
| B | 0 |
빈 문자열 ""은 어떤 문자에 대해서도 LCS = 0이다.
👉 x = 1 계산
| X/Y | 0 | B | D | C | A | B | A |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| B | 0 | ||||||
| C | 0 | ||||||
| B | 0 | ||||||
| D | 0 | ||||||
| A | 0 | ||||||
| B | 0 |
- LCS(1, 1) 는 A와 B를 비교
- LCS(1, 4) 는 A와 BDCA를 비교
- LCS(1, 5) 는 A와 BDCAB를 비교 ...
👉 x = 2 계산
| X/Y | 0 | B | D | C | A | B | A |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| B | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
| C | 0 | ||||||
| B | 0 | ||||||
| D | 0 | ||||||
| A | 0 | ||||||
| B | 0 |
- LCS(2, 2)는 AB와 BD를 비교한다. 끝 값이 값지 않기 때문에 A와 BD 혹은 AB와 B를 비교하여 큰 값이 선택된다 = 1
- LCS(2, 5) 는 AB와 BDCAB를 비교한다. 끝 값이 같기 때문에 마지막 B값은 무조건 포함한다. 끝 값을 제거했을 때 LCS 길이를 포함해야하므로 LCS(1, 4)의 값을 참조한다.
- A와 BDCA의 LCS 길이 = 1
이런 식으로 모든 표를 채우면 된다.
| X/Y | 0 | B | D | C | A | B | A |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| B | 0 | 1 | 1 | 1 | 1 | 2 | 2 |
| C | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
| B | 0 | 1 | 1 | 2 | 2 | 3 | 3 |
| D | 0 | 1 | 2 | 2 | 2 | 3 | 3 |
| A | 0 | 1 | 2 | 2 | 3 | 3 | 4 |
| B | 0 | 1 | 2 | 2 | 3 | 4 | 4 |
- LCS의 최장 길이는 4이다.
문자열 뽑아내기
위 표는 LCS 길이 자체가 테이블에 저장되어있다. LCS 자체를 보고 싶으면 어떻게 해야하는가?
표를 역으로 따라 올라가면 알 수 있다.
| X/Y | 0 | B | D | C | A | B | A |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| B | 0 | 1 🖌️ | 1 | 1 | 1 | 2 | 2 |
| C | 0 | 1 | 1 | 2 🖌️ | 2 | 2 | 2 |
| B | 0 | 1 🖌️ | 1 | 2(↑) | 2 | 3 🖌️ | 3 |
| D | 0 | 1 | 2 🖌️ | 2 | 2 | 3 | 3 |
| A | 0 | 1 | 2 | 2 | 3 🖌️ | 3 | 4 🖌️ |
| B | 0 | 1 | 2 | 2 | 3 | 4 🖌️ | 4 |
- 같으면 대각선으로, 다르다면 위, 아래중 큰 값으로 올라가면 된다.
- 문자가 다른데 위 아래 값이 같다면 문자열이 여러개가 나올 수 있다는 의미다.
X: ABCBDAB
Y: BDCABA
LCS = 4
BCBA
BDAB
BCAB
레퍼런스
[\[알고리즘\] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence
LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Common Substring)을 말하기도 합니다.
velog.io](https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence#longest-common-subsequence-substring)
필기 노트
첨부파일
LCS 알고리즘