[BaekJoon 11722번] 가장 긴 감소 부분 수열(C++)

※주의※

저의 풀이가 정답은 아닙니다.

다른 코드가 더 효율적이거나 좋을 수 있습니다.

언제나 다른 사람의 코드는 참고만 하시기 바랍니다.

 

 

[문제 풀이 사이트]

 

 

11722번: 가장 긴 감소하는 부분 수열

 

 

[문제 설명]

 

 

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

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

 

 

[입력]

 

 

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

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

 

 

[출력]

 

 

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

 

 

[입출력 예]

 

 

입력	출력
6 10 30 10 20 20 10	3

 

 

[문제 풀이]

 

 

문득 미용실에서 머리를 하면서 멍 때리고 있다가

최장 감소 부분 수열도 있을텐데 얘는 어떻게 구현해야할까? 라는 생각이 들었다.

 

최장 증가 부분 수열의 경우 lower_bound를 사용하여 찾고자 하는 값보다 같거나 큰 위치를 반환하여 값을 대체함으로서 오름 차순으로 구현할 수 있었는데 최장 감소 부분 수열의 경우는 어떻게 해야할까?

 

그래서 upper_bound 생각도 했는데, 사용 전제 조건이 vector 또는 배열이 기본적으로 오름 차순 정렬되어 있어야하고 찾고자 하는 값보다  큰 위치를 반환하기 때문에 최장 감소 부분 수열을 만들기에는 부적합하다.

 

내가 생각해낸건 lower_bound의 4번째 인자인 compare 함수를 사용하기로 했다.

template< class ForwardIt, class T, class Compare >
ForwardIt lower_bound( ForwardIt first, ForwardIt last, const T& value, Compare comp );

그렇다면 사용 전에 기본 lower_bound 동작을 확인하자.

 

기본 lower_bound의 comp 함수는 아래와 같다

template <typename T>

bool comp(const T& a, const T& b) 
{
	return a < b;
}

첫번째 파라미터('a')가 배열의 원소를 의미하고 두번째 파라미터('b')가 찾고자하는 값이 되는데,

탐색을 하며 false가 되는 순간 해당 위치의 인덱스를 반환한다.

 

그렇다면 기본 동작 이해를 위해 {2, 3, 7, 5, 6} 수열에서 최장 증가 부분 수열을 구하는 예를 들어보도록 하겠다.

1. {2} = 길이 1

2. {2, 3} = 길이 2

3. {2, 3, 7} = 길이 3

까지 끝내고 

 

수열의 앞에서 부터 차근차근 comp함수로 비교하게 될 것이다.

2와 5를 비교했을 때 comp 함수에서 true이기 때문에 패스

3과 5를 비교했을 때 comp 함수에서 true이기 때문에 패스

7과 5를 비교했을 때 comp 함수에서 false 이기 때문에 해당 위치(7)의 인덱스를 반환한다.

그래서 반환한 인덱스의 값을 7에서 5로 값을 바꾼다.

 

4. {2, 3, 5} = 길이 3

5. {2, 3, 5, 6} = 길이 4

최종 길이가 4인 최장 증가 부분 수열을 구할 수 있다.

 

위 내용을 바탕으로 입출력 예시 소개가 되어있는 {10, 30, 10, 20, 20, 10} 수열을 최장 감소 부분 수열을 구하는 예를 들어보도록 하겠다.

1. {10} = 길이 1

 

이제, 30을 탐색할 차례이다. 

 

현재 최장 감소 부분 수열을 만들기 위해서 30은 10과 대체되어야 한다.

최장 증가 부분 수열처럼 기본 lower_bound를 사용하면 안된다.

lower_bound 의 comp 함수를 조금만 손보면 되는데, 아래와 같이 만들어줘야한다.

template <typename T>
bool comp(const T& a, const T& b) {
    return  a > b;
}

 

위 내용을 바탕으로 설명을 이어나가자면

첫번째 파라미터는 10이 들어가게 되고, 2번째 파라미터는 30이 들어가게 된다.

10과 30을 비교했을 때  false 이기 때문에 해당 위치(10)의 인덱스를 반환한다.

그래서 반환한 인덱스의 값을 10에서 30으로 바꾼다.

 

2. {30} = 길이 1

3. {30, 10} = 길이 2

 

이제 20을 탐색할 차례이다.

위 10, 30에서 처럼 같은 내용이 적용 되어 아래와 같이 바뀐다.

4. {30, 20} = 길이 2

 

이제 20을 탐색할 차례이다.

값이 같은 경우에도 false 이기 때문에 해당 위치(20)의 인덱스를 반환하고,

반환한 인덱스의 값을 20에서 20으로 바꾼다.

5. {30, 20} = 길이 2

6. {30, 20, 10} = 길이 3

 

그래서 최장 감소 부분 수열의 길이는 3으로 구할 수 있다.

 

아니면 생각하기 쉽게(그냥 암기하란 뜻) 4번째 파라미터 값이

less<자료형>() 이면 최장 증가 부분 수열 (오름 차순)

greater<자료형>() 이면 최장 감소 부분 수열 (내림 차순)

이라고 생각하면 쉬울 것 같다.

 

마치 sort 함수의 오름 차순과 내림 차순 처럼 말이다.

 

 

[최종 코드]

 

 

[GitHub]

 

 

GitHub - SmallPeanutPark/BAEKJOON: Study BaekJoon for Coding Test

 

 

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

vector<int> LDS;

bool comp(const int &a, const int& b) {
    return a > b;
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int N; cin >> N;
    for(int i = 0; i < N; ++i) {
        int n; cin >> n;
        if(LDS.empty()) {
            LDS.emplace_back(n);
        } else {
            if(LDS.back() > n) {
                LDS.emplace_back(n);
            } else {
                auto location = lower_bound(LDS.begin(), LDS.end(), n, comp);
                *location = n;
            }
        }
    }
    cout << LDS.size();
    return 0;
}