LCS
📚 문제 설명
LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.
예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.
💡 LCS 알고리즘
이 문제는 LCS 알고리즘에 대한 지식이 없다면 풀 수 없다.
따라서 사전에 LCS 알고리즘을 알아보자.
우선 LCS 알고리즘은 아래와 같이 2차원 배열을 이용하여 생각을 해야 한다.
아래 표에 각각 들어가야할 값은 최장 공통 부분 수열의 길이이다.
그럼 이 점을 생각하며 아래 chart 를 채워보자
| 0 | A | B | C | D | |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | ||||
| B | 0 | ||||
| W | 0 | ||||
| E | 0 | ||||
| R | 0 |
chart[A][A] 를 채우는데 행의 A 와 열의 A 는 같기 때문에
chart[A][A] 에는 chart[A - 1][A - 1] 에 +1 값이 들어간다.
| 0 | A | B | C | D | |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 1 | |||
| B | 0 | ||||
| Q | 0 | ||||
| W | 0 | ||||
| E | 0 |
그럼 이제 A행을 모두 채워보려고 해보자.
그럼 만약 행의 값과 열의 값이 다르면 어떻게 해야할까?
이 문제에서 원하는 것을 바로 최장 공통 부분 수열이다.
연속되는 최대 문자열을 찾는 문제라면 다르겠지만, 최장 공통 부분 수열일 경우에는 이전의 최장 공통 부분 수열을 비교 하면 될 것이다.
그럼 이전의 최대 부분 수열은 무엇일까?
[A][B] 를 채운다고 생각 했을때, [A - 1][B], [A][B - 1] 이 두개를 비교해서 최대 값이 될 것이다.
이해가 되지 않는다면 두개의 포인터로 생각을 해보자
A B C D
^
A B Q W E
^
일 때 최대 수열은 AB 이다.
즉 위 표 기준으로 들어갈 값은 2
그럼 위의 문자열에서 포인터를 하나 이동해보자
A B C D
^
A B Q W E
^
이 경우 최장 공통 부분 수열은 무엇일까?
위의 포인터가 한단계 전일 때
or
아래 포인터가 한단계 전일 때
가 최장 공통 부분 수열일 것이다.
따라서 각각의 행과 열에 -1을 해보고 둘 중 더 큰 값을 넣어준다.그럼 이렇게 표가 완성되게 되고
우리가 원하는 값은 배열의 가장 마지막 값에서 구할 수 있다.
| 0 | A | B | C | D | |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 |
| A | 0 | 1 | 1 | 1 | 1 |
| B | 0 | 1 | 2 | 2 | 2 |
| Q | 0 | 1 | 2 | 2 | 2 |
| W | 0 | 1 | 2 | 2 | 2 |
| E | 0 | 1 | 2 | 2 | 2 |
왜 값이 같을 경우에는 chart[A-1][A-1] 에 +1 을 한 값일까?
그 이유는chart[B][B]를 채울 때 보면 알 수 있다.
문자열 "A" 와 "A" 을 비교한 값에서
문자열 "AB"와 "AB"를 비교 했을 때 공통적으로 B가 늘어 난다.
따라서 [A][A]의 최대 부분 수열에서 +1을 해주면 되기 때문이다.
그럼 여기서 우리는 위의 2차원 배열을 통해서 최대 공통 부분 수열 또한 찾을 수 있는데 어떻게 찾을 수 있을까?
해당 과정은 다음과 같다.
1. 2차원 배열의 마지막 값에서 왼쪽, 위쪽을 비교하며 올라간다.
2. 만약 왼쪽과 위의 값이 나와 다를 경우 내 부분의 위치를 저장, 왼쪽 대각으로 이동
3. 0이 될 때까지 반복
이 과정을 반복하면 [E][D] 에서 [B][B] 까지 가게 되고 B 값을 저장.
왼쪽 대각 위인 [A][A] 로 가게 되고 A 저장, 왼쪽 대각 위로 가고 값이 0이기 때문에 반복문 종료 .
이렇게 최대 부분 수열인 AB를 찾을 수 있다.
👨🏻💻 풀이 과정
그럼 이제 LCS 에 대해 알았으니 구현을 해보자.
- 문자열 2개에 크기에 맞는 2차원 배열 생성
- 문자열 비교하며 2차원 배열에 값을 넣어줌
- 2차원 배열 끝의 값이 최대 공통 부분 수열의 길이
LCS 구현 코드
class LCSequence {
constructor(StringA, StringB) {
this.LcsMap = new Array(StringA.length + 1);
this.StringA = StringA;
this.StringB = StringB;
// 2차원 배열 생성
for (let i = 0; i < this.LcsMap.length; i++) {
this.LcsMap[i] = new Array(StringB.length + 1).fill(0);
}
// 2차원 배열에 값을 넣어줌
this.find();
}
find() {
for (let i = 1; i < this.LcsMap.length; i++) {
for (let j = 1; j < this.LcsMap[0].length; j++) {
// 배열에 1번 인덱스부터 넣어주기 때문에 문자열 기준으로 -1
if (this.StringA[i - 1] === this.StringB[j - 1]) {
this.LcsMap[i][j] = this.LcsMap[i - 1][j - 1] + 1;
} else {
this.LcsMap[i][j] = Math.max(this.LcsMap[i][j - 1], this.LcsMap[i - 1][j]);
}
}
}
}
// 해당 문제에서 원하는 값
GetMaxLength() {
return this.LcsMap[this.StringA.length][this.StringB.length];
}
// 최대 공통 부분 수열을 찾는 함수
// 해당 문제에서는 필요X
GetLCS() {
let target = this.GetMaxLength();
let targetX = this.StringA.length;
let targetY = this.StringB.length;
let answer = '';
while (target !== 0) {
if (this.LcsMap[targetX - 1][targetY] === target) {
targetX = targetX - 1;
}else if (this.LcsMap[targetX][targetY - 1] === target) {
targetY = targetY - 1;
} else {
answer += this.StringA[targetX - 1];
targetX = targetX - 1;
targetY = targetY - 1;
target = this.LcsMap[targetX][targetY];
}
}
return answer;
}
}
전체 코드
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
class LCSequence {
constructor(StringA, StringB) {
this.LcsMap = new Array(StringA.length + 1);
this.StringA = StringA;
this.StringB = StringB;
for (let i = 0; i < this.LcsMap.length; i++) {
this.LcsMap[i] = new Array(StringB.length + 1).fill(0);
}
this.find();
}
find() {
for (let i = 1; i < this.LcsMap.length; i++) {
for (let j = 1; j < this.LcsMap[0].length; j++) {
if (this.StringA[i - 1] === this.StringB[j - 1]) {
this.LcsMap[i][j] = this.LcsMap[i - 1][j - 1] + 1;
} else {
this.LcsMap[i][j] = Math.max(this.LcsMap[i][j - 1], this.LcsMap[i - 1][j]);
}
}
}
}
GetMaxLength() {
return this.LcsMap[this.StringA.length][this.StringB.length];
}
}
const LCS = new LCSequence(input[0], input[1]);
console.log(LCS.GetMaxLength());🧐 후기
이번 기회에 LCS 알고리즘에 대해 알게 되는 좋은 기회를 준 문제이다.
처음에는 LCS 알고리즘을 봐도 이해가 되지 않아서 이런저런 자료를 살펴보며 이해하는 과정을 거쳤고 직접 표를 그려보고 문자열을 따라가며 천천히 생각하면서 이해해 나갔다. 너무 2차원 배열이라고 생각해서 복잡하게 생각해서 더 이해가 안 됐던 것 같고 단순하게 문자열을 하나씩 따라가다 보니 이해가 더 쉬웠다.
