LeetCode 300. Longest Increasing Subsequence

Longest Increasing Subsequence - LeetCode

문제 설명

가장 기본적인 LIS 문제. 

nums 배열에서 가장 긴 증가하는 부분 수열의 길이를 반환하라.

입력: nums = [10,9,2,5,3,7,101,18]
출력: 4
설명: 가장 긴 증가 부분 수열은 [2,3,7,101]이며, 따라서 길이는 4입니다.

입력: nums = [7,7,7,7,7,7,7]
출력: 1

 

문제 풀이

보통 이 LIS 문제는 DP를 사용해서 문제를 풀지만 이번에는 이분 탐색 문제 풀이방식으로 문제를 풀어 보았음.

일단 이분 탐색을 사용하기 위해 먼저 하나의 후보 배열(cur)을 유지함.

만일 cur = [2 3 5]

길이 1짜리 증가 부분수열을 만들 때 가능한 가장 작은 끝값 -> 2

길이 2짜리 증가 부분 수열을 만들 때 가능한 가장 작은 끝값 -> 3

길이 3짜리 증가 부분 수열을 만들 때 가능한 가장 작은 끝값 -> 5

즉 , 같은 길이의 증가 부분 수열이라면 최대한 마지막 값을 작게 유지하는 것이 핵심

why? => 끝 값이 작을수록 뒤에 더 많은 숫자를 추가해서 증가하는 배열을 만들 수 있기 때문

 

ex)

2 3 5

2 3 10

두 배열에서 끝값이 10보다 5가 들어가 있는 것이 더 많은 그다음의 증가하는 배열에 걸맞은 수가 들어올 수가 있음.

 

전체 배열을 처음부터 끝까지 돌면서 현재 들어갈 수를 판단하는데 이때 두 가지 조건을 확인하면서 바로 cur배열에 삽입할지 또는 현재 들어갈 값을 이용해 기존 cur배열의 끝값을 더 작게 만들 수 있는지 확인하는 조건이 있다.

 

조건 1 => 현재 들어갈 값이 cur 배열의 마지막 값보다 큰 경우

nums 배열을 돌면서 현재 nums [i]의 값이 만약에 cur에 들어가 있는 마지막 값보다 크다면 기존 증가 부분 수열의 뒤에 그대로 이어서 붙일 수 있음

따라서 cur배열에 push_back 해줌

ex) 

cur 배열 = 2 4 7 

이고 nums[i]가 10이면

바로 들어가기가 가능함

 

조건 2 => 현재 들어갈 값이 cur 배열의 마지막 값보다 작거나 같은 경우

이때는 cur의 마지막 값보다 작거나 같으면 바로 들어갈 수 없음. 따라서 cur에 들어가기 위해서는

현재 값인 nums[i] 보다 크거나 같은 값이 맨 처음에 등장하는 위치에 넣어준다.

ex) 

cur = 2 4 7 10

이고 nums[i] 가 6이라면

이때는 7과 값을 교체한다.

이렇게 끝값을 더 작게 유지하면 이후에 새로운 숫자가 들어왔을 때 뒤에 붙을 가능성이 높아짐.

즉 값을 교체 하는 것은

이후에 더 긴 LIS를 만들기 위해 (조건 1에 맞추어 길이를 늘이기 위해) 좋은 조건의 상태를 만들기 위함 

 

이분탐색 활용법

매 원소마다 현재 값 이상인 첫 위치를 빠르게 찾기 위해 이분 탐색을 사용. 만일 매 원소마다 선형으로 찾으면 O(N^2)의 시간 복잡도를 가지므로 이분 탐색을 사용하여 빠르게 탐색하자.

cur배열은 항상 오름차순으로 유지되니, 현재 들어갈 값 nums [i]를 기준으로 이보다 작은 구간 | 이보다 큰 구간으로 나누면 경계가 생김. 따라서 이 경계의 첫 위치만 찾으면 되므로 이때 이분 탐색을 활용할 수 있음.

 

탐색의 시작을 left, right로 두고 계속 mid를 갱신하면서 현재 값 이상인 첫 위치를 빠르게 찾는다.

 

if(cur [mid]>=nums [i])

{

   right=mid;

}

=> 현재 값도 후보지만 더 왼쪽에도 조건에 만족하는 값이 있을 수 있으므로 왼쪽의 범위를 더 확인해야 함.

==> 근데 이 mid가 정답 위치일 경우도 있을 수 있기 때문에 +1은 x

 

else

{

left=mid+1;

}

=> 가운데 값을 확인했을 때 현재 값이 cur [mid] 보다 작으면 교체 대상이 될 수 없음. 따라서 조건을 만족하는 오른쪽 구간으로 범위를 줄이면서 탐색해야 함.

 

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> cur;
        cur.push_back(nums[0]);
        for(int i=1;i<nums.size();i++)
        {
            if(cur[cur.size()-1]<nums[i])
            //현재 값이 가장 큰 끝값보다 크다면 바로 
            // 기존 증가 부분 수열 뒤에 삽입 가능함
            {
                cur.push_back(nums[i]);
            }
            else
            {
            //nums[i] 이상인 값이 처음 등장하는 위치를
            // 이분 탐색을 이용하여 빠르게 탐색함
                int left=0;
                int right=cur.size()-1;
                while(left<right)
                {
                    int mid=(right+left)/2;
                    if(cur[mid]>=nums[i])
                    {
                        right=mid;
                    }
                    else
                    {
                        left=mid+1;
                    }
                }
                cur[left]=nums[i];
                //첫번째로 큰 값을 찾아
                //기존 끝값을 더 작은 값으로 교체함
                
            }
        }
        for(int i=0;i<cur.size();i++)
        {
            cout<<cur[i] <<' ';
        }
        return cur.size();
    }
};

 

