이 포스팅을 보고 많은분들이 LIS에 대해서 아! 하시고 창을 닫으시길 바라며 

포스팅을 해보겠습니다. 

물론 제가 올린 내용중 문제가 되는 부분이 있다면 언제든지 댓글로 남겨주시면 환영입니다!
( 필자는 아직 좁밥이므로 갓들의 지적속에 자라나고 있습니다 )

n사이즈의 배열에서 일부 원소들을 뽑아내어 부분수열을 만들어 내었을때 

증가하는 수열이 되도록 할때, 가장 긴 길이를 구하는 문제를 LIS라고 합니다. 

Dynamic Programming에서 빈번하게 등장하는 문제로 알고있으며 실제로 감소하는 수열도 존재합니다.

예를 들어 [5, 2, 3, 7, 4, 1] 이라는 배열이 있다고 해보겠습니다. 

먼저 이 배열에서 가장 긴 증가하는 부분수열을 뽑아낸다고 한다면, [2, 3, 4,]를 뽑아낸

길이 3이 LIS의 길이가 됩니다. 

문제에 대한 설명에 앞서 

인덱스 트리 풀이법, N^2풀이법,  lower_bound 풀이법 등 다양한 방법이 존재하지만 필자가 알고있는 

N^2 풀이법과 Lower_bound를 사용한 선형시간으로 푸는 방법에 대하여 설명하도록 하겠습니다. 


그렇다면 N^2의 풀이를 먼저 사용하여 

풀이해보겠습니다.

1. N^2을 사용해보자
N^2을 사용하기 위해서는 일반적으로 N사이즈가 1000 정도에서 빈번하게 사용되고 있습니다. 
그렇다면 N^2의 풀이는 어떤 풀이길래????? 

원본 배열 arr[]


위와 같은 수열이 있다고 생각해보자
 
원본배열 arr[]에 위 값들을 저장해두고 

입력과 동시에 자기자신은 길이 1을 가지고 있으므로

원본과 같은사이즈의 배열 dp[i] (value가 있는 index번째에) 1로 초기화 해주도록 하자 

lis 길이저장 배열 dp[]

자 그러면 이제 원본의 1번째부터 n번째까지 핀을 꽂으면서 그 앞쪽을 탐색해본다고 따저보자 
이게 이해가 되지 않는다면 아래 그림을 참고해보자 

핀을 꽂은 위치를 기준으로 앞쪽을 전부 탐색해보는것이다. 이짓을 왜하냐?
왜냐하면 핀을 꽂은 위치가 자신보다 앞쪽 인덱스에 위치한 value가 작다면, 즉 (증가수열을 이룰수도 있는 부분이라면!)
-> 내가 앞쪽에 있는 값보다 크다면 당연히 증가수열이지 않은가 

그렇다면 해당 인덱스에 저장된 DP테이블값을 보는것이다! 

즉, dp테이블에 저장된 데이터의 의미는 엄밀히 말하면  

(i번째까지 핀을 꽂으면서 탐색을 해보았을 때 가장 긴 LIS의 길이만 저장되어있는것이다.)
(가장 중요한건 i번째까지만!!! 계산했을때이다. )

위그림은 핀을 꽂은 순서에 따라서 DP테이블에 저장된 LIS의 길이를 저장한것이다. 이 테이블 내의 값과 과정이 이해가 된다면
N^2에 대한 이해는 완벽히 되었다고 볼수 있다. 

이제  지금까지 설명해본 논리를 종합해보자
1. 원본을 기준으로 DP테이블을 갱신해 나간다고 생각하는것이 바탕되어있다. 

2. 원본 1번째부터 N번째까지 그 앞쪽의 인덱스들을 무식하게 전부 봐주는 방식인데
            원본 현 인덱스보다 작다면(증가수열이 가능하므로) 해당 인덱스의 DP테이블에 
저장된VALUE+1을했을때 기존에 저장되어있던 값보다 크다면 
갱신해주고 아니라면 SKIP해준다.

3. 그럼 이제 그 과정에서 즉 항상 맨마지막 인덱스가 LIS값이 저장되어있다는 보장이 없으므로 
매번 기준이 되는 원본 인덱스에서의 DP값들 중의 최대값이 LIS이므로 
max값만 갱신해주며 쭉 끝까지 탐색하면 된다~


자 이제 Lower_bound를 활용한 좀더 큰 사이즈의 배열의 LIS를 구해보자

이 풀이는 선형시간, 즉 O(n)으로 해결할 수 있는 풀이이다. 그렇다면 O(n)으로 어떻게 해결할 수 있나?
Lower_bound (이분탐색 기반의 해당 value 이상의 값이 최초로 등장하는 인덱스의 위치를 찾아내는 알고리즘이다)
을 사용하여 value 이상이 등장하는 위치를 찾아준다. 

먼저 위와 같은 똑같은 원본배열로 설명하겠다.

int arr[]

