[ 백준 12738 ] 가장 긴 증가하는 부분 수열3 (C++)

백준의 가장 긴 증가하는 부분 수열3(12738) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

기존에 굉장히 비슷한 문제에 대한 글을 포스팅 한 적이 있다.

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

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

이 문제는 위의 11053번 문제와 동일한 문제이다.

그래서 위에 링크를 걸어놓은 11053번 문제 풀이를 해놓은 코드 그대로 테스트를 해보면 정답조차 제대로 나온다.

하지만 제출을 하게 되면 시간초과가 발생하게 된다.

왜냐하면 이 문제는 11053문제와 달리, 주어지는 배열의 최대 크기가 1000000이기 때문이다.

따라서, 기존의 풀이 방식인 O(N^2)이 걸리는 방식으로는 해결할 수 없는 문제이다.

그래서 지금부터는 O(NlogN) 시간으로 이 문제를 해결해보자.

우리는 주어진 배열에서 "증가하는 부분 수열"을 새로 만들어서 저장할 것이다.

그럼 이 새로 저장하는 배열의 이름을 LIS[] 라고 표현해보자. 그리고 원래 주어진 배열은 Arr[] 라고 표현하겠다.

[ LIS = Longest Increasing Subsequence : 최장 증가 부분 수열 의 줄인말 입니다. ]

그리고 주어진 예제입력인 [ 10 , 20 , 10 , 30 , 20 , 50 ] 을 Arr로 두고 진행해보자.

현재 LIS 배열은 비어있는 상태이고, Arr[] = { 10 , 20 , 10 , 30 , 20 , 50 } 인 상태이다.

지금부터 할 진행과정은 다음과 같이 2단계로 나눠서 설명할 수 있다.

1. 우리는 현재 Arr에 있는 값을 반드시 LIS 배열에 삽입해줄 것이다.

2. 1)의 과정을 진행할 때, LIS배열의 상태는, "증가하는 부분 수열"의 규칙에 어긋나지 않게, LIS 배열의 상태를

   보면서, "적.절.한.위.치"를 찾으면서 값을 재설정하거나, 값을 삽입해 줄 것이다.

위의 2단계가 정확하게 무슨 말인지 몰라도 좋다. 일단 진행해보자.

가장 먼저, 처음에 나온 숫자 '10'을 보자.

우리는 이 '10'이라는 숫자를 LIS 배열에 넣고 싶다. 어디에 넣으면 될까 ??? 가장 처음에 넣으면 된다.

왜 ? '10'이 들어갈만한 적절한 위치를 LIS배열에서 찾아야 하는데, 현재 LIS배열은 아무런 값도 들어있지 않은 빈 배열이다.

따라서 가장 처음에 넣어주면 된다. 그럼 LIS배열이 다음과 같이 설정될 것이다.

LIS[] = { 10(1) }

위의 적어놓은 배열의 값에서 10(1) 로 표현한 것은, 이후에 진행할 과정에서 '10'이 또 한번 나오기 때문에, 그 때 나오는 '10'과 구분하기 위해서 "Arr배열에 1번 Index에 있었던 10입니다" 라고 표현해놓은 것이다.

지금부터는 LIS배열에 들어가는 값들은 모두 저렇게 표현하도록 하겠다.

두 번째 숫자, '20'을 보자.

우리는 이 '20'을 LIS배열의 적절한 위치에 넣고 싶다. 어디에 넣으면 될까 ?? 현재 LIS 배열은 { 10 } 이기 때문에, 증가하는 부분 수열의 규칙을 어긋나지 않게 하기 위해서는, 10 이후에 넣어주어야 한다.

그럼 10 이후에 넣어주자.

LIS[] = { 10(1) , 20(2) }

세 번째 숫자, '10' 을 보자.

우리는 이 '10'을 LIS배열에 넣을 것인데, 증가하는 부분 수열의 규칙에 어긋나게 삽입을 하면 안된다.

그럼 어디에 넣어주어야 할까 ?? 일단 LIS[] = { 10 , 20 } 인데, 가장 마지막에 들어가는 것은 조금 별로인 것 같다. 왜냐하면 증가하는 부분 수열의 규칙이 어긋나버리기 때문이다. 규칙을 유지하기 위해서는 최소 '20'보다는 이전에 삽입되어야 한다.

