일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
- Z 알고리즘
- 기하
- Z algorithm
- Manacher 알고리즘
- codeforces
- 14179
- Manacher's algorithm
- POI Solution
- 세그먼트 트리
- Implementation
- 볼록 껍질
- IOI 2013
- DP
- JOI 2018
- ICPC 연습
- 기하 알고리즘
- 컨벡스 헐
- JOI
- boj
- acmicpc.net
- convex hull
- BAPC 2018
- 구현
- 코드포스
- 백준 온라인 저지
- 2794
- 그래프
- Divide and conquer optimization
- 8192
- BAPC
- Today
- Total
프로그래밍 연습장
180421 동아리 연습 문제 풀이 본문
동아리 시간 때 설명했었고, 다음 코드를 첨부한다.
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 |
스택에서 수를 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"를 출력한다.
괄호 문자열이 재귀적으로 정의되므로, 괄호의 값 또한 재귀적으로 풀 수 있다. 스택에 "현재 단계에서 괄호가 얼마나 열렸는지"를 유지한다.
할 수 있는 한 가지 관찰은, "여는 괄호와 닫는 괄호가 연이어서 나오는 지점"들에서 괄호의 값이 결정된다는 것이다. 위의 스택을 바탕으로 현재 단계에서 열려 있는 괄호들의 배율(×2 또는 ×3)의 누적 곱을 저장한 뒤, 그런 지점들에서 이 값들을 모두 합해주면 답을 얻을 수 있다.
만약 닫는 괄호가 현재 스택에 들어 있는 여는 괄호와 짝이 맞지 않는 괄호라면 입력은 만들 수 없는 괄호열이 된다. 모든 괄호를 입력받고 나서 스택이 비어있는지를 꼭 확인해주도록 하자(아니면 만들 수 없는 괄호열이다).
동아리 시간 때 설명했었고, 다음 코드를 첨부한다.
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 |
큐를 쓰는 문제가 몇 개 없어서 가지고 왔더니, 알고보니 데크를 쓰는 문제였다. 데크에 관해서도 동아리 시간에 한 설명으로 대체한다.
왼쪽부터 각 $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$ 중에서 가장 작은 원소가 된다.
그러면, 왼쪽에서부터 차례로 그 위치에서 칠할 수 있는 최대 높이까지 페인트를 칠해 보면서, 그런 높이가 변하거나 새로 페인트를 칠해야 하는 높이마다 새로 칠해 주는 방법으로 최대한의 널빤지를 페인트칠할 수 있다.
동아리 시간에 설명했었고, 다음 소스를 첨부한다.
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 |
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<int, vector<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 |
카드를 최소 비용으로 합치기 위해서는 아래 전략에 따르면 됨을 간단히 알 수 있다. 증명은 생략한다.
- 항상 가장 작은 두 묶음의 카드를 합친다.
$N$개의 카드 묶음에서 가장 작은 두 묶음을 합치고 나면 $N-1$개의 카드 묶음이 남게 되고, 다시 이 카드 묶음들 중 가장 작은 두 묶음의 카드를 합쳐 나가면 최소 비용으로 카드를 정렬할 수 있다.
이를 위해서 우선순위 큐를 이용한다.
1. $N$개의 카드 묶음의 크기를 우선순위 큐에 넣는다.
2. 가장 작은 두 수를 뺀다.
3. 그 두 수의 합을 비용에 더하고 다시 우선순위 큐에 넣는다. 2번으로 돌아간다.
4. 1개의 수가 남았을 때, 합치기가 끝났으므로 누적된 최종 비용을 출력한다.
이 또한 우선순위 큐로 비슷하게 생각하여 풀 수 있다.
1. 우선순위 큐에 먼저 K개의 소수들을 넣는다.
2. 우선순위 큐에서 가장 작은 수 $x$를 뺀다. 그리고 $x$에서 각 소수를 곱한 값들을 다시 우선순위 큐에 넣는다.
3. 2번을 N번째 반복했을 때 나오는 수가 우리가 원하는 결과값이다.
이 때 우선순위 큐에 같은 원소가 중복하여 들어가지 않도록 set 등의 자료구조(검색해 보자!)로 중복 원소를 관리할 수 있다.
연속된 빈 자리의 개수를 우선순위 큐에 넣어 관리한다고 생각하면 이 문제 또한 H, I와 같이 특정 연산들을 계속 반복해서 수행하는 문제로 바뀔 것이다. 간단하니 생각해 보자.
추가 문제로 제시되었는데, 기존의 문제들도 다 못 풀어서 문제를 읽은 사람은 없는 것 같다. ㅎㅎㅎㅎ
E번과 유사한 풀이로 풀리는데, 한 가지 차이점은 구간 길이에 제한이 있는 게 아니라, 구간의 최대 원소 - 최소 원소의 크기에 제한이 있다는 것이다. E와 같이 데크를 최댓값, 최솟값을 위해 두 개 사용한 뒤, 원소를 뺄 때에는 "만료"된 원소를 빼기보다는 "최대 원소 - 최소 원소"가 기준값보다 크게 하는 가장 오래된 값을 삭제하는 방식으로 한다.
Set 등을 사용하는 $O(n \log n)$ 방법으로는 시간 초과가 나게 설정되어 있다.
'문제 해결' 카테고리의 다른 글
180519 동아리 연습 문제 풀이 (0) | 2018.05.19 |
---|---|
180428 동아리 연습 문제 풀이 (1) | 2018.04.28 |
180324 동아리 연습 문제 풀이 (0) | 2018.03.24 |
Polish Problems (11-15) (0) | 2018.03.14 |
Polish Problems (6-10) (0) | 2018.03.06 |