300. Longest Increasing Subsequence

문제링크: https://leetcode.com/problems/longest-increasing-subsequence/

nums의 숫자배열에서 몇몇 원소를 삭제해subsequence를 만들 수 있다. 이 subsequence 중에 중복 없는 오름차순이 되는 가장 긴 길이를 구하는 문제이다.

Solution

DP solution

끝나는 번호 => 가장 긴 sequence의 길이를 저장한다. 예를 들어 [1,5,3] 의 경우 1 => 1, 5 => 2, 3 => 2를 저장할 수 있다. 만약 새원소 4가 들어왔을 때 앞의 저장된 자료를 통해 4미만의 값 중 가장 큰 3 => 2를 가져와 새 sequence길이 4 => 3을 추가할 수 있다.

Algorithm

• memoization을 저장할 맵을 만든다.
• 원소를 하나씩 탐색하며 위의 방식으로 자료를 추가한다.
• 결과적으로 map에는 끝나는 숫자 => 최대 길이를 저장하게 되고 새 원소가 추가될 때마다 이를 이용해 결과를 끌어낼 수 있다.
• result를 maxCount가 계산될 때 연산한다.

var lengthOfLIS = function(nums) {
    result = 0;
    const map = new Map(); // lastNumber => Max Sequence Count
    for (let num of nums) {
        let maxCount = 0;
        for (let [key, val] of map) {
            if (key < num) {
                maxCount = Math.max(maxCount, val);
            }
        }
        result = Math.max(result, maxCount + 1);
        map.set(num, maxCount + 1);
        // console.log(map)
    }
    return result;
};

DP & Greedy solution

위의 DP부분을 반대로 생각해보자. 기존의 방식은 마지막 번호 => 최대길이의 방식으로 저장하였지만 반대로 최대길이 => 가장 작은 마지막 번호로도 생각해볼 수 있다.
예를 들어 [2,3,6,4,5]의 배열이 있다고 하자. 처음 2, 3, 6을 통해

• 최대길이 1 중 가장 작은 끝 수 2
• 최대길이 2 중 가장 작은 끝 수 3
• 최대길이 3 중 가장 작은 끝 수 6

을 얻을 수 있다. 이후에 4가 들어오면서 2->3->6의 링크 말고 2->3->4의 새 링크도 얻을 수 있다. 이 경우에 최대길이 3 중 가장 작은 끝 수를 4로 갱신할 수 있다. 찾는 방법은 앞에서 부터 4보다 크거나 같은 값을 찾으면 replace하는 방식이다. 이 배열을 sequence라 하자.

주의할 점은 이 seqeunce가 정확한 순서를 나타내는 것이 아닌 최대길이가 index + 1인 링크의 가장 작은 끝수를 저장한다는 점이다.

Algorithm

• 연결길이 => 가장 작은 끝 수를 저장할 sequence 배열을 만든다.
• nums를 순회한다.
• sequence의 끝 값보다 큰 숫자일 경우 뒤에 추가한다.
• 아닐 경우 앞에서부터 탐색해 num보다 큰 값을 발견할 경우 replace한다.
• 최종적으로 sequence의 길이가 가장 긴 subsequence의 길이가 된다.
• 주의할 점은 sequence의 배열이 가장 긴 순서 자체인 것은 아니다.

var lengthOfLIS = function(nums) {
    const sequence = [nums[0]];
    nums.forEach((num) => {
        if (sequence.at(-1) < num) {
            sequence.push(num);
        } else {
            for (let i = 0; i< sequence.length; i++) {
                if (sequence[i] >= num){
                    sequence[i] = num;
                    break;
                }
            }
        }
    });
    return sequence.length;
};

• DP 문제는 memoization 방식을 한번 반대로 뒤집어서 생각해 볼 필요가 있는 것 같다.