그런데, '20'전에는 '10' 하나밖에 없다. 즉, 들어갈 공간이 한 자리 밖에 없다는 것이다.

그럼 우리가 위에서 말했던 2단계 과정 중, 2단계에서 했던 마지막 말을 다시한번 보자.

"적절한위치를 찾으면서, 값을 '재설정' 하거나 값을 삽입해줄 것이다."

즉 ! 우리가 세 번째 숫자인 '10'에서 찾은 적절한 위치는 LIS배열의 가장 첫 번째 위치이다.

즉, 첫 번째 값을 현재 숫자로 재설정 해주자. 그럼 LIS 배열은 다음과 같이 변할 것이다.

LIS[] = { 10(3) , 20(2) }

네 번째 숫자, '30' 을 보자.

'30'에 적절한 위치를 찾아보니, 가장 마지막에 넣어주면 될 것 같다. 그렇게 넣어주더라도, 규칙에 어긋나는 상황이 발생하지 않기 때문이다.

LIS[] = { 10(3) , 20(2) , 30(4) }

다섯번째 숫자, '20' 을 보자.

'20'의 적절한 위치를 찾아보니, LIS배열에서 1번째 값인 '10'보다는 큰 값이고, '3번째 값인 '30'보다는 작은 값이다.

즉 ! '30'보다는 이전에 들어가야하고, '10'보다는 이후에 들어가야 하는 것이다.

그렇게 적절한 위치를 찾아보니, 2번 Index밖에 존재하지 않는다. 그런데 2번 Index의 값과 비교해보니, 동일한 값이다.

그럼, 2번 Index의 값을 현재 숫자로 재설정 해주자. 그럼 LIS 배열은 다음과 같이 변할 것이다.

LIS[] = { 10(3) , 20(5) , 30(4) }

마지막 숫자, 50을 보자.

'50'의 적절한 위치를 보니, 가장 마지막에 넣어주면 될 것 같다.

LIS[] = { 10(3) , 20(5) , 30(4) , 50(6) }

이렇게 우리는 LIS배열을 완성시켰다. 길이를 보니, 4가되고, 실제로 이 문제의 정답은 4가 맞다.

그럼 이제 대충 어떻게 값을 설정하는지는 알았으니, 본격적으로 값을 찾는 과정에 대해서 이야기해보자.

위에서 설명한 예시는, 너무나도 간단한 예시이고, 배열의 크기도 6밖에 되지 않아서 사실 눈으로만 보더라도 이 숫자가 어디에 들어가야 되는구나 라고 알 수 있었다. 즉 ! 위에서 언급한 "적절한 위치를 찾아가면서" 이 과정이 너무나도 간단하게 표현되어 있다. 하지만, 이 문제의 핵심은, "적절한 위치를 찾는데 걸리는 시간을 최소화 시키는 것" 이다.

실제로, 이 적절한 위치를 단순하게, 하나의 값을 탐색할 때 마다, LIS배열 전체를 순회한다면 이 또한 굉장히 오랜 시간이 걸릴 것이다.

따라서, 이 과정을 "이분탐색(Binary Search)" 를 이용해서 구현하는 것이다.

이분탐색을 하기 위해서는 한 가지 조건이 있다. 바로, 탐색을 하려는 대상이 "정렬되어 있는 상태"여야 한다는 것이다.

그런데 ! LIS 배열을 보자. LIS배열은 우리가 "증가하는 부분 수열"의 규칙에 어긋나지 않도록 값을 삽입해 주었기 때문에, 단 한번도 정렬이 안되었었던적이 없다. 항상 정렬이 되어 있는 상태이다.

그럼, 이 부분을 먼저 코드로 한번 같이 확인을 해보자.

코드를 보기전에, 본인은 위에서 설명한 LIS배열을, Vector를 이용해서 구현해 주었다.

