https://codeforces.com/contest/1375
Dashboard - Codeforces Global Round 9 - Codeforces
codeforces.com
지난번 코드포스 글로벌 라운드 9에서 꽤나 큰 충격을 받았다.
모든 문제가 사고력 위주의 풀이를 요구하며, 예제 입출력으로 말장난을 하는 등 나에겐 익숙하지 않았던 문제들로만 구성되어 있는 것이다.
결국 삽질 끝에 A번과 B번밖에 풀지 못 했으며, C번의 풀이를 보고 현자타임이 왔다.
나중에 알아보니 이러한 문제 유형을 constructive algorithms 라는 태그를 붙여 따로 분류를 하고 있었으며,
이런 문제가 나오면 삽질하지 않기 위해서라도 이런 유형에 대해 알아둬야 할 필요를 느꼈다.
먼저 constructive algorithms이라는 놈이 대체 뭐하는 녀석인지부터 알아보자.
constructive algorithms은 수학에서 말하는 구성적 증명을 생각하면 이해가 쉽다.
수학에서, 구성적 증명(構成的證明, constructive proof)은 일정 조건을 만족하는 대상의 존재성을, 그 대상을 구체적으로 만들어내어 증명하는 방법이다. 반면 비구성적 증명(非構成的證明, non-constructive proof)은 순수하게 존재성만을 입증하는 증명법이다.
출처 : https://ko.wikipedia.org/wiki/%EA%B5%AC%EC%84%B1%EC%A0%81_%EC%A6%9D%EB%AA%85
예를 들어, 소수의 갯수가 유한하다 가정하고, 유한한 소수에서 가장 큰 수 n에 대해, n! + 1을 하여 n보다 큰 소수를 직접 만들어, 소수의 갯수가 유한하다 라는 가정에 모순이 있음을 밝혀내는 유클리드의 소수의 무한성 증명은 구성적 증명이라고 할 수 있다.
constructive algorithms이 붙은 문제 또한 비슷한 맥락이다. 이들의 특징은 다음과 같다.
1. 요구사항이나 제한 조건 등의 규칙이 존재한다.
2. 그 규칙을 만족하는 배열(순열, 수열, 행렬 등)을 구성해야 한다.
3. 대부분 흥미롭다.
4. 때때로 코딩 능력보다는 발상 능력을 더 요구할 수 있다.
5. 다양한 정답 풀이, 그리고 겉보기에는 정답인 것 같은 풀이가 존재할 수 있다.
출처 : https://hkoi.org/en/training-materials/2019/
5번을 다르게 말하면 이상한 풀이나 복잡한 풀이로 삽질하기 정말 쉽다는 것이다.
때문에 이런 문제를 풀 때는 코드로 구현하는 것보다 먼저 여러 방법들을 생각해보고 그 방법이 정당한지 검증할 필요가 있다. 특히, 예제 입출력을 보고 풀이를 유추하는 것은 좋지 않다. 사악한 출제자들은 종종 예제 입출력에서 자신이 생각한 정답 풀이로는 나오지 않는 값을 보여 주기 때문에, 푸는 사람이 이상한 방법으로 생각하기 쉽다.
지난 대회에서 나왔던 constructive algorithms 문제 몇 개를 풀어 보자.
Codeforces Global Round 9
A. Sign Flipping
https://codeforces.com/contest/1375/problem/A
Problem - A - Codeforces
codeforces.com
문제를 요약하자면,
1. 항이 n(n은 홀수)개인 수열 a가 이 주어진다.
2. 이 수열의 임의의 항의 부호를 마음껏 바꿀 수 있다.
3. 1 <= i <= n-1인 정수 i에 대하여 a[i + 1] - a[i]의 값을 모았을 때, 값들 중 절반은 0보다 작거나 같아야 하며, 나머지 절반은 0보다 크거나 같아야 한다.
4. 해당 규칙을 만족하도록 수열의 부호를 바꾸어 출력하라.
이 문제를 해결하기 위한 결정적인 열쇠는 놀랍게도 누구나 알만한 상식이다.
정수 a(a>=0)과 정수 b(b<=0)에 대하여 b - a <= 0 이며, a - b >= 0이다.
그리고 우리는 수열의 모든 항의 부호를 마음대로 바꿀 수 있다.
만약 수열에 규칙을 정하여,
홀수 번째 항은 음수(혹은0), 짝수 번째 항은 양수(혹은0)
이라고 한다면,
홀수 번째 항 - 짝수 번째 항은 반드시 0보다 작거나 같으며,
짝수 번째 항 - 홀수 번째 항은 반드시 0보다 크거나 같다.
이 규칙 대로만 수열의 부호를 바꿔 준다면, 그것이 문제에서 요구하는 조건을 만족하는 수열이 된다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
vector<int> vec;
int n;
cin >> n;
for (int i = 0; i < n; i++) {
int temp;
cin >> temp;
if(i % 2) vec.push_back(abs(temp));
else vec.push_back((temp < 0 ? temp : -temp));
}
for (int i = 0; i < n; i++) cout << vec[i] << " ";
cout << "\n";
}
}
|
cs |
코드의 내용이다. 시간 복잡도와 공간 복잡도 모두 O(n)이다.
B. Neighbor Grid
https://codeforces.com/contest/1375/problem/B
Problem - B - Codeforces
codeforces.com
문제를 요약하자면,
1. 0보다 크거나 같은 정수로 이루어진 행렬이 주어진다.
2. 행렬 내의 임의의 원소에 원하는 값을 마음껏 더할 수 있다.
3. 행렬의 모든 1이상의 원소는 인접한 원소들 중 1이상인 원소들의 갯수와 같아야 한다.
4. 해당 규칙을 만족시킬 수 있는지, 만족시킬 수 있다면 만족하도록 행렬을 수정하여 출력하라.
이 문제를 푸는 아주 무식하면서 강력한 방법은, 그냥 다 채워버리는 거다.
행렬의 가장 자리 원소의 값은 인접한 원소가 2개기 때문에 최대 2이다.
행렬의 가장자리를 제외한 모서리 원소의 값은 인접한 원소가 3개기 때문에 최대 3이다.
그 외에는 인접한 원소가 4개기 때문에 최대 4이다.
최대가 되도록 행렬을 모두 채워버리면 그만이다. 예를 들어 3 * 3 행렬은 다음과 같이 채운다.
232
343
232
이런 식으로 채울 수 없다면 그냥 NO를 출력해주면 된다.
|
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
|
#include <bits/stdc++.h>
using namespace std;
int judge(int n, int m, int y, int x) {
int cnt = 0;
if (y == 0 || y == n) cnt++;
if (x == 0 || x == m) cnt++;
if (cnt == 0) return 4;
else if (cnt == 1) return 3;
else return 2;
}
int main() {
int t;
cin >> t;
while (t--) {
int n, m;
bool ret = false;
cin >> n >> m;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int temp;
cin >> temp;
if (temp > judge(n - 1, m - 1, i, j)) ret = true;
}
}
if (ret) cout << "NO\n";
else {
cout << "YES\n";
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cout << judge(n - 1, m - 1, i, j) << " ";
} cout << "\n";
}
}
}
}
|
cs |
코드의 내용이다. 행렬을 따로 만들어 두지도 않았기 때문에 공간 복잡도는 O(1)이며, 시간 복잡도는 O(nm)이다.
C. Element Extermination
https://codeforces.com/problemset/problem/1375/C
Problem - 1375C - Codeforces
codeforces.com
이 글을 쓰게 된 이유이다. 당시 1시간동안의 삽질에도 결국 풀지 못했다.
문제를 요약하자면,
1. 길이 n의 순열 a가 주어진다.
2. a의 두 항 a[i], a[i + 1] 에 대하여 a[i] < a[i + 1]일 경우 두 항중 원하는 항을 지울 수 있다.
3. 순열의 길이를 1로 만들 수 있는지를 출력하라.
이 문제의 답은 정말 간단하다.
첫 항보다 마지막 항이 더 크다면 YES
그렇지 않다면 NO
어떻게 이런 결론이 나올 수 있는 걸까?
먼저, 첫 항이 마지막 항보다 더 클 때를 생각해 보자.
a[1] < a[n]일 때,
a[1] < a[r]인 가장 앞쪽 인덱스 r을 고른다. a[1]과 a[r] 사이에 있는 항들은 모두 a[r]보다 작다.
r - 1이 1보다 클 경우 a[r-1] < a[r]이다. a[r-1]을 지우고 이를 r - 1이 1이 될 때 까지 반복한다.
r - 1이 1일 경우 a[r]을 지운다.
이 과정을 반복하면 a[1]을 제외한 모든 항이 지워진다.
a[1] < a[n]일 때는 결과가 항상 참임이 증명되었다. 이제 첫 항이 마지막 항보다 작을 때를 생각해 보자.
a[1] > a[n]일 때,
1. 가장 왼쪽 항은 감소될 수 없다. a[1]과 a[1]보다 큰 항을 짝지어서 하나를 지워도 a[1]보다 크거나 같기 때문이다.
2. 가장 오른쪽 항은 증가할 수 없다. a[n]과 a[n]보다 작은 항을 짝지어서 하나를 지워도 a[n]보다 작거나 같기 때문이다.
따라서 a[1] > a[n]이면 가장 왼쪽 항은 항상 가장 오른쪽 항보다 크며, 순열의 길이는 1로 만들 수 없다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while (t--) {
int n, s, e, temp;
cin >> n >> s;
for (int i = 1; i < n - 1; i++) cin >> temp;
cin >> e;
cout << (s < e ? "YES\n" : "NO\n");
}
}
|
cs |
코드의 내용이다. 공간 복잡도는 O(1), 시간 복잡도는 O(n)이다.
'알고리즘 문제풀이 공부' 카테고리의 다른 글
| 알고리즘 동아리 활동#2 이분 탐색 연습문제 풀이 (0) | 2020.11.27 |
|---|---|
| 알고리즘 동아리 활동#1 그리디 알고리즘 연습문제 풀이 (0) | 2020.11.27 |
| [백준 2618] 경찰차 : 동적 계획법 연습하기 (0) | 2020.05.25 |
| [백준 17613] 점프 : 수의 규칙성을 이용한 최적화 (0) | 2020.04.28 |
| [백준 1398] 동전 문제 : 수의 규칙성을 이용한 최적화 (0) | 2020.04.27 |