준비물은 정수형 벡터 하나와 lower_bound 알고리즘이면 된다. 

vector<int>

자 그렇다면 먼저 vector안에 -1을 넣고 시작한다. 
물론 lis 문제가 자연수 문제일경우에만 해당된다. 

(어떠한 수가와도 본인자체의 길이는 1이 되므로 )
여기서는 vector 컨테이너에 한번 넣을수 있다는 것이 어떠한 Event라고 생각해주면된다. 

즉 vector에 보관되고 있는 수들은 기존에 갱신해왔던 lis길이를 구성하였었던 수들? 이라고 말하면 편하겠다. 
그치만 lis가 3일때의 ->  vector<int>에는 딱 이수들이 있어야겠지? 라는 말이 아니다.

위 그림을 가지고 과정을 설명해보겠다. 

----------------------------------------------------<1 stage>----------------------------------------------------

----------------------------------------------------<2 stage>----------------------------------------------------

----------------------------------------------------<3 stage>----------------------------------------------------

이 단계에서 어떤 로직이 일어날까? 그렇다 Lower_bound알고리즘을 사용하여 
현 vector컨테이너에 저장된 수들(현존하는 lis 구성 체제라고 보는게 맞을것 같다 )

여기서 이 원본의 작은 수가 현 vector컨테이너에 들어왔을때 (어느 계급??)인지를 

보는게 맞을것같다. 
이때 사용되는 Lower_bound알고리즘의 복잡도는 O(LogN)이다
즉!!! 뒤에 등장한 작은수가 더 긴 lis수로 거듭날수 있는지 현체제의 해당 계급의 수와 1대1 매칭시켜가줘보는것이다.

( 사실 위에서 한말이 이 알고리즘 설명의 전부인것 같다 ) 
그렇다면 계속해서 구해보자. ( 이해가 안될땐 의심이 많아지기 때문이다 )

----------------------------------------------------<4 stage>----------------------------------------------------

짜잔~ 이렇게 바뀌엇다. 

그럼이제 계속 더 잘 진행해보자

---------------------------------------------------- <5 stage> ---------------------------------------------------- 

---------------------------------------------------- <6 stage> ---------------------------------------------------- 

---------------------------------------------------- <7 stage> ---------------------------------------------------- 

여기서는 이제 기존에 구성되어있던 LIS 만큼의 수들이 새롭게 등장한 back보다 작은 수들로 바뀌어 back마저(비교 대상마저 바뀐 상태이다)

---------------------------------------------------- <8 stage> ---------------------------------------------------- 

갱신된 back을 기준으로 원본가 비교가 이루어지는 상태이다

---------------------------------------------------- <9 stage> ---------------------------------------------------- 


자 이렇게 하면 이제 count: 5를 마지막으로 종료가 되엇다. 

저뒤에 어떠한 5나 6아 온다고 한들 back보다 작으므로 현수열의 back이 갱신될때까지의 인덱스는 기존 벡터

에도  5나 6이 잔존하니 길이가 갱신될리가 없는것은 자명하다. 

파란색으로 칠한 인덱스는 Lower_bound를 통해 갱신된 것을 표시한것이다. 

총 lower_bound함수호출 3번, 탐색은 1방향으로 O(N)이 이루어졌다. 
즉 NLogN정도?의 복잡도가 발생하는것 같다

< 연습 문제 >
https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열
11053번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 가장 긴 증가하는 부분 수열 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 256 MB 20796 7600 5235 37.489% 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = { 10 , 20 , 10, 30 , 20, 50 }
www.acmicpc.net

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

12015번: 가장 긴 증가하는 부분 수열 2
12015번 제출 맞은 사람 숏코딩 풀이 풀이 작성 풀이 요청 재채점/수정 채점 현황 강의 가장 긴 증가하는 부분 수열 2 시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율 1 초 512 MB 2712 1102 777 44.173% 문제 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = { 10 ,  20 , 10,  30
www.acmicpc.net
<Code> - (n제곱 풀이법)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//2018年 08月 15日 LIS 
//pda_pro12
#include<iostream>
#include<algorithm>
#define N_ 1001
using namespace std;
int dp[N_], a[N_], n, m, ans;
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL), cout.tie(NULL); 
    cin >> n;
    for (int i = 1; i <= n; i++) 
        cin >> a[i], dp[i] = 1;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (a[i] > a[j]) 
                dp[i] = max(dp[i], dp[j] + 1);
            ans = max(ans, dp[i]); 
        }
    }
    cout << dp[n];
    return 0;
}

<Code> - (Lower_bound 풀이법)


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
//2018年 08月 15日  LIS 
//pda_pro12
#include<iostream>
#include<algorithm>
#include<vector>
 
#define N 1000001
#pragma warning(disable:4996)
 
using namespace std; 
 