void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        if (V.size() == 0 || V[V.size() - 1] < Arr[i]) V.push_back(Arr[i]);
        else
        {
            int Left = 0;
            int Right = V.size() - 1;
            while (Left < Right)
            {
                int Mid = (Left + Right) / 2;
                if (V[Mid] >= Arr[i]) Right = Mid;
                else Left = Mid + 1;
            }
            V[Left] = Arr[i];
        }
    }
    cout << V.size() << endl;
}

이 코드가 본인이 구현한 코드이다.

위의 코드에서 'V'라는 변수는 LIS배열을 대체한 Vector이고, Arr는 주어진 입력 값을 저장해놓은 배열이다.

line5)에서 보면, 2가지 조건문이 달려있다.

1. Vector가 비어있는 상태일 경우

- 즉, 우리가 가장 처음에 '10'을 넣었을 때와 같은 상황이다. LIS배열이 처음 비어잇을 때는, 비교할 대상도 없었고, 찾아야 할

  적절한 위치같은 것도 없었다. 무조건 그냥 가장 처음에 넣어주면 되었었다. 이 경우를 의미하는 조건문이다.

2. Vector의 마지막 값이, 현재 값보다 더 작을 경우

- Vector는 LIS배열과 동일한 역할을 하는 친구이다. 즉 ! LIS배열은 "오름차순"으로 정렬된 상태로, 값이 차곡차곡 쌓이고 있는

  상태일 것이다. 그런데, 현재 삽입하려는 값이 LIS배열의 가장 마지막 값 보다 더 크다면 ?? 이 경우에는 적절한 위치를

  찾을 필요 없이, 가장 마지막에 넣어주더라도 "증가하는 수열"이라는 규칙에 어긋나지 않게 된다.

따라서 위와 같이 2가지 조건 중 하나라도 걸리게 되면, Vector에 단순 값을 push하는 과정을 확인할 수 있다.

문제는 line6 ~ 17) 에 있는 "적절한 위치를 찾아야 되는 경우" 이다.

line10 ~ 15)를 보게 되면, 이분 탐색을 통해서 LIS배열에서 적절한 위치를 찾고 있는 것을 확인할 수 있다.

적절한 위치를 찾아서, 이분 탐색이 종료되었다면, line16)을 통해서 값을 재설정 해주는 과정을 하고 있는 것이다.

위에서 보면, 중간에 LIS배열이 { 10(1) , 20(2) } 에서, { 10(3) , 20(2) } 와 같이, 재설정 되는 과정이 있었다.

그 과정을 진행한 것이다.

그리고 최종적으로 LIS배열의 크기를 의미하는, V.size()를 출력하게 해주면 이 문제를 pass를 받을 수 있다.

이분탐색은 기본적으로 절반씩 나눠가면서 탐색을 하기 때문에 시간복잡도로 표시하면 O(logN) 만큼의 시간이 걸린다고 할 수 있다. 그런데, 이 과정을 최악의 경우 N번동안 진행해야 하기 때문에 전체 시간복잡도는 O(NlogN) 이 된다.

이런 방법을 이용해서 이 문제를 해결할 수 있다.

그리고 본인이 한 것과 같이, 직접 이분탐색 하는 과정을 구현해도 상관없지만 많은 분들이 이부분에서 유용하게 사용하는 함수가 lower_bound() 라는 함수이다. <algorithm> 헤더를 추가하면 사용할 수 있는 STL에서 제공해주는 함수인데, lower_bound에 대해서도 간단하게만 알아보자.

# lower_bound()

lower_bound는 3개의 인자를 필요로한다.

lower_bound(시작범위 , 끝 범위 , 찾고자 하는 값)

이렇게 3개의 인자를 필요로 하는데, lower_bound(Start, End, Key) 를 실행시켰을 때, 반환되는 값은

"주어진 범위(Start ~ End) 에서, Key값 이상인 첫 번째 원소의 위치를 반환" 하게 된다.

그럼 우리가 위에서 진행했던 풀이 중, 다섯번째 값인 '20'을 lower_bound로 한번 찾아보자.

우리가 다섯번째 값을 구하기 전까지, LIS배열의 상태는 { 10(3) , 20(2) , 30(4) } 였다.

