트리의 지름
문제를 풀기 전에 다음 properties를 알면 좋다.
- '트리의 지름'은 트리에서 찾을 수 있는 가장 긴 경로이다.
- 트리의 지름은 항상 루트 노드를 지나는 것은 아니다.
- 트리의 지름은 최소 2개의 정점을 포함한다.
- 트리의 지름은 유일하지 않을 수 있지만, 임의의 두 정점을 잇는 경로는 유일하다.
또한 다음 방법을 통해 경로를 구할 수 있다.
1. 임의로 한 정점(풀이에선 1번 노드)을 잡고, 그 정점과 가장 멀리 있는 정점(n1)을 찾는다.
2. n1에서 가장 멀리 있는 정점(n2)을 찾으면, n1과 n2가 트리의 지름의 양 끝 점이 된다.
(proof) 유일한 경로 ($n_{1}$, $n_{2}$)가 트리의 지름이 아니라고 가정하자(귀류법)
그렇다면 ∃$n_{3}$, s.t. ($n_{1}$, $n_{3}$)가 트리의 지름이 될 수 있다. 따라서 $n_{1}$, $n_{3}$ 간의 거리 차가 $n_{1}$, $n_{2}$보다 크다는 것인데, 이는 위 method의 2번 과정에서 모순이다.
이를 통해 증명할 수 있는 것은 $n_{1}$이 지름의 한 끝점이라면, ($n_{1}$, $n_{2}$)가 트리의 지름이라는 것이다.
그렇다면 $n_{1}$이 트리의 지름의 한 끝점인 것은 어떻게 증명할까? 위와 같이 귀류법을 적용해 생각해보면 쉽게 구할 수 있다.
코드는 아래와 같다. 크게 dfs를 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
|
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX_N = 10001;
const int inf = 1e9;
const ll INF = 1e18;
int N;
vector< pair<int, ll> > adj[MAX_N];
ll dist[MAX_N];
void dfs(int x)
{
for(auto &i : adj[x]){
int nxt = i.first;
ll nxtDist = i.second;
if(dist[nxt] == -1){
dist[nxt] = dist[x] + nxtDist;
dfs(nxt);
}
}
}
int main()
{
scanf("%d", &N);
for(int i=1; i<=N-1; i++){
int A, B;
ll C;
scanf("%d %d %lld", &A, &B, &C);
adj[A].push_back({B, C});
adj[B].push_back({A, C});
}
// 거리를 -1로 초기화
memset(dist, -1, sizeof(dist));
dist[1] = 0;
dfs(1);
// 루트노드에서 dfs 시행
ll mx = 0, idx = 0;
for(int i=1; i<=N; i++){
if(dist[i] > mx){
mx = dist[i], idx = i;
}
}
// 루트에서 가장 먼 노드 idx에서 dfs 시행
memset(dist, -1, sizeof(dist));
dist[idx] = 0;
dfs(idx);
mx = 0;
for(int i=1; i<=N; i++){
mx = max(mx, dist[i]);
}
printf("%lld\n", mx);
return 0;
}
|
cs |
님 게임 2
굉장히 전형적인 스프러그-그런디 정리의 문제이다. 각 더미에 있는 돌의 수가 그런디 수가 되므로 이들을 모두 xor한 값이 0이 되는지, 아닌지에 따라 누가 이기는지가 결정된다. 일단 xor한 값이 0이 되냐 안되냐에 따라 승패가 결정된다고만 기억하자. 구체적으로 xor한 값이 0이면 누가 이기는지는 예시를 만들어 생각해보라.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n;
int main()
{
scanf("%d", &n);
ll x=0;
while(n--){
ll a;
scanf("%lld", &a);
x^=a;
}
if(x){ cout << "koosaga\n"; }
else{ cout << "cubelover\n"; }
return 0;
}
|
cs |
이항계수 3
$nCr = n! / k!*(n-k)! $의 모듈러 p에 대한 나머지를 구하는 문제이다. p가 소수이므로 페르마의 소정리가 성립한다.
$a^{p-1} = 1 \quad (mod \quad p)$
구하고자 하는 값은 곧, $n! * (k!*(n-k)!)^{-1}$이므로 $(k!*(n-k)!)^(-1) = x \quad (mod \quad p)$라 하면
$x*(k!*(n-k)!)^{p} = (k!*(n-k)!)^{p-1} = 1 (mod \quad p)$이다. 즉, $x$는 $(k!*(n-k)!)^{p}$의 곱셈의 역원임을 알 수 있고, 이는 $ x = (k!*(n-k)!)^{p-2} $를 만족한다.
따라서 구하고자 하는 값은 결국 $ n! * (k!*(n-k)!)^{p-2} $이므로 Divide and Conquer을 통한 power calculation을 통해 구현할 수 있다.
|
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
|
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1e9;
const ll INF = 1e18;
/*
(n, k) = n! / k!*(n-k)!
이는 법 p에 대해 n! * (k!*(n-k)!)^(p-2)와 합동
*/
ll N, K;
const ll p = 1000000007LL;
// factorial 계산
ll fac(ll x)
{
ll ret = 1LL;
for(ll i=1; i<=x; i++){
ret = (ret*i)%p;
}
return ret;
}
// 분할정복
ll DnC(ll x, ll y)
{
if(y == 0LL) return 1LL;
if(y == 1LL) return x;
ll ret = DnC(x, y/2LL) % p;
ret = (ret*ret)%p;
if(y%2 == 0) return ret%p;
else return (ret*(x%p))%p;
}
int main()
{
scanf("%lld %lld", &N, &K);
printf("%lld\n", (fac(N) * DnC( (fac(N-K)*fac(K))%p, p-2 )%p) % p );
return 0;
}
|
cs |
간선 끊어가기 2
Maximum Flow - Minimum Cut Theorem에 의해 minimum cut은 maximum flow를 구하는 것과 동치이고, 잘리는 간선은 곧 maximum flow problem에서 $capacity$와 $flow$가 같은 간선이다. 따라서 maximum flow를 구현하면 된다.
그래프를 표현하기 위해 구성해야 할 것이 3가지이다. 인접리스트(adj), 용량(C), 유량(f)이다.
인접리스트는 연결관계만을 나타낸다. 따라서 bfs를 통해 증가 경로를 탐색할 때 사용한다. 용량과 유량은 간선에 대한 정보를 나타낸다. c[a][b] - f[a][b] > 0이라는 것은, Edge (a, b)가 아직 여유 유량이 남아있다는 뜻이 된다.
아래 코드에서 prv 배열을 간단히 설명하고자 한다. prv 배열은 bfs를 통해 찾는 경로를 역추적하기 위한 변수로, 방문하는 노드 번호 x에 대해, prv[x]는 'x 이전에 방문한 정점의 번호'를 저장한다. 따라서 나중에 유량을 업데이트할 때, i를 prv[i]로 갱신하는 과정을 통해 t에서 s로 갈 수 있게 된다.
|
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
|
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1e9;
const ll INF = 1e18;
const int MAX_N = 501;
int N, M;
vector<int> adj[MAX_N];
int s, t;
ll C[MAX_N][MAX_N], f[MAX_N][MAX_N];
int prv[MAX_N];
queue<int> q;
int main()
{
scanf("%d %d", &N, &M);
for(int i=1; i<=M; i++){
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
adj[a].push_back(b);
adj[b].push_back(a);
C[a][b] = c;
C[b][a] = c;
}
scanf("%d %d", &s, &t);
ll ans = 0LL;
while(true){
queue<int> q;
q.push(s);
memset(prv, -1, sizeof(prv));
prv[s] = 0;
while(!q.empty()){
int x = q.front();
q.pop();
for(int nxt : adj[x]){
if(prv[nxt] == -1 && C[x][nxt] - f[x][nxt] > 0){
prv[nxt] = x;
q.push(nxt);
}
}
}
if(prv[t] == -1) break;
ll min_flow = INF;
for(int i=t; i!=s; i=prv[i]){
min_flow = min(min_flow, C[prv[i]][i] - f[prv[i]][i]);
}
for(int i=t; i!=s; i=prv[i]){
f[prv[i]][i] += min_flow;
f[i][prv[i]] -= min_flow;
}
ans += min_flow;
}
printf("%lld\n", ans);
return 0;
}
|
cs |
파일 합치기
파일 합치기는 유명한 dp 문제이다. 문제의 범위를 통해 차수를 예상해보면 최대 3차까지 가능하다. 후술하겠지만, 시간복잡도는 3차이고 공간복잡도는 2차가 될 것이다.
다음과 같이 배열을 잡자.
$f(s, e) : [s, e]$에 해당하는 파일을 합치는데 필요한 최소 비용
다음 점화식이 성립한다.
$ f(s, e) = min_{k∈[s, e-1]} \quad ( f(s, k) + f(k+1, e) ) + \sum_{i=s}^e a_{i}$
구하고자 하는 것은 f(1, N)이므로 f(1, N)에서 f(k, k) 꼴의 partial problem으로 향하는 Top - Down 기법의 재귀 함수를 구현하자. 점화식 마지막 항에 있는 합 부분을 $O(1)$에 처리하기 위해 prefix sum(부분합)을 이용했음에 유의하여 코드를 확인하라.
|
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
|
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1e9;
const ll INF = 1e18;
const int MAX_N = 501;
int N;
int arr[MAX_N], sum[MAX_N];
int memo[MAX_N][MAX_N];
int dp(int s, int e)
{
// initial value
if(s == e) return memo[s][e] = 0;
if(s+1 == e) return memo[s][e] = arr[s] + arr[e];
// memoization
if(memo[s][e]!=-1) return memo[s][e];
memo[s][e] = inf;
for(int k=s; k<e; k++){
memo[s][e] = min(memo[s][e], dp(s, k)+dp(k+1, e));
}
memo[s][e] += sum[e]-sum[s-1];
return memo[s][e];
}
int main()
{
int T;
scanf("%d", &T);
while(T--){
scanf("%d", &N);
sum[0] = 0;
for(int i=1; i<=N; i++){
scanf("%d", &arr[i]);
sum[i] = sum[i-1] + arr[i];
}
memset(memo, -1, sizeof(memo));
printf("%d\n", dp(1, N));
}
return 0;
}
|
cs |
트리 순회
임의의 트리에 대해 우리는 전위순회(preorder), 중위순회(inorder), 후위순회(postorder)를 정의할 수 있고, 이들은 각각 탐색의 순서에 따라 결정되는 탐색열이다.
전위순회는 탐색의 우선순위가 루트 -> 왼쪽자식 -> 오른쪽자식이고,
중위순회는 탐색의 우선순위가 왼쪽자식 -> 루트 -> 오른쪽자식이며,
후위순회는 탐색의 우선순위가 왼쪽자식 -> 오른쪽자식 -> 루트이다. (루트가 앞이면 전위, 중간이면 중위, 뒤면 후위이다)
위 그래프의 preorder traversal 결과는 ABDCEFG인데, 이를 세 부분으로 나누면 A BD CEFG이다.
세 부분은 각각 루트, 왼쪽 자식을 루트로 하는 서브트리의 전위순회 결과, 오른쪽 자식을 루트로하는 서브트리의 전위순회 결과를 나열한 것과 같다.
즉, 루트를 x로 하여 전위순회하는 함수를 pre(x)라 하면 pre(x)는 다음 연산을 수행한다.
pre(x):
print(x)
if left(x) exists:
pre(left(x))
if right(x) exists:
pre(right(x))
마찬가지로, 중위, 후위 순회에 대해서도 의사코드를 구성할 수 있을 것이다. 이를 구현하면 아래 코드와 같다.
|
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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N;
int l[26], r[26];
// l[0]은 A의 왼쪽 자식, r[0]은 A의 오른쪽 자식
// 0 -> A, 1 -> B, ...
void pre(int node)
{
printf("%c", node+'A');
if(l[node]!='.'-'A') pre(l[node]);
if(r[node]!='.'-'A') pre(r[node]);
}
void in(int node)
{
if(l[node]!='.'-'A') in(l[node]);
printf("%c", node+'A');
if(r[node]!='.'-'A') in(r[node]);
}
void post(int node)
{
if(l[node]!='.'-'A') post(l[node]);
if(r[node]!='.'-'A') post(r[node]);
printf("%c", node+'A');
}
int main()
{
scanf("%d", &N);
getchar();
for(int i=0; i<N; i++){
char a, b, c;
scanf("%c %c %c", &a, &b, &c);
getchar();
l[a-'A']=b-'A';
r[a-'A']=c-'A';
}
pre(0); printf("\n");
in(0); printf("\n");
post(0); printf("\n");
return 0;
}
|
cs |
유클리드 게임
푼 문제들 중 가장 재미있었다. 전형적인 게임이론이고 관찰할 내용도 재미있어서 좋았다.
두 수 A, B에 대해 큰 수에서 작은 수를 k번 빼는 연산을 두 플레이어가 돌아가며 반복한다. 이 때, A, B는 항상 양의 값을 유지하며, 먼저 한 수를 0으로 만드는 플레이어가 승리하게 된다.
게임을 파악하기 위해 (25, 7)의 상황에 대해 생각해보자. (25, 7)에서 플레이어가 만들 수 있는 상태는 (18, 7), (11, 7), (4, 7)일 것이다. 그럼 이를 일반화하여 (A, B)에 대해 플레이어가 만들 수 있는 다음 상태를 생각해보면 (A-kB, B) 꼴의 가능한 모든 경우일 것이다. 하지만 A, B는 int integer의 범위를 만족하므로 가능한 경우가 매우 많을 수 있다.
A-kB > 0이지만 A-(k+1)B < 0인 k를 '(A, B)의 임계'라는 값으로 정의하자. 그러면 이 값은 [$\frac{A}{B}$]가 될 것이다.
관찰할 수 있는 사실은, 플레이어가 (A, B)의 임계 * B 만큼을 뺀다면 다음 턴에서 수의 대소가 뒤집힌다. 증명은 간단하므로 생략한다.
이제 플레이어가 (A, B)의 임계보다 작은 수를 골라 (A, B)를 (A-kB, B)로 만들었다고 하자. 다음 플레이어가 취할 수 있는 행동은 '임계만큼 빼서 수의 대소를 뒤집기'와 '임계보다 적은 수를 빼기'이다.
즉, 임계보다 작은 수를 골라 빼는 것은 '(A, B)의 대소상태를 유지'하며 다음 턴인 상대방에게 기회를 미루는 것이다.
따라서 우리는 위에서 보았던 (25, 7) -> (18, 7), (11, 7), ...과 같이 가능한 모든 수를 고려하는 것이 아니라,
'((A, B)의 임계-1)만큼을 빼던지', '임계만큼을 빼서 A, B의 대소를 뒤집던지'만 고려하면 되는 것이다.
즉, '(A, B)의 임계'를 k라 하면(단, A>B) 플레이어가 만들 수 있는 상태는 (A-(k-1)B, B) 혹은 (A-kB, B) (대소가 바뀜)이다.
이제 (A, B)에서 나올 수 있는 경우를 (A-(k-1)B, B), (A-kB, B)로 줄였으므로 문제를 간단히 해결할 수 있다.
이제 플레이어 A가 승리하는지 여부를 따지는 함수 f(A, B, t)를 설정한다. f(A, B, t)가 1이라면 (A, B)에 대해 A는 항상 승리한다. t가 의미하는 것은, t가 1이면 플레이어 A의 차례, 아니면 B의 차례이다.
만약 A|B이거나 B|A라면 f(A, B, t) = t이다. (t가 1이면 A 차례이므로 A가 승리 -> 1 반환)
그렇지 않다면 t == 1인 경우와 아닌 경우를 나누어주면 된다. 자세한 내용을 코드의 주석을 참고하면 좋을 것 같다.
Game Theory의 형태로 재귀를 구성하고 dp를 적용할지 고민했는데, 유클리드 호제법을 생각해보면 재귀 깊이가 그렇게 깊지 않을 것이라는 정성적인 추론에 의거해 메모이제이션을 적용하지 않았다.
|
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 <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 1e9;
const ll INF = 1e18;
// 1이면 A가 승리
bool f(int A, int B, int t)
{
if(A < B) swap(A, B);
if(A%B == 0) return t;
// A가 선공이면
if(t == 1){
if(A%B+B == A) return f(A%B, B, (t+1)%2);
else return f(A%B, B, (t+1)%2) || f(A%B+B, B, (t+1)%2);
// A를 A%B로 만들어 대소를 전환하거나, A%B+B로 만들어 대소를 유지하거나
// 두 방법 중 하나에 대해 필승이라면 참이다!
}
// B의 공격 차례
else{
if(A%B+B == A) return f(A%B, B, (t+1)%2);
else return f(A%B, B, (t+1)%2) && f(A%B+B, B, (t+1)%2);
// B가 어떤 방법을 취하더라도 f는 1이어야하므로 AND로 묶어줌
}
}
int main()
{
while(true){
int A, B;
scanf("%d %d", &A, &B);
if(!A && !B) break;
if(f(A, B, 1)){
printf("A wins\n");
}
else printf("B wins\n");
}
return 0;
}
|
cs |