티스토리 뷰

문제 링크


I. Robot


로봇은 초기에 동쪽을 바라보고 있고, $(0, 0)$ 위치에 있다. 회전하는 명령과 앞으로 이동하는 명령이 주어졌을 때, 주어진 정사각형 범위를 벗어나는지 아닌지 확인하고 벗어나지 않으면 최종 위치를 출력하는 문제다.


단순한 구현 문제이므로 설명은 생략한다.



G. Percolation


$M \times N$ 크기의 격자판 상황이 주어진다. 1은 장애물을 의미하고 0은 장애물이 없는 빈 칸을 의미한다. 맨 위에서 물을 붓는데, 상하좌우로 인접한 빈 칸으로 물이 흐른다. 이 때 물이 아래로 나오는지 확인하는 문제다.


물통 붓기(Flood-Fill)을 구현하면 된다. 물통 붓기의 시작점은 맨 윗 줄의 모든 빈 칸이다. 시간복잡도는 $O(MN)$이 된다.



L. Virus


이진트리가 주어진다. 초기에 트리의 루트는 감염되어있고, 매 순간 아직 감염되지 않은 한 정점에 백신을 투여할 수 있다. 한 번 백신이 투여되면 이후에 영원히 감염되지 않는다. 백신을 한 정점에 투여한 직후, 감염된 모든 정점에서 백신을 투여받지 않은 인접한 정점으로 감염이 확산된다. 이 때, 백신을 적절히 투여하여 감염되는 정점의 수를 최소화하는 문제다.


이 문제를 쉽게 해결하기 위해 주어지는 트리가 이진트리라는 사실을 숙지해야한다. 이진트리이므로 매순간 마지막으로 감염된 정점의 왼쪽 자식 정점에 백신을 투여할 것인지, 오른쪽 자식 정점에 백신을 투여할 것인지 두 가지 선택지 밖에 존재하지 않는다. 각 선택지 중에 무엇이 이득인지 계산해서 이득인 선택을 하면 문제를 $O(N)$ 시간에 해결할 수 있다.



B. Football


$n$개의 팀이 리그에 있고, 모든 팀들은 서로 정확히 한 판씩 경기를 했다. 경기의 결과는 무승부 없이 항상 승패로 갈린다. 각 팀이 승 수가 주어졌을 때, 가능한 조합인지 판단하는 문제다.


$i$번 팀의 승 수를 $a_i$라고 하고, 일반성을 잃지 않고 $a_1 \leq a_2 \leq a_3 \leq \dots \leq a_n$이라 하자. 1이상 $n$이하인 모든 $k$에 대해 아래 조건을 만족하면 필요충분하게 가능한 조합인지가 결정된다. (관련식: Fulkerson–Chen–Anstee theorem)



$O(n^2)$ 방법: 승 수가 높은 팀부터 차례대로 처리되지 않은 나머지 팀에 대해 승 수가 높은 순서대로 패배 수 만큼 져준다.



C. House Rental


$n$개의 건물이 일차원 좌표계에 있고, 건물의 종류 수는 $k$개다. 정수 좌표 중 한 곳에 숙소를 잡을 것인데, 각 종류마다 제일 가까운 건물과의 거리 중 최대값을 최소화하는 문제다. 만약 최소화할 수 있는 숙소의 위치가 여러 개라면 그 중 좌표값이 제일 작은 숙소의 위치를 구한다.


우선 건물들을 좌표 순서로 정렬하자. 그리고 Parametric search로 $d$를 정하고, 각 종류마다 제일 가까운 건물과의 거리가 $d$이하가 되는지 판단하는 결정 문제를 생각하자. $i$번 건물의 위치가 $x_i$일 때, $i$번 건물이 영향을 주는 숙소의 $x$ 좌표 범위는 $[x_i-d, x_i+d]$이다. 좌표 범위를 구간이라고 생각했을 때, 크기 $2d$인 구간이 $n$개 존재한다. 그리고 숙소로 가능한 위치는 해당 $x$좌표에 수직선을 그었을 때, $k$개의 종류 구간을 모두 지나는 위치가 될 것이다. 결정 문제에서 해당 위치가 존재하는지 확인하고, 가능한 위치 중 가장 왼쪽 위치를 찾으면 되므로, 결정 문제는 $O(n + k)$ 시간안에 해결된다.