int n, m, a[N], ans; vector<int> v(n); 
 
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL), cout.tie(NULL); 
 
    cin >> n; 
    for (int i = 1; i <= n; i++)
        cin >> a[i]; 
    v.push_back(-1); 
    for (int i = 1; i <= n; i++) {
        if (v.back() < a[i]) {
            ans++;     // ans가 counting 해주는 것은 back을 갱신하는 순간이 몇번이엇는지 (즉 현재까지 세어온 LIS의 길이를 갱신해주었던 순간의 횟수를 세어주는 것이다 )
            v.push_back(a[i]);
        }
        else {
            auto j = lower_bound(v.begin(), v.end(), a[i]); // a[i]이상의 값이 등장하기 시작하는 인덱스의 위치를 찾는다
            *j = a[i];      // a[i]로 해당 lower_bound번째의 인덱스를 수정해주므로 이 값은 이제   
        }
    }
    cout << ans; 
    return 0; 
}


저작자표시

그냥 1차원적인 구현 문제이다. 

감시카메라의 갯수가 8개를 넘지않으므로 

각 카메라에 대한 회전 경우의수 4가지 (0도 90도 180도 270도)

4^8 = O(65536 * n^2(사각지역을 구할때 8*8밖에 되지않아 그냥 0인곳을 매번 다 탐색했다))

본인은 구현하지 않았지만 생각해보면 다음 5번 경우는 회전을해도 그대로니 

               5번 케이스인 경우는 제외하고 탐색해준다면 더빠를것 같다. 

다른분들은 더 효율적으로 짠것같기는 한데 나는 무려 20MS나 나왔다... ㅠ

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




<code>


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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
//pda_pro12
#include<iostream>
#include<vector>
#define INT 0x7fff0000
using namespace std;
 
int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 }, n, m;   // 0: 위 // 1: 오른 // 2: 아래 // 3: 왼 
bool Map[9][9][4]; int tmp[9][9], Orign[9][9];
vector<pair<int, int>> v;  // 감시카메라의 좌표정보 저장(1~8) 
vector<int> Rotate; // 카메라 회전정보 저장(O(4^v.size()))
int ans = INT;    // 최소값 산출을 위해 초기값 INT MAX값으로 214748347 설정
 
int Min(int a, int b) {
    return (a < b) ? a : b; 
}
 
int Recovery() {   // 감시처리 전의 상태로 복구함과 동시에 사각지역 탐색 
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (tmp[i][j] == 0) cnt++;
            tmp[i][j] = Orign[i][j];
        }
    }
    return cnt;
}
 
void View_Camera(int num, int flag) {  // 몇번 카메라가 몇도 회전 했는지 Prameter로 받는다. 
    int x = v[num].first;  int y = v[num].second;
    for (int i = 0; i < 4; i++) {
        if (Map[x][y][i]) {
            int nx = x + dx[(i + flag) % 4];  int ny = y + dy[(i + flag) % 4];
            while (tmp[nx][ny] != 6 && nx >= 0 && nx < n && ny >= 0 && ny < m) { // 범위를 벗어나지 않거나 이미 감시한 지역(9)이고, 빈칸일경우 
                if (tmp[nx][ny] == 0) tmp[nx][ny] = 9;
                nx += dx[(i + flag) % 4];  ny += dy[(i + flag) % 4];
            }
        }
    }
    return;
}
 
void dfs(int cnt) {
    if (cnt == v.size()) { // 카메라에 대한 회전 정보가 카메라 갯수와 같아젔다면
        for (int i = 0; i < Rotate.size(); i++) // 회전정보만큼 카메라 돌려서 감시지역 처리해주기
            View_Camera(i, Rotate[i]);
        ans = Min(ans, Recovery());
        return;
    }
    for (int i = 0; i < 4; i++) { // 0: No rotate 1: 90  2: 180 3: 270
        Rotate.push_back(i);
        dfs(cnt + 1);
        Rotate.pop_back();
    }
    return;
}
 
int main() {
    cin >> n >> m;   // n = row  ,    m = col 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> tmp[i][j];
            Orign[i][j] = tmp[i][j];
            if (!tmp[i][j] || tmp[i][j] == 6)     continue; // 0이나 벽일경우 
            v.push_back(make_pair(i, j));  // Camera Direction (row, col); 
 
            switch (tmp[i][j]) {  // No1 ~ No5 Camera Direction input
            case 1: // 1type Camera   --> 초기 방향에 대한 정보를 저장해둔다 
                Map[i][j][1] = true;
                break;
            case 2:    //2type Camera
                Map[i][j][1] = true;
                Map[i][j][3] = true;
                break;
            case 3:  // 3type Camera
                Map[i][j][0] = true;
                Map[i][j][1] = true;
                break;
            case 4:   // 4type Camera
                Map[i][j][0] = true;
                Map[i][j][1] = true;
                Map[i][j][3] = true;
                break;
            case 5:
                for (int a = 0; a < 4; a++)
                    Map[i][j][a] = true;
                break;
            }
        }
    }
    dfs(0);
    cout << ans;
    return 0;
}


