때가 매우 늦었지만 간단히 해설을 써 봅니다. 말투는 다른 자료로 사용한 것이라 이해해 주세요 (__) 문제 링크에는 리베셋에서 수고해 주시겠습니다.
참조 링크: 2nd KPC 결과 - http://algospot.com/zbxe/news/46930
A. Anagram Number [ 문제 ]
주어진 입력의 숫자들을 비내림차순으로 정렬하여, 맨 첫 숫자가 0인 경우는 0이 아닌 가장 앞쪽의 값을 찾아 서로 swap하면 된다. 특별히 n == 0인 경우를 조심한다.
B. Bi-station Search [ 문제 ]
두 원 사이의 거리 관계에 따라 경우를 분류한다. 즉, 두 원의 중심 사이의 거리를 d라 하고 각각의 반지름을 r1, r2(WLOG r1 >= r2)라 하면
d = 0, d == r1 - r2, d == r1 + r2, 0 < d < r1 - r2, r1 - r2 < d < r1 + r2, r1 + r2 < d 등의 경우로 나눌 수 있다. 두 원 사이의 관계는 공교육 교과 과정에 등장한다.
그러나, d와 r1, r2를 실수 연산하게 되면 floating point precision 문제로 잘못된 답을 내어놓게 된다. 예를 들어 밑변의 길이가 10억, 높이가 1인 삼각형을 생각하면 빗변의 길이를 구하면 실수 오차로 인하여 적절하지 않은 값이 나오게 될 것이다. 따라서 위 식들의 양변을 적당히 제곱하여 거리를 구함에 있어 제곱근을 사용하지 않고 모든 연산을 64-bit integer 내에서 처리하도록 한다.
C. Voting [ 문제 ]
Implement-this 형태의 문제이다. 문제 description을 충실히 이해하였다면 자잘한 실수를 하지 않는 것이 핵심이다.
D. Duel [ 문제 ]
가장 전형적인 greedy 문제로, 두 집합에서 하나씩 매칭할 때에는 한 쪽을 정렬해 놓고 생각하면 편리하다. 한 쪽을 정렬해 두면, 다른 아래쪽을 어떤 상대와 맞붙여야 할 지 쉽게 판단할 수 있다. 가장 센 우리 팀 선수부터, 상대팀에 내가 이길 수 있는 상대가 존재한다면 이길 수 있는 가장 센 상대 팀 선수와 맞붙이면 된다. 없으면 가장 센 상대와 맞붙일 수 있다. (물론 그 이후로는 따질 필요 없이 전패지만)
E. KTX [ 문제 ]
겹쳐 보이는 것을 제거하지 않는다고 하면 유명한 구간 겹침 문제가 된다. 겹쳐 보이는 것을 처리하기 위해서, 어떤 한 전봇대가 보이는 구간을 X라 하면 다른 N-1개의 전봇대에 대해 겹치게 되는 위치를 각각 ci라 놓고 X - {c1, c2, ..., cn-1}을 어떤 형태의 구간으로 표현할 지 생각해보면, 하나의 거대한 폐구간 내에 구멍이 뚫리는 것과 같으므로 구간을 반개구간/폐구간/개구간 등으로 쪼개어 나타낼 수 있음을 알게 된다. 쪼갠 이후에는 기존의 문제와 동일하게 정렬한 후 세면 된다.
F. Squarefree [ 문제 ]
소수들을 적당히 구한 후, parametric search로 N개의 제곱으로 나누어떨어지는 수가 등장하게 되는 최초의 위치를 찾는다. 이 때 제곱으로 나누어떨어지는 수의 개수는 Inclusion-Exclusion을 통해 세는데, 소수들의 제곱의 곱이 기하급수적으로 증가하므로 in-ex principle에 따라 탐색 깊이는 실제로 얼마 되지 않는다. complexity 분석을 빡세게 한다면 prime을 찾는 것이 가장 time-consuming task임을 알 수 있다.
G. Ordinal [ 문제 ]
CLRS(introduction to algorithms 2/e)의 sorting network 항목을 보면 zero-one principle이라는 절이 있는데, 이는 N개의 입력을 갖는 어떤 sorting network를 검증하기 위해서는 각 변수를 0 혹은 1로, 즉 2^N개의 경우만 따져 보아도 가능함을 증명한다. 이 원리를 이용하여 각 변수를 0 혹은 1로 두어 계산해 보고, 결과값에 따라 가능한 순위를 표시해두어 유일하게 존재하는지 확인하면 된다.
H. Extra Pipes [ 문제 ]
0-1 knapsack 문제인데, 일반적으로 weight에 대해서 DP로 풀기도 하고 2^N으로 탐색하기도 한다. 이 문제에서는 어느 쪽도 해결될 수 없을 것처럼 보이지만, 입력을 절반으로 쪼개서 2^(N/2) 개의 두 뭉치로 쪼갠 후 양쪽을 정렬하여 훑고 올라가면서 합이 나누어 떨어지는 것이 존재하는지 확인함으로써 풀 수 있다.
I. Connection Panic [ 문제 ]
Graph임을 온몸으로 설명하고 있는 문제인데, Bi-connected components를 구현할 줄 안다면 쉽게 풀리는 문제이다. bi-connected components에 의해 component graph(tree)를 그린 이후, 어느 부분을 절단하는 것이 가장 좋은지 component tree 위에서 DFS로 탐색하면 된다. 구현이 매우 어렵다. (덧: 이 문제를 그때 참가자 분들이 진작에 풀었으면 이번 인터넷 예선에서 한문제 건졌지 말입니다..)
J. Drawing ladder [ 문제 ]
주어진 데이터로부터 directed acyclic graph(dag)를 얻을 수 있다. 이 dag로부터 2^N state DP를 정의하여 풀 수 있다. 즉, 어떤 index를 할당한 적이 있는지를 따짐으로써 경우의 수를 셀 수 있다. 2^N DP가 무엇을 의미하는 지 잘 모르겠다면, 전형적인 TSP 문제에 대한 DP 풀이를 찾아보면 도움이 될 것이다.
Being
때가 매우 늦었지만 간단히 해설을 써 봅니다. 말투는 다른 자료로 사용한 것이라 이해해 주세요 (__) 문제 링크에는 리베셋에서 수고해 주시겠습니다.
참조 링크: 2nd KPC 결과 - http://algospot.com/zbxe/news/46930
A. Anagram Number [ 문제 ]
주어진 입력의 숫자들을 비내림차순으로 정렬하여, 맨 첫 숫자가 0인 경우는 0이 아닌 가장 앞쪽의 값을 찾아 서로 swap하면 된다. 특별히 n == 0인 경우를 조심한다.
B. Bi-station Search [ 문제 ]
두 원 사이의 거리 관계에 따라 경우를 분류한다. 즉, 두 원의 중심 사이의 거리를 d라 하고 각각의 반지름을 r1, r2(WLOG r1 >= r2)라 하면
d = 0, d == r1 - r2, d == r1 + r2, 0 < d < r1 - r2, r1 - r2 < d < r1 + r2, r1 + r2 < d 등의 경우로 나눌 수 있다. 두 원 사이의 관계는 공교육 교과 과정에 등장한다.
그러나, d와 r1, r2를 실수 연산하게 되면 floating point precision 문제로 잘못된 답을 내어놓게 된다. 예를 들어 밑변의 길이가 10억, 높이가 1인 삼각형을 생각하면 빗변의 길이를 구하면 실수 오차로 인하여 적절하지 않은 값이 나오게 될 것이다. 따라서 위 식들의 양변을 적당히 제곱하여 거리를 구함에 있어 제곱근을 사용하지 않고 모든 연산을 64-bit integer 내에서 처리하도록 한다.
C. Voting [ 문제 ]
Implement-this 형태의 문제이다. 문제 description을 충실히 이해하였다면 자잘한 실수를 하지 않는 것이 핵심이다.
D. Duel [ 문제 ]
가장 전형적인 greedy 문제로, 두 집합에서 하나씩 매칭할 때에는 한 쪽을 정렬해 놓고 생각하면 편리하다. 한 쪽을 정렬해 두면, 다른 아래쪽을 어떤 상대와 맞붙여야 할 지 쉽게 판단할 수 있다. 가장 센 우리 팀 선수부터, 상대팀에 내가 이길 수 있는 상대가 존재한다면 이길 수 있는 가장 센 상대 팀 선수와 맞붙이면 된다. 없으면 가장 센 상대와 맞붙일 수 있다. (물론 그 이후로는 따질 필요 없이 전패지만)
E. KTX [ 문제 ]
겹쳐 보이는 것을 제거하지 않는다고 하면 유명한 구간 겹침 문제가 된다. 겹쳐 보이는 것을 처리하기 위해서, 어떤 한 전봇대가 보이는 구간을 X라 하면 다른 N-1개의 전봇대에 대해 겹치게 되는 위치를 각각 ci라 놓고 X - {c1, c2, ..., cn-1}을 어떤 형태의 구간으로 표현할 지 생각해보면, 하나의 거대한 폐구간 내에 구멍이 뚫리는 것과 같으므로 구간을 반개구간/폐구간/개구간 등으로 쪼개어 나타낼 수 있음을 알게 된다. 쪼갠 이후에는 기존의 문제와 동일하게 정렬한 후 세면 된다.
F. Squarefree [ 문제 ]
소수들을 적당히 구한 후, parametric search로 N개의 제곱으로 나누어떨어지는 수가 등장하게 되는 최초의 위치를 찾는다. 이 때 제곱으로 나누어떨어지는 수의 개수는 Inclusion-Exclusion을 통해 세는데, 소수들의 제곱의 곱이 기하급수적으로 증가하므로 in-ex principle에 따라 탐색 깊이는 실제로 얼마 되지 않는다. complexity 분석을 빡세게 한다면 prime을 찾는 것이 가장 time-consuming task임을 알 수 있다.
G. Ordinal [ 문제 ]
CLRS(introduction to algorithms 2/e)의 sorting network 항목을 보면 zero-one principle이라는 절이 있는데, 이는 N개의 입력을 갖는 어떤 sorting network를 검증하기 위해서는 각 변수를 0 혹은 1로, 즉 2^N개의 경우만 따져 보아도 가능함을 증명한다. 이 원리를 이용하여 각 변수를 0 혹은 1로 두어 계산해 보고, 결과값에 따라 가능한 순위를 표시해두어 유일하게 존재하는지 확인하면 된다.
H. Extra Pipes [ 문제 ]
0-1 knapsack 문제인데, 일반적으로 weight에 대해서 DP로 풀기도 하고 2^N으로 탐색하기도 한다. 이 문제에서는 어느 쪽도 해결될 수 없을 것처럼 보이지만, 입력을 절반으로 쪼개서 2^(N/2) 개의 두 뭉치로 쪼갠 후 양쪽을 정렬하여 훑고 올라가면서 합이 나누어 떨어지는 것이 존재하는지 확인함으로써 풀 수 있다.
I. Connection Panic [ 문제 ]
Graph임을 온몸으로 설명하고 있는 문제인데, Bi-connected components를 구현할 줄 안다면 쉽게 풀리는 문제이다. bi-connected components에 의해 component graph(tree)를 그린 이후, 어느 부분을 절단하는 것이 가장 좋은지 component tree 위에서 DFS로 탐색하면 된다. 구현이 매우 어렵다. (덧: 이 문제를 그때 참가자 분들이 진작에 풀었으면 이번 인터넷 예선에서 한문제 건졌지 말입니다..)
J. Drawing ladder [ 문제 ]
주어진 데이터로부터 directed acyclic graph(dag)를 얻을 수 있다. 이 dag로부터 2^N state DP를 정의하여 풀 수 있다. 즉, 어떤 index를 할당한 적이 있는지를 따짐으로써 경우의 수를 셀 수 있다. 2^N DP가 무엇을 의미하는 지 잘 모르겠다면, 전형적인 TSP 문제에 대한 DP 풀이를 찾아보면 도움이 될 것이다.
15년 전