이 상태에서, lower_bound를 호출하려면 lower_bound(0 , 2 , 20) 으로 호출할 수 있을 것 같았지만, 사실은 이렇게 호출은 되지 않는다. lower_bound는 iterator값을 이용해서 범위를 입력받고, iterator값을 return 하는 자료구조 이기 때문이다.

즉, 주어진 객체에 대한 범위를 포인터 변수를 이용해서 입력 받고, return 또한 적절한 위치를 iterator로 하게 된다.

따라서 lower_bound(Start, End, Key) 에서, 'Start'와, 'End'는 int형이 아닌, iterator 값으로 입력을 해주어야 한다.

vector  같은 경우에는 V.begin() , V.end() , 배열 같은 경우에는 Arr + 1 , Arr + 10 뭐 이런식으로 호출을 해 주어야 한다.

그럼 찾아보면, '20'이상인 첫 번째 원소는 '1'이 된다. 왜냐하면, 1번 Index에 '20'이라는 숫자가 존재하고, 이 '20'이라는 숫자가 우리가 찾고자 하는 '20' 이상인 숫자 중, 가장 첫 번째 원소이기 때문이다. 이런식으로 이분탐색을 직접 사용하지 않고도 lower_bound라는 함수를 이용해서도 찾을 수 있다.

lower_bound() 함수 또한, 내부적으로는 이분탐색을 베이스로 하는 자료구조로 알고 있다. 주의해야 할 점은 반환형이 int형이 아니라는 것이다. 단순히, int A = lower_bound(0 , 2 , 20) 이라는 식이 성립자체가 불가능하다는 것이다.

왜냐하면, lower_bound()의 반환형은 'iterator' 이기 떄문이다. 바로, 주소값을 가르키고 있는 포인터 변수가 반환된다는 것이다. 따라서, 이를 다시 int형으로 바꿔서 Index값을 찾기 위해서는 해당 자료만큼을 빼주는 연산을 진행해주면 된다.

즉, 벡터 같은 경우는, int A = lower_bound(V.begin() , V.end() , 20) - V.begin()

배열같은 경우는, int A = lower_bound(Arr , Arr + 범위 , 20 ) - Arr 와 같은 식으로 구현을 하면 int형으로 return을 받을 수 있게 된다.

따라서 위와 같은 방법을 이용하면 이 문제를 O(NlogN) 시간 안에 해결할 수 있게 된다.

그럼 지금부터는, 이 문제와는 상관이 없지만, 조금은 의아하고도 신기한 내용에 대해서 조금 이야기해보고자 한다.

우리가 진행했던 Arr[] = { 10 , 20 , 10 , 30 , 20 , 50 } 에 대해서 위의 과정을 진행한 후, 최종적으로 "가장 긴 증가하는 부분 수열의 길이"만 출력하는 것이 아니라, 실제로 "가장 긴 증가하는 부분 수열"을 출력해보자.

어디에 저장되어있는데 ? 바로 LIS배열에 저장되어 있으니, 해당 배열을 출력해보자.

본인이 설명한 위의 코드에서는 Vector로 구현되어 있으니, 다음과 같이 한번 출력을 해보겠다.

void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        if (V.size() == 0 || V[V.size() - 1] < Arr[i]) V.push_back(Arr[i]);
        else
        {
            int Left = 0;
            int Right = V.size() - 1;
            while (Left < Right)
            {
                int Mid = (Left + Right) / 2;
                if (V[Mid] >= Arr[i]) Right = Mid;
                else Left = Mid + 1;
            }
            V[Left] = Arr[i];
        }
    }
    cout << V.size() << endl;
    for (int i = 0; i < V.size(); i++) cout << V[i] << " ";
    cout << endl;
}

위의 코드를 한번 실행시켜 보겠다.

그럼 출력결과는 다음과 같다.

.

아무런 문제가 없어보인다. 그럼 여기서 배열의 값을 하나만 바꿔보겠다.

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

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

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

.

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

더 이상한 것은, 이 문제에서는 위의 코드를 제출해도 맞았습니다를 받을 수 있다는 것이다.

도대체 왜그럴까 ???