< STL의 유혹을 떨처버린 Code >


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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
//pda_pro12
#include<iostream>
#define INT 0x7fff0000
 
using namespace std;
 
int dx[] = { -1,0,1,0 }, dy[] = { 0,1,0,-1 }, n, m;   // 0: 위 // 1: 오른 // 2: 아래 // 3: 왼 
bool Map[9][9][4]; int tmp[9][9], Orign[9][9];
 
template<class T>
class _vector {
public:
    int _size; 
    int capacity; 
    T* arr; 
    _vector() {
        _size = 0; 
        capacity = 32; 
        arr = new T[capacity]; 
    }
    _vector(int k) {
        _size = k; 
        capacity = k; 
        arr = new T[k]; 
    }
    ~_vector() {
        delete[] arr; 
    }
    void clear() {
        delete[] arr; 
        _size = 0; 
        capacity = 32; 
        arr = new T[capacity]; 
    }
    
    void resize(int k) {
        T* temp; 
        temp = new T[k];
        for (int i = 0; i < _size; ++i) 
            temp[i] = arr[i]; 
        delete[] arr; 
        arr = temp; 
        _size = capacity = k; 
    }
 
    int size() const {
        return _size; 
    }
 
    T* begin() const {
        return &arr[0]; 
    }
 
    T* end() const {
        return &arr[0] + _size; 
    }
 
    void push_back(T val) {
        if (capacity == _size) {
            resize(_size * 2); 
            _size /= 2; 
        }
        arr[_size++] = val; 
    }
 
    void pop_back() {
        _size--; 
    }
 
    T& operator[](int idx) {
        return arr[idx]; 
    }
 
    T operator[](int idx) const{
        return arr[idx]; 
    }
};
 
_vector<pair<int, int>> v;  // 감시카메라의 좌표정보 저장(1~8) 
_vector<int> Rotate; // 카메라 회전정보 저장(O(4^v.size()))
 
int ans = INT;    // 최소값 산출을 위해 초기값 INT MAX값으로 214748347 설정
 
int Min(int a, int b) {
    return (a < b) ? a : b;
}
 
int Recovery() {   // 감시처리 전의 상태로 복구함과 동시에 사각지역 탐색 
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (tmp[i][j] == 0) cnt++;
            tmp[i][j] = Orign[i][j];
        }
    }
    return cnt;
}
 
void View_Camera(int num, int flag) {  // 몇번 카메라가 몇도 회전 했는지 Prameter로 받는다. 
    int x = v[num].first;  int y = v[num].second;
    for (int i = 0; i < 4; i++) {
        if (Map[x][y][i]) {
            int nx = x + dx[(i + flag) % 4];  int ny = y + dy[(i + flag) % 4];
            while (tmp[nx][ny] != 6 && nx >= 0 && nx < n && ny >= 0 && ny < m) { // 범위를 벗어나지 않거나 이미 감시한 지역(9)이고, 빈칸일경우 
                if (tmp[nx][ny] == 0) tmp[nx][ny] = 9;
                nx += dx[(i + flag) % 4];  ny += dy[(i + flag) % 4];
            }
        }
    }
    return;
}
 
void dfs(int cnt) {
    if (cnt == v.size()) { // 카메라에 대한 회전 정보가 카메라 갯수와 같아젔다면
        for (int i = 0; i < Rotate.size(); i++) // 회전정보만큼 카메라 돌려서 감시지역 처리해주기
            View_Camera(i, Rotate[i]);
        ans = Min(ans, Recovery());
        return;
    }
    for (int i = 0; i < 4; i++) { // 0: No rotate 1: 90  2: 180 3: 270
        Rotate.push_back(i);
        dfs(cnt + 1);
        Rotate.pop_back();
    }
    return;
}
 
int main() {
    cin >> n >> m;   // n = row  ,    m = col 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> tmp[i][j];
            Orign[i][j] = tmp[i][j];
            if (!tmp[i][j] || tmp[i][j] == 6)     continue; // 0이나 벽일경우 
            v.push_back(make_pair(i, j));  // Camera Direction (row, col); 
            switch (tmp[i][j]) {  // No1 ~ No5 Camera Direction input
            case 1: // 1type Camera   --> 초기 방향에 대한 정보를 저장해둔다 
                Map[i][j][1] = true;
                break;
            case 2:    //2type Camera
                Map[i][j][1] = true;
                Map[i][j][3] = true;
                break;
            case 3:  // 3type Camera
                Map[i][j][0] = true;
                Map[i][j][1] = true;
                break;
            case 4:   // 4type Camera
                Map[i][j][0] = true;
                Map[i][j][1] = true;
                Map[i][j][3] = true;
                break;
            case 5:
                for (int a = 0; a < 4; a++)
                    Map[i][j][a] = true;
                break;
            }
        }
    }
    dfs(0);
    cout << ans;
    return 0;
}


