[Algorithm] 동적 프로그래밍 LIS 문제 (Memoization VS Tabulation)

LIS(Longest Increasing Subsequence)는 엄격하게 오름차순으로 정렬된 가장 긴 부분 배열을 반환합니다. 부분 배열(Subsequence)는 데이터의 순서가 유지되는 모든 부분 배열을 의미합니다. 반면 substring 혹은 subarray는 연속된 부분 배열을 의미합니다. 

 

 

예를 들어 'abc' 문자열이 주어진 경우 substring과 subsequence는 다음과 같습니다.

arr='abc';

substring = 'a','b','c','ab','bc', 'abc';
subsquence = 'a','b','c','ab','ac','bc','abc';

 

주어진 배열에서 subsequnce를 구하기 위해서 동적 프로그래밍(Dynamic Programming) Memoization과 Tabulation을 사용할 수 있습니다. 쉽게 말해 Memoization은 Top-Down 방식으로 작동하고, Tabulation은 Bottom-up 방식으로 작동합니다.

 

[Algorithm] 동적 계획법 타일링 알고리즘 문제 Javascript

 

[Algorithm] Advanced Fibonacci using Memoization

 

 

 

문제

 

정수를 요소로 가지는 문자열을 입력받아 다음 조건을 만족하는 LIS의 길이를 반환합니다.

입/출력

 

입력 arr

• Number 타입의 요소를 가지는 배열
• arr.length <= 60,000
• arr[i] <= 100,000 의 정수

 

출력

• Number 타입의 정수

 

주의사항

 

• LIS의 길이를 반환합니다.
• LIS가 존재하지 않는 경우는 없다고 가정합니다.

 

입출력 예시

let output = LIS([3, 2]);
console.log(output); // --> 1 (3 or 2)

output = LIS([3, 10, 2, 1, 20]);
console.log(output); // --> 3 (3, 10, 20)

 

풀이

 

LIS(Longest Increasing Subsequence)는 동적 프로그래밍의 Memoization과 Tabulation으로 답을 찾을 수 있습니다. 순서를 유지하면서 처음부터 카운팅을 시작할 것인지, 마지막 부분에서부터 카운팅을 할 것인지 결정해야 합니다. 

① Memoization

LIS를 기록할 memo 배열을 생성합니다. 배열은 -1로 초기화 됩니다. 뒷 부분에서부터 카운팅을 시작할 것이므로 맨 마지막 요소는 1을 할당합니다. 

const memo = Array(arr.length).fill(-1);
memo[memo.length-1] = 1;

 

재귀 함수를 작성합니다. for 반복문을 순회하면서 내부요소들에 대해 재귀 함수를 실행합니다. LIS를 구하는 과정에서 순서를 유지하면서 subsequence를 구해야 하기 때문입니다. [3,4,5]가 존재할 수 있지만, [3,5,4]일 때도 [3,4]라는 subsequnce를 구해야 하므로, for문과 재귀 함수를 혼합해서 사용합니다. 마지막 요소에 도달하면 값을 반환하는 탈출 조건을 생성합니다.

const recur = (idx) => {
    if(memo[idx] !== -1) return memo[idx];
}

 

 

for 반복문을 설정합니다. 시작은 현재 idx 바로 다음 부터 순회하기 시작하며 특정 조건이 충족될 경우 arr[idx]값을 증가시키면서 LIS의 길이를 구합니다. 재귀 함수 특성상 탈출조건 직전까지 함수가 호출되며 반환되면서 값을 더하면서 거슬러올라오게 됩니다.

const recur = (idx) => {
    if(memo[idx] !== -1) return memo[idx];
    
    let max = 1;
    
    for(let i=idx+1; i<arr.length; i++){
        const adder = recur(i);
        
        if(arr[i] > arr[idx]){
            max = Math.max(max, adder+1);
        }
    }
    
    return memo[idx] = max;
}

 

Memoization 전체 코드

function LIS(arr){
    const memo = Array(arr.length).fill(-1);
    memo[memo.length - 1] = 1;

    const recur = (idx) => {
        if(memo[idx] !== -1) return memo[idx];

        let max = 1;

        for(let i=idx+1; i<arr.length; i++){
            const adder = recur(i);

            if(arr[i] > arr[idx]){
                max = Math.max(max, adder+1);
            }
        }

        return memo[idx] = max;
    }
    recur(0);
    return Math.max(...memo);
};

 

 

②Tabulation

Memoization과 다르게 맨 처음부터 LIS 길이를 구해냅니다. 2개의 반복문이 돌아가면서 특정 지점 앞에 있는 요소들을 특정조건을 걸어 확인한후 길이를 증가시킵니다. 길이를 담을 tabulation 배열을 주어진 arr 배열 길이만큼 생성하고, 1로 초기화 합니다.

function TabulationLIS(arr) {
    const N = arr.length;
    const tabulation = Array(N).fill(1);
}

 

2개의 반복문을 순회하면서 특정지점(idx) 앞에 있는 요소들과 비교하면서 LIS를 구해냅니다. 만약 이전 로직에서 구한 부분배열(Subsequence)가 존재하면 누적해서 LIS를 구해냅니다.

for(let i=1; i<N; i++){
    for(let j=0; j<i; j++){
        if(arr[i] > arr[j] && tabulation[i] < tabulation[j] + 1){
            tabulation[i] = tabulation[j]+1;
        }
    }
}

 

Tabulation 전체 코드

const tabulationLIS = (arr) => {
    const N = arr.length;
    const tabulation = Array(N).fill(1);
    
    for(let i=1; i<N; i++){
        for(let j=0; j<i; j++){
            if(arr[i] > arr[j] && tabulation[i] < tabulation[j] + 1){
                tabulation[i] = tabulation[j] + 1;
            }
        }
    }
    return Math.max(...tabulation);
}

 

 

[Algorithm] 힙 정렬(Heap Sort) 구현하기 Node.js/Javascript

 

[Algorithm] Gossip Protocol 알고리즘 문제 Node.js

 

[Algorithm] 최대 이진 힙 구현하기 Node.js/Javascript