[Baekjoon Online Judge] 백준 12015번 가장 긴 증가하는 부분 수열 2(C++, Python)

© 2020 All Rights Reserved. 주식회사 스타트링크

[Baekjoon Online Judge] 백준 12015번

가장 긴 증가하는 부분 수열 2

(C++, Python)

(글쓴날 : 2020.04.20)

 

---

* Baekjoon Online Judge, 백준 12015번 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

백준 12015번 가장 긴 증가하는 부분 수열 2

---

1) 문제

문제 링크 : https://www.acmicpc.net/problem/12015

12015번: 가장 긴 증가하는 부분 수열 2

---

2) 풀이 과정

* 시간 복잡도 : O(n log n)

 

수열 A가 주어질 때, 가장 긴 증가하는 부분 수열을 구하는 문제입니다.

 

저의 경우, 이분 탐색을 적용하였으며, C++과 Python을 사용했습니다.

이 문제는 수열의 크기가 최대 1,000,000이므로, 기존 LIS를 구하는 방식의 시간 복잡도가 O(n²)인 동적 계획법을 적용할 시, 시간 초과가 발생합니다.

따라서, 다른 방법을 사용해야 하는데 아무리 고민해도 시간 복잡도를 줄일 방법이 도저히 떠오르지 않아 풀이를 검색했습니다...

 

검색 결과, 이 문제의 정해는 두 가지 방식이 있는데, 세그먼트 트리와 이분 탐색입니다.

둘 중에서 그동안 다른 문제에서도 적용해 보았던 이분 탐색을 선택해 적용하였으며, 이분 탐색 방식 중에서도 lower_bound 방식을 사용해야 했습니다.

lower_bound의 경우 C++의 STL에 이미 구현되어 있지만, 공부할 겸 로직을 직접 구현하여 문제를 해결했습니다.

 

풀이는 아래의 제가 참고한 블로그와 같습니다.

 

* 참고 블로그 : https://jason9319.tistory.com/113

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <vector>
 
using namespace std;
 
int A[1000001];
 
int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int N = 0;
    cin >> N;
 
    for (int i = 0; i < N; i++)
        cin >> A[i];
 
    vector<int> LIS;
    LIS.push_back(0);
 
    int length = 0;
    int left = 0;
    int right = 0;
    int mid = 0;
 
    for (int i = 0; i < N; i++)
    {
        if (A[i] > LIS.back())
        {
            LIS.push_back(A[i]);
            length++;
        }
        else
        {
            left = 0;
            right = LIS.size();
 
            while (right - left > 0)
            {
                mid = (left + right) / 2;
 
                if (LIS[mid] < A[i])
                    left = mid + 1;
                else
                    right = mid;
            }
 
            LIS[right] = A[i];
        }
    }
 
    cout << length;
 
    return 0;
}

---

* Python 코드

import sys
input = sys.stdin.readline
 
N = int(input())
A = list(map(int, input().split()))
LIS = [0]
length = 0
 
for num in A:
    if num > LIS[-1]:
        LIS.append(num)
        length += 1
    else:
        left = 0
        right = len(LIS)
 
        while right - left > 0:
            mid = (left + right) // 2
 
            if LIS[mid] < num:
                left = mid + 1
            else:
                right = mid
 
        LIS[right] = num
 
print(length)

---