저작자표시

'PS) BOJ > DFS' 카테고리의 다른 글

[C++] 사다리조작 [백준 15684]  (0) 2018.08.15




컴퓨터 N를 최소의 비용으로 연결하기 위해서는 사이클이 생성되도록 연결하면 번복된 연결이 발생하므로 

사이클이 발생하지 않도록 모든 컴퓨터들이 연결되도록 하는 문제로 이해했다. 

입력 -> 정점 V1, V2 가중치 W로  vector에  적재하여 가중치 w를 기준으로 오름차순 정렬을 한뒤에 

Disjoint_Set을 사용하여 사이클 발생여부를 판단하면서 가중치를 더해주면 끝

Disjoint_Set이나 Mst를 숙지하고 있다면 굉장히*3  쉽게 풀수 있는 문제입니다.


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






<code>


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
// pda_pro12
#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 0x7fff0000
#define N_ 100000
using namespace std; 
 
int n, m, par[N_], ans; 
vector<pair<int, pair<int, int>>> v; 
 
int find(int x) {
    if (x == par[x])
        return x; 
    return par[x] = find(par[x]); 
}
 
bool Merge(int x, int y) {
    x = find(x); 
    y = find(y); 
    if (x == y)
        return false; 
    par[y] = x; 
    return true; 
}
 
int main() {
    int v1, v2, w;
    ios::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);   
 
    cin >> n >> m; 
    for (int i = 1; i <= n; i++)
        par[i] = i; 
    
    while (m--) {
        cin >> v1 >> v2 >> w; 
        v.push_back({ w, {v1, v2}}); 
    }
    sort(v.begin(), v.end());    // 가중치 별 정렬 
    
    for (int i = 0; i < v.size(); i++) {
        int w = v[i].first; 
        int v1 = v[i].second.first; 
        int v2 = v[i].second.second; 
        if (Merge(v1, v2))  // 사이클 발생하지 않을경우 연결 후  
            ans += w;    // 연결비용 적재 
    }
    cout << ans; 
    return 0; 
}


저작자표시

  




3개월전쯤이었나 이분탐색 문제들중에서 유일하게 못풀었던 문제였다. 


그냥 못풀겠거니~ 하고 냅뒀는데 북마크 문제 뒤적이다가 한번 볼까하고 풀었는데 

인덱스 카운팅을 통해 풀수 있을것 같았다.


-> 석순은 최대 높이부터 아래로 탐색하면서 보다 높은 높이에서 뚫어야할 석순이 있다면 그것보다 낮은 높이에도 뚫어야할게 있는것이므로 1높은 높이에서의 정보를 그대로 가저옴으로서 (종유석도 마찬가지) 종유석과 석순에 대한 뚫어야할 갯수 정보를 저장한다. 

갱신된 석순과 종유석을 기반으로 높이 하나하나(1~ h)까지의 관점에서 종유석과 석순의 뚤어야할 갯수를 더하며 정해를 찾아낸다.





<code>


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
// pda_pro12
#include<iostream>
 
#define N_ 500001
#define D 0x7fffffff
 
using namespace std;
 
int s[N_], r[N_], s_b[N_], s_t[N_], n, h, min_ = D, cnt_; 
 
int main() {
    ios::sync_with_stdio(false); 
    cin.tie(NULL), cout.tie(NULL); 
    cin >> n >> h; 
    for (int i = 0; i < n / 2; i++) {
        int t, b; 
        cin >> b >> t; 
        s_b[b]++; s_t[t]++; 
    }
    for (int i = h; i >= 1; i--) {   // 가장 높은 높이부터 
        s[i] = s_b[i] + s[i + 1]; s_b[i] = 0; 
        r[i] = s_t[i] + r[i + 1]; 
    }
    for (int i = 1; i <= h; i++) {
        s_b[i] = s[i] + r[h - i + 1]; 
        if (s_b[i] <= min_)
            (s_b[i] == min_) ? cnt_++ : cnt_ = 1, min_ = s_b[i]; 
    }
    cout << min_ << ' ' << cnt_; 
    return 0;
}


저작자표시


문제 설명에서 가장 먼거리에 숨은 헛간의 번호를 찾는다고 하였으나 사실상 시작점으로 부터
각 헛간까지 우회하는 경로가 없어야하므로, 다익스트라로 각 헛간까지의 최단거리를 
갱신해주면된다. 

중요한것은 거리를 기준으로 정렬하였을때, 초기 입력받은 번호에 대한 정보를 잃지 않기 위해서 

구조체 형식으로 거리배열을 생성하고, 갱신하였다. 

나머지는 무방향 그래프이면서 최대거리와 최대거리 요소의 갯수만 찾아주면 간단히 해결된다.



<code>

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
//pda_pro12
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
 
#define all(x) x.begin(), x.end()
#define INT 0x7fffffff
#define N_ 20001
 
using namespace std;
 