따라서, 가능한 $d$의 범위가 $X$일 때 $O(N \lg N + N \lg X)$ 시간안에 문제를 해결할 수 있다.



D. Independent Edges


총 $n$개의 정점과 $m$개의 간선으로 이루어진 이분그래프가 여러 개 주어진다. 해당 이분그래프에서 maximum independent edge set과 maximum independent vertex set을 구하는 문제다.


문제에서 말하는 independent edge set은 matching이라고 한다. 때문에 maximum independent edge set은 maximum matching이 된다. 그래프에서 임의의 vertex cover를 구하고 vertex cover에 있는 정점들을 제외하면 independent vertex set이 된다. 때문에 minimum vertex cover를 구하여, minimum vertex cover에 있는 정점들을 제외한 나머지 정점들은 maximum independent vertex set이 된다.


이분그래프에서 maximum matching과 minimum vertex cover 모두 이분매칭을 통해 구할 수 있다. 이분매칭은 주로 Hopcroft-Karp, maximum flow 등으로 구한다. Hopcroft-Karp algorithm으로 이분매칭을 구현하면, $O(m \sqrt{n})$ 시간에 이 문제를 해결할 수 있다.



H. Power Supply


$N$개의 정점으로 구성되어 있는 트리가 주어진다. 각 정점은 supply 혹은 demand다. 주어진 트리를 여러 개의 서브트리로 나눌 때, 단 하나만의 supply를 포함해야하며 서브트리에 있는 하나의 supply는 같은 서브트리에 존재하는 demand들에게 특정 조건을 만족하며 전력을 공급해야한다. 이 때 조건에 맞게 서브트리를 나누는 것이 가능한지 확인하는 문제다.


편하게 supply는 공급량을 양수로, demand는 수요를 음수로 적어 표현하겠다. 1번 정점을 루트로 두어 rooted tree를 만들고, 각 정점마다 그 정점을 루트로 한 서브트리에 대해 문제를 재귀적으로 해결할 것이다. i번 정점을 루트로한 서브트리에 대해서 발생할 수 있는 경우는 두 가지 뿐이다.


1. 전력 공급이 충분하여 i번 정점에서 i번 정점의 부모 정점으로 갈 때, 전력이 공급되는 경우

2. 수요가 공급을 초과하여 i번 정점에서 i번 정점의 부모 정점으로 갈 때, 전력을 필요로 하는 경우


i번 정점이 demand일 때와 supply일 때, 두 경우에 대해 나눠서 생각해보자.


1) i번 정점이 demand일 때



아래에서 위로 오는 파란색 간선은 해당 자식 정점을 루트로 한 서브트리에서 전력이 남아 공급되는 경우를, 위에서 아래로 내려가는 주황색 간선은 해당 자식 정점을 루트로한 서브트리에서 전력이 부족해, 전력을 필요로 하는 경우를 표현한 것이다. 파란색 간선에는 가능한 공급량이 정해져있고, 주황색 간선에는 필요로 하는 전력이 정해져있다. 우선 여러 파란색 간선이 있는 경우 공급량이 제일 큰 간선 하나만 의미가 있다. 나머지는 간선을 잘라 트리를 분리한다. 공급량이 제일 큰 간선 하나로 주황색 간선이 필요로 하는 전력을 모두 공급해줄 수 있으면, i번 정점을 루트로한 서브트리에서 전력 공급이 충분하여 i번 정점의 부모 정점으로 갈 때, 전력이 공급되는 경우가 된다. 그렇지 않다면, 파란색 간선의 공급량이 전부 무의미해지고, 주황색 간선들의 필요량에 i번 정점의 수요을 더해 전력을 필요로 하게 된다. 만약 필요로 하는 전력이 i번 정점과 부모 정점을 연결하는 간선 가중치보다 크다면 불가능한 경우다.


