백준 12015 LIS c++ // 이분탐색, LIS nlgn풀이 종결?, 한계

https://www.acmicpc.net/problem/12015

 

1. 설명

1. 기존 dp : O(n^2) // n개입력에대해 * 앞의n개를 살펴보며 최대값을 찾아야함

2. lower_bound : lb성질에 의해 n개입력 * lgn으로 구현쌉가능

 

2. 의사코드

1. num을 1개씩보면서

2. (lis에없는) 개큰수가 등장한경우, lis길이+1

3. 나머지는 lb성질에의해 날먹된다.

작은값이오면, 기존값을 작은값으로 교체함

 

i)작은값이옴 -> 10 20 30 에서 25in, idx=30, 30값이 25로 교체됨
ii)같은값이옴 -> 10 20 30 에서 20in, idx=20, 변화없음
iii)개큰값이옴 -> 10 20 30 [ ]에서 40in , idx=0, lis에 추가해줌

4. ex)

10 -> 저장, lis+1

20->저장, lis+1

10 -> 무시됨

30 -> 저장,lis+1

25 -> 30을 25로바꿔버림

50 -> 저장, lis+1

 

3. 전체코드

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n, lis[1000000+1], len, num;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> num;
        //1. num 이상인 idx를 찾음 -> 더 작은값이 들어오면, 작은값으로 교체함!
        //lis(현재의 증가수열길이) 중에서
        int idx = lower_bound(lis, lis + len, num) - lis;
        //i)작은값이옴 -> 10 20 30 에서 25in, idx=30, 30값이 25로 교체됨
        //ii)같은값이옴 -> 10 20 30 에서 20in, idx=20, 변화없음
        //iii)개큰값이옴 -> 10 20 30 [ ]에서 40in , idx=0, lis에 추가해줌

        if (lis[idx] == 0) len++; 
        //(lis에없는)개큰수가 등장한 경우, 맨뒤에 추가해줌, lis길이+1

        lis[idx] = num; 
        /*for (int j = 0; j < n; j++) {
            printf("%d ", lis[j]);
        }
        printf("\n");*/
    }
    cout << len;

    return 0;
}

 

4. 한계

lis의 길이만 구할뿐, 정답인 lis를 구할수 없다.

 

Arr[] = { 10 , 20 , 10 , 30 , 15 , 50 } 으로 바꿔서 진행해보자.

그럼 눈으로 딱 봤을 때, 가장 긴 증가하는 부분수열은 { 10 , 20 , 30 , 50 } 으로 길이가 4인 부분 수열이라는 것을

알 수 있다. 그럼 위의 코드로 실행을 해보면 다음과 같은 결과값이 나온다.

뭔가 조금 이상하다는 것을 눈치챌 수 있다. 우리가 하고자 하는 Arr에서는, 도저히 { 10 , 15 , 30 , 50 } 이라는 부분 수열을 찾을 수가 없음에도 불구하고, 위와 같은 배열이 나오게 된다.

LIS[] = { 10(3) , 20(5) , 30(4) , 50(6) } 이게 우리가 위에서 직접 하나하나 적절한 위치를 찾으면서 LIS를 구했을 때, 나온 결과값이다. 그런데 본인이 적어놓은 숫자뒤에 괄호들을 잘보자. 이 괄호가 의미하는 것을 다시한번 이야기하자면, "원본 배열에서 해당 숫자번째에 있엇던 값입니다." 를 의미한다.

그런데, 두 번째 있는 '20'이라는 값을 보자. 20(5)라고 적혀있다. 즉, 원본 배열에서 다섯 번째 있었던 값이였음을 의미한다.

그런데, 그 뒤에 있는 '30'은 ? 30(4)라고 적혀있다. 즉, 원본 배열에서 네 번쨰 있었던 값이였음을 의미한다.

잘못되도 단단히 잘못되었다. 우연히, '20'이라는 숫자가 중복되어서 나왔기 때문에, 얼핏 보기에는 제대로 나온 것 처럼 보였을 뿐, 실제로 그 '20'이라는 숫자를 '15'로 바꿔버리니까 위와 같은 결과가 나온 것이다.

그럼 이렇게 잘못된 배열이 구해짐에도 불구하고 길이가 항상 맞다고 판단되는 이유를 알아보자.

해당 숫자가, '15', '16', '17', .... '29' 까지 어떤 숫자가 와도 사실 상관이 없다. 왜 ?? 본인이 앞에서 나열한 저 숫자들은

바로, "그 전에 있는 10보다는 크고, 그 이후에 있는 30보다는 작은 값들" 이기 때문이다

출처: https://yabmoons.tistory.com/560 [얍문's Coding World..:티스토리]

 

5. 한계 해결

마지막으로, 실제로 LIS수열을 제대로 출력하기 위해서는 또 다른 방법이 필요한데, 이 방법은 다음 문제를 참고하면 해결할 수 있다.

[ 백준 - 가장 긴 증가하는 부분수열5(14003) 문제 바로가기 ]

[ 백준 - 가장 긴 증가하는 부분수열5(14003) 풀이 바로가기 ]]

 

 

6. len 증가시키는 로직 점검

이문제는 Ai가 1부터시작하기 때문에

if(lis[idx]==0) 이 해당 num이 처음등장하는 개큰수임 과 필요충분조건이 된다

하지만, Ai에 0이 있는경우 이 '0'이 처음등장한다는 의미인지 lis안에 계산된 '0'이 라는 의미인지 불명확하다!!!

// https://www.acmicpc.net/problem/14003 

따라서, if(idx == len) 이렇게 하는것이 Ai의 범위에 상관없이 처음등장하는 개큰수라는 것과 필요충분조건이다!!

//lb 성질에 의해 없는수를 찾으면 v.end()==len를 반환함!!

 

7. 24.6.20. 추가

리트코드를 복습하면서 깨달은점 정리

- lis 배열탐색시, 탐색범위는 전체가아님, lis+len까지로 제한해야함에 주의

- 10 20 30 25 예시를 보면서 해보면 좋음

: 10

10 20

10 20 30

10 20 25

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> lis(2504,0);
        int len=0;
        for(auto i : nums){
            //탐색범위를 제한해야함에주의!, lis전체가아님
            int idx = lower_bound(lis.begin(),lis.begin()+len,i)-lis.begin(); 
            
            if(idx==len){ //기존에없던 개큰수가 등장한경우
                len++;
            }
            lis[idx]=i; //기존값을 더 작은값으로 교체
        }
        return len;
    }
};