struct DATA { int num, value; };
 
vector<pair<int, int>> v[N_]; priority_queue<pair<int, int>> pq;
int n, m; DATA dst[N_]; int x, y; vector<int> ans;
 
bool cmp(DATA u, DATA t) {
    return u.value < t.value;
}
bool cmp1(DATA u, DATA t) {
    return u.num < t.num;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
    while (m--) {
        cin >> x >> y;
        v[x].push_back({ y, 1 });
        v[y].push_back({ x, 1 });
    }
    for (int i = 1; i <= n; i++) {
        dst[i].value = INT, dst[i].num = i;
    }
    dst[1].value = 0;
    pq.push({ 1, 0 });
    while (!pq.empty()) {
        int v_x = pq.top().first;
        int dis = -pq.top().second;
        pq.pop();
        if (dis > dst[v_x].value) continue;
        for (int i = 0; i < v[v_x].size(); i++) {
            int next = v[v_x][i].first;
            int n_dis = dis + v[v_x][i].second;
            if (n_dis < dst[next].value) {
                dst[next].value = n_dis;
                pq.push({ next, -n_dis });
            }
        }
    }
    sort(dst + 1, dst + 1 + n, cmp);
    int Max = 0;
    for (int i = 1; i <= n; i++) {
        if (Max < dst[i].value) {
            Max = dst[i].value;
            ans.clear();
            ans.push_back(dst[i].num);
        }
        else if (Max == dst[i].value)
            ans.push_back(dst[i].num);
    }
    sort(all(ans));
    cout << ans.front() << ' ' << Max << ' ' << ans.size();
 
    return 0;
}


저작자표시

'PS) BOJ > Dijkstra' 카테고리의 다른 글

[C++]알고스팟[백준1261]  (0) 2018.08.15





처음엔 A....뭐야... 그냥 bfs로 슥삭하면되겠네....

라고 생각했지만 아니었다. 

더 많은 칸을 가야하지만 최소의 벽을 깨고 가는 경우가 있기 때문이었다. 

기냥 2차원 거리 배열을 선언해서 INF로 초기화해주자. 

어차피 시작점은 0,0 이니 거리배열 [0][0] = 0으로 해주자 

똑같이 Priority_Queue를 사용하는데 인자로 <int,int> int를 주었다. 

Vertext 하나의 위치정보가 x,y좌표이므로 ~
간선정보는 배열자체에 주어져있으므로 필요없고, 연결 노드야 현시점에서 4방향

탐색을 통한 지점일테고....

다만 시간줄이려고 cin.tie(NULL)해놓고 scanf를 써서 맞왜틀을 30분 겪었다...ㅎㅎ

나머지는 단순한 다익스트라로 쉽게 풀린답


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



<CODE>


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
// pda_pro12
#include<algorithm>
#include<queue>
#include<iostream>
 
#define lng(x) x.length()
#define sz(x) x.size()
#define N_ 101
#define INT 0x7fffffff
using namespace std;
 
int dx[] = { -1,1,0,0 }; int dy[] = { 0,0,-1,1 };
int n, m, a[N_][N_], dst[N_][N_];
priority_queue<pair<pair<int, int>, int>> pq; 
 
int main() {
    cin >> n >> m; 
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            scanf("%1d", &a[i][j]),dst[i][j] = INT; 
    dst[0][0] = 0;
    pq.push({ {0,0},0 }); 
    while (!pq.empty()) {
        int v_x = pq.top().first.first; int v_y = pq.top().first.second; 
        int dis = -pq.top().second;
        pq.pop(); 
        if (dis > dst[v_x][v_y]) continue; 
        for (int i = 0; i < 4; i++) {
            int nx_x = v_x + dx[i]; int ny_y = v_y + dy[i]; 
            if (nx_x < 0 || nx_x >= m || ny_y < 0 || ny_y >= n) continue; 
            int n_dis = dis + a[nx_x][ny_y]; 
            if (n_dis < dst[nx_x][ny_y]) {
                dst[nx_x][ny_y] = n_dis; 
                pq.push({ {nx_x, ny_y}, -n_dis }); 
            }
        }
    }
    cout << dst[m - 1][n - 1]; 
    return 0;
}


저작자표시

'PS) BOJ > Dijkstra' 카테고리의 다른 글

[C++]숨바꼭질[백준 6118]  (0) 2018.08.15








입국심사대 N이 10만,   입국 처리인원이 10억으로 Max값이 주어진다. 각 심사대에서 처리하는데 소요되는 시간 또한 10억이다. 완탐으로 1초안에 해결이 불가능한 문제이다. 
이걸 완탐돌린다면... 생각만 해도 끔찍하다. 

착안해낸 아이디어
1. 하한값을 1로 잡고 상한값을 10억*10만값으로 가정하고 풀이하였다.
    (WorstCase: 각 심사대10억*10만)