바로, 이 문제에서는 "가장 긴 증가하는 부분수열의 길이만" 구하면 되기 때문이다. 실제 그 증가하는 부분 수열이 어떻게 구현되어있는지는 이 문제와는 상관이 없는 내용이다. 이 문제에서는 가장 긴 증가하는 부분수열의 길이만 구하면 된다.

따라서, 위의 코드는 제출을 해도 맞았습니다를 받을 수 있다. 그럼 왜 맞았습니다를 받을 수 있을까 ??

실제로 배열을 계산해서 증가하는 부분 수열을 구해보니까, 엉뚱한 배열이 나오는데, 그 길이는 항상 맞다고 판단이 되는 상황인 것이다.

결과부터 말하자면 "길이에는 영향을 미치지 않기 때문" 이다.

그럼, 다시 돌아가보자. 우리가 입력받은 데이터는 Arr = { 10 , 20 , 10 , 30 , 15, 50 } 이고, 이 때, 증가하는 부분수열을 구해보니, { 10 , 15 , 30 , 50 } 이 나온 상황이다.

그런데 왜 Arr[] = { 10 , 20 , 10 , 30 , 20 , 50 } 일 때는 제대로 나왔을까 ?? 왜 어떤 경우에는 제대로 나오고 어떤 경우에는 제대로 나오지 않을까 ?? 사실 우리가 위에서 진행했던 { 10 , 20 , 10 , 30 , 20 , 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보다는 작은 값들" 이기 때문이다. 그 사이에 있는 값이 저 값들로 재 설정 될 뿐이지, 값과 값 사이에 새로운 값이 공간을 비집고 들어가서 전체 크기를 늘려버리는 상황이 아닌 것이다.

따라서, 기존의 값에서 값이 "규칙을 유지한 채, 재설정"될 뿐이기 떄문에 전체 길이에는 영향을 미치지 않는다.

그래서 이 문제에서는 실제로 출력해보면 올바른 증가하는 부분 수열이 나오지 않음에도 불구하고, 길이만 출력하면 되기 때문에 정답을 받을 수 있는 것이다.

이 글을 정리해보자.

1. O(N^2)에 걸리는 시간복잡도로는 문제를 해결할 수가 없다.

2. 새로운 공간에, LIS 수열을 따로 저장할 것인데, Vector를 사용하든, Arr를 사용하든 상관이 없다.

3. 핵심은 "적절한 위치"를 찾는 것인데, 이 때, 이분탐색을 사용하거나, lower_bound() 함수를 사용해서

   구할 수 있다. 이러한 탐색 방법을 사용하게 되면 O(logN) 만에 찾을 수 있다.

4. 실제로, 구한 LIS수열을 출력해보면 올바르지 않은 배열이 나오지만, 길이만 출력하면 되는 이 문제에서는

   상관없이 pass를 받을 수 있다.

5. 따라서, 실제 LIS수열을 출력하기 위해서는 또 다른 방법이 필요하다.

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

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

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

[ 이분탐색 구현한 소스코드 ]

#include <iostream>
#include <vector>
#define endl "\n"
#define MAX 1000010
using namespace std;
 
int N;
int Arr[MAX];
vector<int> V;
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        if (V.size() == 0 || V[V.size() - 1] < Arr[i]) V.push_back(Arr[i]);
        else
        {
            int Left = 0;
            int Right = V.size() - 1;
            while (Left < Right)
            {
                int Mid = (Left + Right) / 2;
                if (V[Mid] >= Arr[i]) Right = Mid;
                else Left = Mid + 1;
            }
            V[Left] = Arr[i];
        }
    }
    cout << V.size() << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}

[ lower_bound() 함수를 이용한 소스코드 ]

#include <iostream>
#include <vector>
#include <algorithm>
#define endl "\n"
#define MAX 1000010
using namespace std;
 
int N;
int Arr[MAX];
vector<int> V;
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++) cin >> Arr[i];
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        if (V.size() == 0 || V[V.size() - 1] < Arr[i]) V.push_back(Arr[i]);
        else
        {
            int Pos = lower_bound(V.begin(), V.end(), Arr[i]) - V.begin();
            V[Pos] = Arr[i];
        }
    }
    cout << V.size() << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}