cur 배열에 들어가 있는 값은 실제 LIS일 때 배열이 아니다!

cur 배열의 의미

각 길이별로 증가 부분수열을 만들 때 가능한 가장 최소의 끝값

 

cur 배열을 갱신하다 보면 순서가 바뀌어 정답의 배열이 되지 않는다.

ex) 2 3 4 1 5

라 하면

2

2 3

2 3 4

1 3 4 (1이 들어왔을 때 2와 바꿈)

1 3 4 5

이렇게 되면 최종 cur은 1 3 4 5가 되어 실제 부분 수열과는 다른 값이 저장이 되어있음

cur은 실제 LIS를 저장하는 배열이 아니라 각 길이의 증가 부분 수열이 가질 수 있는 최소 끝값을 저장하는 배열이라는 점을 잊지 말아야 함.

 

cur배열의 길이가 최종적으로 LIS의 길이가 되는 이유

cur 배열의 길이가 늘어나는 것은 현재 비교하는 값이 cur의 마지막값보다 클 때뿐.

2 4 7에서 10이 들어오면 이때는 조건에 충조하므로 2 4 7 10 이 됨

길이 3짜리 증가 부분 수열이 존재하고 그 뒤에 더 큰 값인 10을 붙일 수 있다는 의미. 즉 길이 4짜리 증가 부분 수열이 존재함.

반대로 2 4 7 -> 2 4 6일 때는 길이를 늘이지 않는다. 

단순히 길이의 끝값만 미래에 더 추가될 수 있도록 유리하도록 수를 교체하는 것임.

 

번외. => 만약 현재 증가하는 LIS배열을 실제로 출력하고 싶을 때?

이때는 cur 배열과 다르게 각 원소가 LIS에서 어느 위치에 들어갔는지와 이전 원소가 누구였는지 두 개를 같이 기록해야 함

즉 cur배열과 또 다른 이전 원소가 누구였는지에 대한 배열 총 2가지를 관리해야 함.

1. 현재 원소가 LIS의 몇 번째 위치에 해당하는지 추적

2. 현재 원소 바로 이전에 연결되는 LIS 원소의 인덱스를 기록함

3. 각 길이의 LIS 후보가 실제 원본 배열의 어떤 인덱스에서 끝나는지도 관리

4. 모든 탐색이 끝난 뒤 가장 긴 LIS의 마지막 원소 인덱스부터 이전 인덱스를 따라가며 역추적함

5. 역추적한 결과는 뒤에서 붙어 얻어지므로 마지막에 순서를 뒤집으면 실제 LIS를 복원 가능

 

EX) 

2 3 4 1 5 -> 여기서 LIS가 되는 배열은 2 3 4 5 

prev배열과 cur 배열을 같이 보면서 설명

prev 배열 -> 이전에 어떤 값이 있는지 저장 (실제로는 인덱스를 저장할 듯 함)

 

1. nums [0] => 2

cur = [2]

prev [2] = 없음 (맨 처음에 들어오는 값이므로 없어)

관계

아직 생성 X

 

2. nums [1] => 3

cur = [2 3] : 3은 2보다 크니 추가

prev [3] = 2 

관계

2 -> 3

 

3. nums [2] => 4

cur = [2 3 4] : 4는 3보다 크니 추가

prev [4] = 3 : 4 이전 값에 3이 있음

관계 

2 -> 3 -> 4

 

4. nums [3] => 1

cur = [1 3 4] : 1은 cur의 마지막 값보다 작다. 1 이상인 첫 위치를 찾아 교체 즉 2와 1 교체함

prev [1] = 없음

관계

2 -> 3 -> 4

 

5. nums [4] => 5

cur = [1 3 4 5 ] : 5는 4보다 큼 추가

prev [5] = 4

----

최종적으로 완성된 prev배열

+ 관계 

2->3->4->5

 

prev = [-1 2 3 -1 4]

prev [0] : nums [0] (2) 이전에 아무 값도 없음

prev [1] : nums [1] (3) 3 앞에 2

prev [2] : nums [2] (4) 4 앞에 3

prev [3] : nums [3] (1) 1 앞에 아무 값도 없음

prev [4] : nums [4] (5) 5 앞에 4

 

마무리로 이제 5부터 prev를 역추적해서 따라가면

5 -> 4 -> 3 -> 2

이 배열을 뒤집으면 실제 LIS길이를 가지고 있는 배열을 추출할 수 있음

 

 

글 내용 중에 틀린 것이 있거나 궁금한 것이 있다면 댓글 남겨주세요! 봐주셔서 감사합니다.