LCS, LIS (JavaScript)

LCS? LIS?

LCS(Longest Common Subsequence) 는 가장 긴 공통 부분 수열으로, 공통적으로 일치하는 수열 중 가장 긴 부분을 의미한다.
LIS(Longest Increasing Subsequence)는 가장 긴 증가(또는 감소) 하는 수열을 의미한다.

두 가지 모두 **DP 알고리즘**에 속한다.두 가지의 개념과 구현코드를 정리할 예정이다!

LCS

• 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴것을 찾는 문제
• 이때 꼭 문자열이 연속적으로 존재할 필요는 없다.

ex) CAPCAK, ACAYKP 의 LCS는 ACAK 가 된다.

LCS 점화식

결론적으로 LCS의 점화식은 아래와 같다.

비교하고 있는 두 문자가 같다면 -> dp[i][j] = dp[i-1][j-1] + 1
비교하고 있는 두 문자가 다르다면 -> dp[i][j] = Math.max(dp[i-1][j], dp[i][j - 1]

점화식 풀이

1. LCS를 풀기 위해서는 비교대상인 각각의 문자열 길이보다 1이 큰 배열로 2차원 배열로 만든다.
2. 0행과 0열은 모두 0으로 초기화 한다.

3. 반복문을 돌면서 문자열을 비교하며 각 칸을 채워나간다.

• 예를들어 (C,A) 의 경우는, C와 A를 비교하겠다는 뜻이다.
• C는 A와 다르기때문에 dp[i][j] = Math.max(dp[i-1][j], dp[i][j - 1]의 값이 된다.

• (C,C)의 경우는 C와 AC를 비교하는 것을 의미하며 비교중인 문자는 C, C를 의미한다.
• 따라서 dp[i][j] = dp[i-1][j-1] + 1 의 값이 된다.

• (C, A)의 경우, C와 ACA를 비교하는 것을 의미하며 비교중인 문자는 C, A를 의미한다.
• C는 A와 다르기때문에 dp[i][j] = Math.max(dp[i-1][j], dp[i][j - 1]의 값이 된다.

• 해당 과정을 반복하게 되면 최종적으로 표를 채울 수 있다.
• 결론적으로 dp의 마지막 행, 마지막 열에 위치한 숫자가 두 문자열의 LCS 값이 된다.

구현 코드

• 백준 LCS 코드

const readline = require('readline');
const rl = readline.createInterface({
    input : process.stdin,
    output : process.stdout
});

function solution (input) {
    const str1 = input[0];
    const str2 = input[1];
    
    const dp = Array.from({length : input[0].length + 1}, () => Array(input[1].length + 1).fill(0));
    
    for (let i = 1; i <= str1.length; i++) {
        for (let j = 1; j <= str2.length; j++) {
            if (str1[i - 1] === str2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }
    console.log(dp[input[0].length][input[1].length]);
}

let input = [];

rl.on('line', function(line) {
    input.push(line);
}).on('close', () => {
    solution(input);
    process.exit();
});

---

LIS

• 어떤 수열에서 만들 수 있는 부분 수열중에서 가장 길면서 오름차순으로 유지하는 수열 List
• DP를 활용한 LIS구현과, 이분 탐색을 활용한 LIS 구현 방법이 존재한다.

ex) [5, 3, 1, 2, 6] 의 배열이 존재할 때,
위 배열로 만들 수 있는 증가 부분 수열 -> [5, 6], [3, 6], [1, 2, 6], [1, 6], [2, 6]
최장 증가 부분 수열 (LIS) -> [1, 2, 6]

DP를 이용한 LIS

• 가장 단순한 방법으로 완전탐색이다.
• 시간복잡도는 O(N^2)를 가진다.

• 수열의 한 원소에 대해, 그 원소에서 끝나는 최장 증가수열을 구해야 하므로, 최장 증가 수열의 K(임시)를 제외한 모든 원소들은 반드시 K보다 작다.
• 따라서 K의 앞 순서에 있는 모든 원소들 중, 값이 K값보다 작은 원소에 대해
  • 그 각각이 원소에서 끝나는 최장 증가수열의 길이를 알고 있다면
  • K에서 끝나는 최장 증가 수열의 길이를 구할 수 있다.

즉 앞 순서의 모든 원소에서 끝나는 최장 증가 수열들의 길이 중, 가장 긴 것을 골라 1을 더한 것이 현재 수에서 끝나는 최장 증가 수열의 길이다.
따라서 dp[i] = i번째 인덱스에서 끝나는 최장 증가 수열의 길이

구현 코드

• 주의 할 점은 dp[j] > count 해당 부분이다.

const list = [5, 3, 1, 2, 6];

// 특정 원소에서 끝나는 LIS의 최소값 설정
let dp = new Array(list.length).fill(0); 

for(let i = 0; i < n; i++) {
	let count = 0;
  	
  	for (let j = 0; j < i; j++) {
      	// i 번째 이전에 위치한 모든 원소에 대해, 해당 원소에서 끝나는 LIS의 길이를 확인한다.
    	if (list[i] > list[j] && dp[j] > count) {
       		count = dp[j];
        }
    }
  	
  	// 이전 원소에서 끝나는 LIS에 +1 (현재 수)를 더한 새로운 LIS 길이
  	dp[i] = ++count;
}

console.log(Math.max(...dp));

이분탐색을 이용한 LIS

• 입력 값의 크기가 클 경우에 DP를 활용하면 효율이 떨어지기 때문에, 이분 탐색을 활용해서 시간 복잡도를 줄일 수 있다.
• 시간복잡도는 O(logn)을 가진다.

• arr 배열을 LIS의 형태로 유지하기 위해 기존 수열의 각 원소가 LIS에 들어갈 위치를 찾는 원리로 동작한다.
• 현재 원소를 아래 배열에 넣어, LIS를 유지하려고 할 때 최적의 위치를 찾는 것이다.

구현 코드

// value가 arr에 위치할 인덱스를 구하는 함수
function binarySearch (list, left, right, value) {
    while(left < right) {
        let mid = Math.floor((left + right) / 2);
        
        if (list[mid] < value) {
            left = mid + 1;
        } else if (list[mid] > value) {
            right = mid;
        } else {
            return mid;
        }
    }
    
    return right;
} 

function solution (N, list) {
    const arr = [];
    arr.push(list[0]);
    
    for (let i = 1; i < N; i++) {
      	// arr의 마지막 원소보다 list[i]가 클 경우에는 push
        if (arr[arr.length - 1] < list[i]){
            arr.push(list[i]);
        }
        else {
          	// arr에 오름차순으로 위치할 인덱스 찾기
            let index = binarySearch(arr, 0, arr.length - 1, list[i]);
            arr[index] = list[i];
        }
    }
    
  	// LIS의 길이
    console.log(arr.length);
}