2.  이분탐색으로 시간을 가정하고 해당 시간으로 10만의 심사대에서 처리하고자하는 인원 M을 처리할
     수 있는지 혹은 처리하기에 시간이 부족한지를 살펴본다. 

3. 처리시간이 부족하다면 하한을 중간값+1로 설정하여 중간값을 다시 설정하고 이분탐색을 진행한다. 
    인원처리가 가능하다면 상한값을 중간값-1로 설정하여 left값이 right를 초과하는 순간 종료된다. 

4. lft는 항상 최소한의 가능한순간까지의 하한값을 증가시킬것이다. right값을 lft값이 초과하는 순간
   빠져나와버리므로 수용가능한 경우의 최소 mid값과 lft값은 일치한다. 
시간 복잡도 :  O(NlogN) 
탐색과정을 보면 다음과 같다 





<code>


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
// pda_pro12
#include<iostream>
#include<algorithm>
#define N_ 100000
#define Upper 100000000000000   // N_ * M(max)
 
using namespace std;
 
typedef long long ll;
ll lft, rgt, n, m;   int a[N_];
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> m;
    for (int i = 0; i < n; i++) 
        cin >> a[i];
 
    ll lft = 1;  ll rgt = Upper;   // Lower ,  Upper
 
    while (lft <= rgt) {
        
        ll mid = (lft + rgt) >> 1;
        ll Sum = 0;
        for (int i = 0; i < n; i++)
            Sum += (mid / a[i]);
        if (Sum >= m)
            rgt = mid - 1; 
        else
            lft = mid+1;
    }
    cout << lft << '\n';
    return 0;
}


'PS) BOJ > Binary Search' 카테고리의 다른 글

[C++]수열 걷기[백준 4929]  (0) 2018.08.21
[C++] 랜선 자르기 [BOJ 1654]  (0) 2018.08.16
[C++] K번째 수[백준 1300]  (0) 2018.08.16
[C++] 게임 [백준 1072]  (0) 2018.08.16

개인적으로 '감시' 문제보다 구현할게 많지 않아서 간단하게 풀수 있는 문제입니다.  

먼저 '연구소'라는 문제를 풀어본사람은 비슷하다는 느낌을 많이 받았을 것입니다.  

먼저 사다리의 시작점-도착점이 일치하는지 여부를 판별하기전에 사다리부터 놓아야합니다.  

문제 해결 절차 

1. 사다리를 h*n인덱스를 탐색하며 양사이드 [h][n-1]과 [h][n+1], [h][n]이 비어있는 사다리인지 확인 
   해본다. (h가 세로선이므로 행 n이 가로선 번호이므로 열이다.헷갈리지 않게 주의하자) 
2. 비어있다면 사다리를 놓고 재귀호출~ 그리고 재귀호출 끝나고 돌아오면 백트래킹으로 다시 사다리를 
    없애주도록 하자. 생각보다 복잡도가 심하지 않은 편이다. (양사이드와 현재 인덱스가 있으므로 )
 시간을 최대한 줄이자
- 가지치기를 잘하여 사다리들이 시작점으로 모두 도착하는경우 더이상 탐색하지 않는다. 
- 탐색과정에서 행단위로 양사이드 및 해당 열에 사다리를 모두 놓았다면, 해당 행 이상인 부분만 탐색. 

위 조건만 잘 만족시켜준다면 시간안에는 통과할수 있을 것이다. 




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

<Code>


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
56
57
58
59
// Minerba
#include<iostream>
using namespace std;
bool a[31][11]; int n, m, h, Ladder;    bool res;
bool Count_Ladder() {
    for (int i = 1; i <= n; i++) { // 세로선 번호  // i는 반복문 시작전 최초의 시작점, pt는 변경될 시작점
        int pt = i;
        for (int j = 1; j <= h; j++) {
            if (a[j][pt]) pt += 1;   // 오른쪽으로 이동
            else if (pt - 1 > 0 && a[j][pt - 1]) pt -= 1; // 왼쪽으로 이동 
        }
        if (i == pt) continue;
        else
            return false;
    }
    res = true; 
    return true;
}
 
void dfs(int x, int cnt) {
    if (res) return;
    if (cnt == Ladder) {
        if (Count_Ladder())  m = cnt;
        return;
    }
    for (int i = x; i <= h; i++) {   // 기존 행에 사다리를 놓았다면 해당 행과 같거나 더 커야한다.
                                     // 사다리가 역주행해서 위로 올라갈순 없으니...
        for (int j = 1; j < n; j++) {
            if (!a[i][j]) {
                if (!a[i][j - 1] && !a[i][j + 1]) { // 연속되지 않은 가로선 
                    a[i][j] = 1;
                    dfs(i, cnt + 1);
                    a[i][j] = 0;
                }
            }
        }
    }
    return;
}
 
