728x90

 0. [c++] 백준


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


 1. 풀이


1) 동적계획법을 활용한 풀이

우선 이 풀이는 O(N^2)의 풀이이다.

풀이 방법은 다음과 같다.

1. cache라는 배열은 cache[i] = i번째 수를 기준으로 만들 수 있는 LIS(Longest Increasing Subsequence, 가장 긴 증가하는 부분 수열)의 길이를 저장한다.

2. 이제 모든 경우에 대해서 탐색을 수행한다. 이때, 동적 계획법을 적용해준다.

3. 이 탐색의 횟수를 줄여주기 위해서 1번에서 설명한 cache를 활용해 메모이제이션을 적용한다.

이미 LIS를 탐색한 후라면 그 수는 더이상 탐색하지 않고 바로 반환을 하도록 해준다.

4. 이 과정을 반복하며 최종적으로 LIS를 구할 수 있게 된다.


하지만, 이와 같은 풀이는 N = 10^6 인 지금의 문제에서는 시간초과가 발생한다.

이를 막기 위해서 다른 방법이 필요할 것으로 보인다.


2) 이분 탐색을 활용한 풀이

그러면 어떤 방법을 적용해야 시간복잡도를 줄일 수 있을까?

사실 아이디어가 잘 나지 않아서 다른 블로그를 찾아보았는데 똑같은 메모이제이션을 활용하지만, 저장하는 데이터를 다르게 구현하는 것이었다.

포인트는 각 배열의 마지막 수를 저장해주는 것이었다.

이 마지막 수 메모이제이션은 vector<int> sequence를 활용해주었고

sequence[i] = 길이가 (i-1)인 배열에서 가장 큰 수

를 저장해주었다.



예를 들어보자.

10, 20 ,30, 25, 15, 60 이라는 배열이 문제로 주어진 경우이다. 이제 LIS를 탐색하는 과정은 아래와 같다.

1. sequence[0]에 10이 저장된다.

2. sequence[0](=10) < 20 이므로, sequence[1]에 20이 저장된다.

3. sequence[1](=20) < 30 이므로, sequence[2]에 30이 저장된다.

3. sequence[2](=30) > 25 이므로, 부분 수열의 길이를 증가시키는 것은 불가능하고, sequence[2]에 저장되어있던 30을 25로 치환해준다.

(길이가 3인 부분 수열중 가장 큰 수가 30에서 25로 변경된다.)

4. sequence[3](=25) > 15 이므로, 부분 수열의 길이를 증가시키는 것은 불가능하고, sequence[1]에 저장되어있는 20을 15로 치환한다.

5. sequence[3](=25) < 60 이므로, sequence[4]에 60이 저장된다.


최종적으로 sequence는 10, 15, 25, 60을 저장하게 된다.

그리고 이때 sequence의 크기가 LIS의 크기와 동일하게 된다.


이러한 과정을 아래 소스코드에 구현을 할 수 있었고, 탐색에 소요되는 시간을 줄이기 위해 이분 탐색을 적용해주었다.




 2. 소스코드


1. 기본적인 동적계획법을 활용한 풀이(허나 이와같이 해결하면 시간초과가 발생한다.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<algorithm>
#include<vector>
 
 
using namespace std;
 
int cache[1000001];
int arr[1000001];
int N;
 
int dp(int here) {
    int& ret = cache[here];
    if (ret != 0)
        return ret;
    ret = 1;
    for (int next = here + 1; next < N; next++) {
        if (arr[here] < arr[next])
            ret = max(ret, dp(next) + 1);
    }
 
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N;
    int ret = 0;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    for (int i = 0; i < N; i++) {
        ret = max(ret, dp(i));
    }
    cout << ret;
    return 0;
}
cs





2. 반복문과 이분 탐색을 활용한 풀이

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int arr[1000001];
vector<int> sequence;
int N;
 
void binary_search(int num) {
    int low = 0, high = sequence.size()-1, mid;
    int ret = 1000000007;
    while (low <= high) {
        mid = (low + high) / 2;
        int here_num = sequence[mid];
        if (here_num >= num) {
            if (ret > mid)
                ret = mid;
            high = mid - 1;
        }
        else
            low = mid + 1;
    }
 
    sequence[ret] = num;
}
 
void find_lis() {
    sequence.push_back(arr[0]);
    for (int i = 1;i < N;i++) {
        if (sequence.back() < arr[i]) {
            sequence.push_back(arr[i]);
        }
        else {
            binary_search(arr[i]);
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    find_lis();
 
    cout << sequence.size();
 
    return 0;
}
cs





 3. 참고


https://seungkwan.tistory.com/8


질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!


저작자표시

'<백준> > 이분 탐색' 카테고리의 다른 글

[C++] 백준 2110 - 공유기 설치(이분 탐색, 무식하게 풀기, brute force, binary search)  (0) 2020.02.10
[C++] 백준 2805 - 나무자르기(이분 탐색, 이진 탐색, binary search)  (0) 2020.02.10

+ Recent posts

티스토리툴바