프로그래밍 연습장

180421 동아리 연습 문제 풀이 본문

문제 해결

180421 동아리 연습 문제 풀이

김준원 2018. 4. 21. 12:56

A. 스택


동아리 시간 때 설명했었고, 다음 코드를 첨부한다.


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
#include <iostream>
#include <string.h>
#include <stack>
using namespace std;
 
stack<int> st;
int q;
char op[10];
int k;
 
int main()
{
    cin >> q;
 
    for (int t=0; t<q; t++) {
        cin >> op;
        if (strcmp(op, "push"== 0)
            cin >> k;
 
        if (strcmp(op, "push"== 0)
            st.push(k);
 
        if (strcmp(op, "pop"== 0) {
            if (st.empty()) cout << "-1\n";
            else {
                cout << st.top() << "\n";
                st.pop();
            }
        }
 
        if (strcmp(op, "size"== 0)
            cout << st.size() << "\n";
 
        if (strcmp(op, "empty"== 0)
            cout << (st.empty() ? 1 : 0<< "\n";
 
        if (strcmp(op, "top"== 0) {
            if (st.empty()) cout << "-1\n";
            else cout << st.top() << "\n";
        }
    }
}
 
cs



B. 스택 수열


스택에서 수를 pop함과 동시에 수열의 수가 하나씩 늘어나게 된다. 입력된 수열을 만들 수 있는 전략을 생각해 보자.


1. 첫 번째 수 $a_1$을 만들려면, $1$에서 $a_1$까지의 모든 수를 push한 다음에 한 번의 pop을 해야 한다.

2-1. 만약 두 번째 수가 $a_1-1$이라면, 바로 한 번 더 pop하면 된다.

2-2. 만약 두 번째 수가 $a_1$ 초과라면, 다시 $a_2$까지의 모든 수를 push한 다음에 한 번의 pop을 해야 한다.

2-3. 만약 두 번째 수가 $a_1-1$ 미만이라면, 만들 수 없는 수열이다.


일반화하면 다음과 같다. $i=1..n$까지 돌면서 각 $a_i$를 만들려 한다. (1) $a_i$가 이 때까지 스택에 넣은 마지막 수와 같거나 크다면, 마지막 수+1부터 $a_i$까지의 수들을 push한 다음 한 번의 pop을 한다. (2) 그렇지 않다면, $a_i$는 스택 안 바로 뺄 수 없는 곳에 들어 있으며, $a_i$를 만들 수 없다. 이 때엔 수열 전체가 만들 수 없으므로 "NO"를 출력한다.


C. 괄호의 값


괄호 문자열이 재귀적으로 정의되므로, 괄호의 값 또한 재귀적으로 풀 수 있다. 스택에 "현재 단계에서 괄호가 얼마나 열렸는지"를 유지한다.


할 수 있는 한 가지 관찰은, "여는 괄호와 닫는 괄호가 연이어서 나오는 지점"들에서 괄호의 값이 결정된다는 것이다. 위의 스택을 바탕으로 현재 단계에서 열려 있는 괄호들의 배율(×2 또는 ×3)의 누적 곱을 저장한 뒤, 그런 지점들에서 이 값들을 모두 합해주면 답을 얻을 수 있다.

만약 닫는 괄호가 현재 스택에 들어 있는 여는 괄호와 짝이 맞지 않는 괄호라면 입력은 만들 수 없는 괄호열이 된다. 모든 괄호를 입력받고 나서 스택이 비어있는지를 꼭 확인해주도록 하자(아니면 만들 수 없는 괄호열이다).


D. 큐


동아리 시간 때 설명했었고, 다음 코드를 첨부한다.


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
#include <iostream>
#include <string.h>
#include <queue>
using namespace std;
 
queue<int> st;
int q;
char op[10];
int k;
 
int main()
{
    cin >> q;
 
    for (int t=0; t<q; t++) {
        cin >> op;
        if (strcmp(op, "push"== 0)
            cin >> k;
 
        if (strcmp(op, "push"== 0)
            st.push(k);
 
        if (strcmp(op, "pop"== 0) {
            if (st.empty()) cout << "-1\n";
            else {
                cout << st.front() << "\n";
                st.pop();
            }
        }
 
        if (strcmp(op, "size"== 0)
            cout << st.size() << "\n";
 
        if (strcmp(op, "empty"== 0)
            cout << (st.empty() ? 1 : 0<< "\n";
 
        if (strcmp(op, "front"== 0) {
            if (st.empty()) cout << "-1\n";
            else cout << st.front() << "\n";
        }
        
        if (strcmp(op, "back"== 0) {
            if (st.empty()) cout << "-1\n";
            else cout << st.back() << "\n";
        }
        
    }
}
 
cs



E. 홍준이와 울타리


큐를 쓰는 문제가 몇 개 없어서 가지고 왔더니, 알고보니 데크를 쓰는 문제였다. 데크에 관해서도 동아리 시간에 한 설명으로 대체한다.


왼쪽부터 각 $i = x .. n$에 대해, $a_{i-x+1} .. a_i$ 중 가장 작은 높이를 찾는 문제를 생각하자. 이 문제가 풀린다면 본 문제도 풀릴 것이다. 이는 데크를 이용하여 풀 수 있는데, 핵심 아이디어는 "왼쪽에서부터 훑으면서 계산했을 때, 현재 원소 $x$가 등장했다면, 그 전에 등장한 $x$보다 큰 원소들은 앞으로의 최솟값에 영향을 끼치지 못한다"는 것이다. 이는 deque를 이용해 해결할 수 있다. deque의 앞에서 뒤로 가면서 뒤의 원소들이 더 새롭고(뒤에 등장하고), 또한 뒤의 원소들이 더 큰 순서로 deque 안에 들어있다. 차례대로 원소를 넣으면서 이 순서를 유지할 것이다.


1. 현재 $i$번째 인덱스를 보고 있다: $a_i$를 데크의 뒤에 넣고 싶다.

2. 데크의 맨 뒤에 있는 원소가 $a_i$보다 크다면, 그 원소를 뺀다. 데크의 맨 뒤에 있는 원소가 $a_i$보다 작게 될 때까지 반복한다.

3. 데크의 맨 뒤에 $a_i$를 넣는다.

4. 데크의 맨 앞에 있는 원소가 등장한 인덱스(데크에 원소를 넣을 때 같이 기록해 두어야 한다!)가 $i-x+1$ 미만이 되지 않도록, 그런 원소들을 데크의 앞에서 제거해 준다.

5. 이 때, 데크의 맨 앞에 있는 원소가 $a_{i-x+1} .. a_i$ 중에서 가장 작은 원소가 된다.


그러면, 왼쪽에서부터 차례로 그 위치에서 칠할 수 있는 최대 높이까지 페인트를 칠해 보면서, 그런 높이가 변하거나 새로 페인트를 칠해야 하는 높이마다 새로 칠해 주는 방법으로 최대한의 널빤지를 페인트칠할 수 있다.



F. 최대 힙


동아리 시간에 설명했었고, 다음 소스를 첨부한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;
 
priority_queue<int> pq;
 
int main()
{
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        if (x) pq.push(x);
        else {
            if (pq.empty()) cout << "0\n";
            else {
                cout << pq.top() << '\n';
                pq.pop();
            }
        }
    }
}
 
cs


G. 절댓값 힙


priority_queue 안에 비교 함수는 다음과 같이 정의할 수 있다. 동아리 시간에 설명하기를 깜빡하였다. ㅠ priority_queue 선언할 때 두번째 인자인 vector<int>는 별 의미는 없고, 세 번째 인자로 주어지는 comparator가 중요하다. 다음과 같은 comparator class를 넣어주면 정렬 순서를 지정할 수 있다.


물론 저 방법을 쓰지 않고도 앞서 알려준 힙의 기능만으로 풀 수도 있다. 양수들을 저장하는 힙, 음수들을 저장하는 힙, 두 개의 힙을 유지하면 된다. 최솟값을 뽑아야 하므로, 양수에 대해서는 -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
#include <bits/stdc++.h>
using namespace std;
 
class comp {
    // < 연산자 역할을 할 수 있는 함수여야 함.
    // 하지만 최소 힙이므로 부등호 방향을 바꾼다.
    public:
    bool operator()(int x, int y) {
        return abs(x) > abs(y) or (abs(x) == abs(y) and x > y);
    }
};
 
priority_queue<intvector<int>, comp> pq;
 
int main()
{
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        if (x) pq.push(x);
        else {
            if (pq.empty()) cout << "0\n";
            else {
                cout << pq.top() << '\n';
                pq.pop();
            }
        }
    }
}
 
cs


H. 카드 정렬하기


카드를 최소 비용으로 합치기 위해서는 아래 전략에 따르면 됨을 간단히 알 수 있다. 증명은 생략한다.


- 항상 가장 작은 두 묶음의 카드를 합친다.


$N$개의 카드 묶음에서 가장 작은 두 묶음을 합치고 나면 $N-1$개의 카드 묶음이 남게 되고, 다시 이 카드 묶음들 중 가장 작은 두 묶음의 카드를 합쳐 나가면 최소 비용으로 카드를 정렬할 수 있다.


이를 위해서 우선순위 큐를 이용한다.


1. $N$개의 카드 묶음의 크기를 우선순위 큐에 넣는다.

2. 가장 작은 두 수를 뺀다.

3. 그 두 수의 합을 비용에 더하고 다시 우선순위 큐에 넣는다. 2번으로 돌아간다.

4. 1개의 수가 남았을 때, 합치기가 끝났으므로 누적된 최종 비용을 출력한다.


I. 소수의 곱


이 또한 우선순위 큐로 비슷하게 생각하여 풀 수 있다.


1. 우선순위 큐에 먼저 K개의 소수들을 넣는다.

2. 우선순위 큐에서 가장 작은 수 $x$를 뺀다. 그리고 $x$에서 각 소수를 곱한 값들을 다시 우선순위 큐에 넣는다.

3. 2번을 N번째 반복했을 때 나오는 수가 우리가 원하는 결과값이다.


이 때 우선순위 큐에 같은 원소가 중복하여 들어가지 않도록 set 등의 자료구조(검색해 보자!)로 중복 원소를 관리할 수 있다.


J. 컴퓨터실


연속된 빈 자리의 개수를 우선순위 큐에 넣어 관리한다고 생각하면 이 문제 또한 H, I와 같이 특정 연산들을 계속 반복해서 수행하는 문제로 바뀔 것이다. 간단하니 생각해 보자.


K. Pilots


추가 문제로 제시되었는데, 기존의 문제들도 다 못 풀어서 문제를 읽은 사람은 없는 것 같다. ㅎㅎㅎㅎ


E번과 유사한 풀이로 풀리는데, 한 가지 차이점은 구간 길이에 제한이 있는 게 아니라, 구간의 최대 원소 - 최소 원소의 크기에 제한이 있다는 것이다. E와 같이 데크를 최댓값, 최솟값을 위해 두 개 사용한 뒤, 원소를 뺄 때에는 "만료"된 원소를 빼기보다는 "최대 원소 - 최소 원소"가 기준값보다 크게 하는 가장 오래된 값을 삭제하는 방식으로 한다.


Set 등을 사용하는 $O(n \log n)$ 방법으로는 시간 초과가 나게 설정되어 있다.

'문제 해결' 카테고리의 다른 글

180519 동아리 연습 문제 풀이  (0) 2018.05.19
180428 동아리 연습 문제 풀이  (1) 2018.04.28
180421 동아리 연습 문제 풀이  (1) 2018.04.21
180324 동아리 연습 문제 풀이  (0) 2018.03.24
Polish Problems (11-15)  (0) 2018.03.14
Polish Problems (6-10)  (0) 2018.03.06
1 Comments
댓글쓰기 폼