2) i번 정점이 supply일 때



i번 정점이 supply인 경우 간단하다. 우선, 파란색 간선은 무의미해진다. 따라서 파란색 간선들을 모두 잘라 트리를 분리한다. i번 정점의 공급량으로 주황색 간선이 필요로 하는 전력을 만족시키지 못하면 불가능한 경우를 의미하고, 주황색 간선이 필요로 하는 전력을 만족시킨 뒤 남은 전력이 i번 정점이 부모 정점으로 가면서 공급하는 전력량이다. 만약 남은 전력량이 i번 정점과 부모 정점을 연결하는 간선 가중치보다 크다면 간선 가중치 만큼의 전력만 공급하게 된다.


이와 같이 문제를 해결하면 $O(N)$ 시간복잡도로 문제를 해결할 수 있다.



K. Rounding


실험 결과 표가 주어지고, 표의 모든 칸에 적힌 값을 내림 혹은 올림해야해서 정수로 만들어야한다. 정수로 만든 뒤 row sum과 col sum이 유지되도록 만드는 문제다.



위는 예제 1번 처럼 입력이 들어왔을 때, 만들어지는 L-R flow diagram이다. L-R flow는 일반적인 maximum flow와 달리 간선에 유량이 아니라 유량의 하한과 상한이 정해져있다. Source와 sink가 정해져있을 때, 각 간선의 하한과 상한을 모두 만족하는 flow가 존재하는지 확인하는 알고리즘이 L-R flow고, 이는 각 정점에 demand를 매겨 일반적인 maximum flow 문제로 변형하여 구현할 수 있다.



E. Memory Cell


주어진 중위 표현식을 트리로 파싱했을 때, 동일한 서브트리 쌍 중 서브트리의 크기가 제일 큰 서브트리를 후위표기법으로 출력하는 문제다.


까다로워보이는 파싱 문제처럼 보이지만, 주어지는 문자열의 길이 제한이 1,000 밖에 되지 않아 $O(L^2)$ 시간에 파싱을 할 수 있다. 파싱에 대한 설명은 코드를 첨부하는 것으로 대신하겠다.


아래 코드에서 구현한 파싱 방법은 $O(L^3)$ 시간복잡도를 갖는 것 처럼 보이지만, 트리에서 정점의 개수가 $L$개를 넘지 않으므로 시간복잡도가 $O(L^2)$이 된다. 하나의 서브트리를 문자열로 표현할 수 있고, 이 때 문자열의 최대 길이는 $L$에 비례한다. 서브트리의 개수 도한 최대 $L$개이기 때문에 문자열 비교로 서브트리의 동일성을 판단해도 $O(L^2 \lg L)$ 시간복잡도를 갖는다.



F. Meteorites


$n$개의 건물들이 서로 겹치지 않게 주어지고, $k$개의 운석이 주어진다. 운석의 초기 위치와 방향 벡터가 주어졌을 때, 운석에 가장 먼저 닿는 건물의 번호를 구하는 문제다.


만약 운석의 방향 벡터 $x$성분 $dx$가 0인 경우, 이분검색을 통해 제일 먼저 닿는 건물의 번호를 구할 수 있다. 나머지 경우에 대해 일반성을 잃지 않고 운석의 방향 벡터 $x$성분 $dx$가 0보다 크다고 하자. 운석들을 방향 벡터가 수직에 가까운 순서대로 정렬한다. 방향 벡터가 수직에서 수평으로 가까워질 수록 방향 벡터의 방향으로 보이는 건물들은 항상 줄어들기만 한다.


특정 운석에 대해 그 운석의 방향 벡터에 따라 보이는 건물들을 추려낼 수 있는데, 이를 heap과 union-find로 해결할 수 있다. 가려진 건물들을 제외하고 방향에 대해 보이는 건물들에 대해서 특정 운석이 먼저 닿는 건물은 이분검색을 통해 구할 수 있다.


이 풀이는 쿼리를 offline으로 해결하며, 총 시간복잡도는 $O(n \lg n)$이다.



댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
«   2024/03   »
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
글 보관함