[C++] 백준 온라인 저지 11053번 가장 긴 증가하는 부분 수열 풀이

가장 긴 증가하는 부분 수열의 길이를 구하는 문제

 

---

 

문제의 조건

 

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

 

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

 

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

 

 

풀이 과정

 

 가장 긴 증가하는 부분 수열 자체를 몰랐기 때문에... 처음엔 예제만 보고 무식하게 배열 정렬하고 중복제외 한 길이를 출력했습니다. 당연히 시작하자마자 실패 ㅋㅋㅋㅋㅋㅋㅋ 주륵... 구글링을 통해 알고리즘 공부를 하고 난 후 풀 수 있었습니다. 

 

1. 가장 긴 증가하는 부분 수열은 정렬하는 것이 아니다. 정렬되지 않은 상태에서 중간에 있는 어떤 원소들을 제외했을 때 원소들이 오름차순으로 정렬되면서 그 길이가 가장 긴 것이어야 한다. 

* 참고 링크 :  https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4

 

알고리즘 두 가지에 대해 비교적 친절하게 자세히 설명되어 있다. 

 

2. 가장 긴 증가하는 부분 수열을 찾기 위한 알고리즘 중 log(n log n) 복잡도를 갖는 알고리즘을 쓰는 것이 시간 효율성이 좋기 때문에 이 알고리즘을 작성한다. 지금까지 저장한 LIS 길이별 가장 작은 원소값을 갱신하기 위해서 binary search가 필요하다. 

* 이진 탐색 참고 링크 : https://chanhuiseok.github.io/posts/algo-49/

알고리즘 - 최장 증가 부분 수열(LIS) 알고리즘

 

3. 입력받은 배열을 탐색하면서 최장 증가 부분 수열을 구한다. 

 

 STL에 있는 이진탐색 함수도 써 보고 싶어서 lower_bound 함수로도 풀어보았습니다. 

* STL 이진탐색 참고 링크 : https://chanhuiseok.github.io/posts/algo-55/

알고리즘 - c++ lower_bound, upper_bound 활용하기

 

 어휴 이 분 없었으면 못 풀었다 정말;;

 

 

코드

 

이진 탐색 함수를 만들어서 푼 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int BinarySearch(vector<int>& LIS, int left, int right, int target)
{
    int mid;
    
    //left와 right가 만날 때까지 target이 들어갈 자리를 찾는다. 
    while (left < right)
    {
        mid = (left + right) / 2;
        //target이 현재 중간값보다 크면 left를 증가시킨다. 
        if (target > LIS[mid])
            left = mid + 1;
        //작으면 right를 감소시킨다. 
        else
            right = mid;
    }
    
    return right;
}

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    
    vector<int> numbers(N, 0);
    for (int i = 0; N > i; i++)
        cin >> numbers[i];
    
    vector<int> LIS(1, 0);
    LIS.emplace_back(numbers[0]);
    for (int i = 1; numbers.size() > i; i++)
    {
        //현재 원소가 LIS의 마지막 값보다 크면 그 값 뒤에 이어붙일 수 있기 때문에 push back한다. 
        if (LIS.back() < numbers[i])
            LIS.emplace_back(numbers[i]);
        else
        {
            //아니라면 LIS 배열 원소 중 현재 원소보다 크거나 같은 첫번째 값을 현재 원소로 바꿔줘야 한다.
            //이진탐색으로 들어갈 인덱스를 찾는다. 
            int index = BinarySearch(LIS, 0, LIS.size() - 1, numbers[i]);
            LIS[index] = numbers[i];
        }
    }
    
    //인덱스 번호가 최장 길이니까 총 길이에서 1을 뺀 값을 출력 
    int answer = LIS.size() - 1;
    cout << answer;
    
    return 0;
}

 

lower_bound 함수를 쓴 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    
    vector<int> numbers(N, 0);
    for (int i = 0; N > i; i++)
        cin >> numbers[i];
    
    vector<int> LIS(1, 0);
    LIS.emplace_back(numbers[0]);
    for (int i = 1; numbers.size() > i; i++)
    {
        if (LIS.back() < numbers[i])
            LIS.emplace_back(numbers[i]);
        else
        {
            //현재 원소보다 크거나 같은 숫자가 나오는 첫번째 인덱스를 찾기 위해 
            //lower_bound 함수 사용 
            int index = distance(LIS.begin(), 
                lower_bound(LIS.begin(), LIS.end(), numbers[i]));
            LIS[index] = numbers[i];
        }
    }
    
    int answer = LIS.size() - 1;
    cout << answer;
    
    return 0;
}