int main() {
 
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> n >> m >> h;
    while (m--) {
        int x, y; cin >> x >> y;
        a[x][y] = 1;
    }
    for (int i = 0; i <= 3; i++) {
        Ladder = i;
        dfs(1, 0);
        if (res) break;
    }
    if (!res) cout << -1 << '\n';
    else cout << m << '\n';
    return 0;
}














'PS) BOJ > DFS' 카테고리의 다른 글

[C++]감시[백준 15683]  (0) 2018.08.15




※문제 해결 과정

A, B, C물통이 있고 초기에 C만 꽉차있다. 여기서 물통의 물이 옮겨지는 경우의 수를 BFS로 물통들의 

잔량을 큐에 저장하면서 돌려주면 된다. 



먼저 C->A물통으로 옮기는경우와 C->B물통으로 옮기는 경우가 있다. 

또 B->C물통으로 옮기는 경우와 B-> A물통으로 옮기는 경우

A->C물통으로 옮기는 경우, A->B물통으로 옮기는 경우를 따져주면 된다. 중요한건 A물통의 잔량이 

비었다면 그때의 C물통에 있을 수있는 물의 양이므로 물을 옮기는 과정에서 A물통의 잔량이 없다면 

물의 양이 1~200까지 밖에 주어지지 않으므로 그때의 Array_[C의 잔량] = true; 이런식으로 체크해주

면된다. 여기서 방문처리와 같은 배열처럼 같은 물의 양 조합이 또나오면 번복하는 연산이 일어날수 있

으므로  A,B물통의 잔량을 이차원배열로 체크를 해준다. Array_[A잔량][B잔량] = true; 



(물통이 2개라서 이런식으로 체크가 가능한것이다..ㅠ) 



다돌려주고 나서 1~200까지 쭉 올라가면서 체크된 c의 잔량 배열을 출력해주면 


AC를 받을수 있을 것이다. 



<code>


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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
//pda_pro12
#include<algorithm>
#include<iostream>
#include<queue>
 
using namespace std;
 
bool chk[201][201];  // a, b 물통의 물의 양을 확인해주는 배열
bool ans[201];   // c물통의 물의 양을 확인해주는 배열 
int a, b, c, sum;
 
queue<pair<int, int>> q;
 
int main() {
    cin >> a >> b >> c;
    chk[0][0] = true;
    ans[c] = true;
    sum = c;   // c물통에만 가득차있으므로 손실되는 물이 없으면 총량은 c의 들이와 같음
    q.push(make_pair(0, 0));
 
    while (!q.empty()) {
        int x = q.front().first;
        int y = q.front().second;
        int z = sum - (x + y);   // 
        q.pop();
        int nx, ny, nz;
        nx = x; ny = y; nz = z;
        ny += nx;
        nx = 0;
        if (ny >= b) {  // 물의 이동시 살펴줘야할 조건 
            nx = ny - b;
            ny = b;
        }
        if (!chk[nx][ny]) {
            chk[nx][ny] = true;
            q.push(make_pair(nx, ny));
            if (nx == 0) {
                ans[nz] = true;
            }
        }
        nx = x; ny = y; nz = z;
        nz += nx;
        nx = 0;
        if (nz >= c) {
            nx = nz - c;
            nz = c;
        }
        if (!chk[nx][ny]) {
            chk[nx][ny] = true;
            q.push(make_pair(nx, ny));
            if (nx == 0) {
                ans[nz] = true;
            }
        }
        nx = x; ny = y; nz = z;
        nz += ny;
        ny = 0;
        if (nz >= c) {
            ny = nz - c;
            nz = c;
        }
        if (!chk[nx][ny]) {
            chk[nx][ny] = true;
            q.push(make_pair(nx, ny));
            if (nx == 0) {
                ans[nz] = true;
            }
        }
 
        nx = x; ny = y; nz = z;
        nx += ny;
        ny = 0;
        if (nx >= a) {
            ny = nx - a;
            nx = a;
        }
        if (!chk[nx][ny]) {
            chk[nx][ny] = true;
            q.push(make_pair(nx, ny));
            if (nx == 0) {
                ans[nz] = true;
            }
        }
 
        nx = x; ny = y; nz = z;
        ny += nz;
        nz = 0;
        if (ny >= b) {
            nz = ny - b;
            ny = b;
        }
        if (!chk[nx][ny]) {
            chk[nx][ny] = true;
            q.push(make_pair(nx, ny));
            if (nx == 0) {
                ans[nz] = true;
            }
        }
        nx = x; ny = y; nz = z;
        nx += nz;
        nz = 0;
        if (nx >= a) {
            nz = nx - a;
            nx = a;
        }
        if (!chk[nx][ny]) {
            chk[nx][ny] = true;
            q.push(make_pair(nx, ny));
            if (nx == 0) {
                ans[nz] = true;
            }
        }
    }
    for (int i = 0; i <= c; i++) {
        if (ans[i]) {
            cout << i << ' ';
        }
    }
    return 0;
}


+ Recent posts

티스토리툴바