티스토리 뷰

문제 링크


I. Q-Index


$n$개의 논문들에 대한 인용횟수가 주어지고, $k$번 이상 인용된 $k$편의 논문이 있고, 나머지 $n-k$편의 논문은 모두 인용횟수가 $k$이하일 때, Q-Index는 $k$라고 얘기한다. 가능한 Q-Index 중 가장 큰 값을 구하는 문제다.

매우 쉬운 문제라 0이상 $n$이하의 $k$를 정한 뒤, 실제로 $k$가 Q-Index가 되는지 확인하는 $O(n^2)$ 방법과 인용횟수 배열을 내림차순으로 정렬한 뒤에 이를 더 빠르게 계산하는 $O(n \lg n)$ 방법 두 가지가 있다.



L. Trucks


길이가 $w$인 다리가 있고, $n$개의 트럭이 있다. 트럭이 일렬로 줄을 지어 다리를 통과하는데 매순간 다리 위에 있는 트럭 무게 합이 $L$을 넘어서는 안된다. 이 때, 모든 트럭이 다리를 건너기 위해 필요한 최소 시간을 구하는 문제다.

순서대로 트럭이 다리를 건널 수 있는 순간, 바로 건너게 해주는 것이 전체 시간을 최소화한다. 그러므로 이 문제는 단순한 구현을 의도하며, 단순히 구현했을 때 시간복잡도는 $O(nw)$이다.



A. Binary Tree


높이가 $k$인 완전이진트리가 주어진다. 루트에서 각 리프노드까지의 거리가 모두 같도록 간선들의 거리를 증가시키는데, 최종적으로 간선 길이 합을 최소화하는 문제다.

루트에서 각 리프노드로 가는 거리가 모두 같기 위해서는 각 노드마다 그 노드의 서브트리에 있는 리프노드에 가는 거리가 모두 같아야한다. 때문에 이 문제는 재귀적으로 생각할 수 있다. 노드마다 자식 노드에 대해 부분 문제를 해결한다. 그 다음 노드에서 두 자식 노드로 가는 거리가 같도록 맞춰주면 된다.



J. Railway


$n$개의 수평 선분이 주어졌을 때, 주어진 수평 선분들을 최대한 많이 포함하는 길이가 $L$인 새로운 수평 선분을 만드는 문제다.

우선 주어진 $n$개의 수평 선분을 오른쪽 끝 점 기준으로 오름차순 정렬한다. $i$ 수평 선분과 길이가 $L$인 새로운 수평 선분의 오른쪽 끝 점이 같다고 했을 때, 포함되는 수평 선분의 개수를 순서대로 구할 수 있다. 이는 수평 선분이 오른쪽 끝 점 기준으로 오름차순 정렬되어 있을 때, heap을 통해 계산할 수 있다. 전체 시간복잡도는 $O(n \lg n)$이다.



C. Frogs


시작 영역이 문제의 그림 아래쪽에 있고, 끝 영역이 그림 위쪽에 있다. 사이에 여러 통나무(수평 혹은 수직 선분)들이 있고, 선분 안에서 걸어다니는데 에너지는 들지 않고, 선분 사이를 뛰어다닐 때만 에너지가 든다. 또한, 선분 사이를 뛰어다닐 때 뛰는 최대 거리의 제한이 있다. 이 때 시작 영역에서 끝 영역까지 최소의 에너지로 이동하는 문제다.

정점 개수가 최대 10,000개이고, 그래프가 완전 그래프일 때 최단 거리를 구하는 문제다. 이 때 Dijkstra Algorithm은 $O(n^2)$의 시간복잡도를 가지고, 이는 1초안에 나온다. 때문에 이 문제는 선분 사이의 거리를 적절히 계산만하면 $O(n^2)$ Dijkstra Algorithm으로 해결할 수 있다. 각 정점 사이의 거리는 메모리에 저장할 필요도 없이 필요할 때마다 계산해주면 된다. 한 가지 코너 케이스로는 통나무를 거치지 않고 바로 시작 영역에서 끝 영역으로 가는 경우가 있다.



D. Message Passing


D[0] = 1

D[i < 0] = 0

D[i > 0] = D[i-1] + D[i-2] + ... + D[i-d] 일 때, D[t]를 구하는 문제다.

다만, t가 최대 2,000,000,000이므로 단순한 문제는 아니다. 이는 일차원 단순 점화식을 행렬로 바꾸어 D[t]를 $O(d^3 \lg t)$에 계산할 수 있다. 행렬식은 $d$ 값에 따라 달라지는데, 아래는 $d=3$일 때, 행렬식 풀이를 식으로 나타낸 것이다.

때문에 위 $d \times d$ 크기 행렬의 $t$승의 첫 행, 첫 열의 값은 $D_t$이 된다. 행렬의 $t$승은 repeated squaring을 통해 $O(d^3 \lg t)$ 시간복잡도로 구할 수 있다.



F. Palindromic


$\theta \leq 2\frac{|u|}{|w|}$를 만족하는 $w=uvu^R$로 나타낼 수 있을 때 문자열 $w$를 Θ-palindrom이라 정의한다. 길이가 $n$인 문자열이 주어졌을 때, 주어진 문자열을 Θ-palindrom인 문자열들을 이은 것으로 볼 수 있는데, 이 때 최소 개수의 Θ-palindrom인 문자열들을 이어 만드는 문제다.

L[i][j] = i번째 문자부터 j번째 문자까지의 부분문자열을 $w$로 볼 때, $u$의 가능한 최대 길이로 정의한다.

L배열은 시간복잡도 $O(n^2)$에 계산할 수 있고, 2 바이트 정수형을 사용할 수 있다. 이 문제에서 최적화를 요구하진 않지만, L배열 계산 순서를 어떻게 정하느냐에 따라 low level에서 메모리 접근을 효율적 바꿀 수 있으며 실행 시간을 2배 정도 줄일 수도 있다.

계산한 L배열을 이용해서 아래 DP를 해결할 수 있다.

D[i] = 주어진 문자열의 i번째 문자까지 Θ-palindrom인 문자열들을 이용하여 이었을 때, 사용한 Θ-palindrom인 문자열들의 최소 개수

DP를 해결하는 시간복잡도 또한 $O(n^2)$이다.



G. Planar Drawing


입력의 첫 수로 1이 주어지면, 주어지는 그래프가 평면그래프인지 확인하고, 입력의 첫 수로 -1이 들어오면 주어진 그래프가 $K_5$나 $K_{3,3}$의 subdivision인지 확인하는 문제다.

두 가지의 알고리즘을 구현하면 된다. 우선, 평면그래프인지 확인하는 문제에서는 입력으로 인접한 정점의 순서가 반시계방향으로 주어진다. a번 정점과 b번 정점을 잇는 양방향 간선을 두 방향성 간선으로 나누자.

예를 들어, 아래 그림처럼 a번 정점에서 b번 정점으로 가는 간선 번호에 해당하는 평면과 b번 정점에서 a번 정점으로 가는 간선 번호에 해당하는 평면을 생각할 수 있다.


   

위 그림에서 각 간선 번호에 해당하는 평면은 빨간색 화살표가 가르키는 평면이다. 이처럼 $2E$개의 간선에 대해 각각 평면을 대응 시킬 수 있다. 그리고 아래 그림처럼 서로 다른 간선에 해당하는 평면이지만 실제로 같은 경우가 있다.


위 그림에서 a번 정점에서 c번 정점으로 가는 간선 번호에 해당하는 평면과, d번 정점에서 a번 정점으로 가는 간선 번호에 해당하는 평면이 실제로는 같다. 실제로 같은 평면끼리 union-find를 할 수 있다. 이후에는 결국 그래프에서 평면 개수 F를 계산할 수 있다. 평면 개수를 구한 뒤에 그래프가 평면그래프인지는 오일러식 $V-E+F = 2$인지 확인하면 된다.


둘째로, 주어진 그래프가 $K_5$나 $K_{3,3}$의 subdivision인지 확인하는 문제를 해결해야한다. $K_5$와 $K_{3,3}$ 둘 다 모든 정점의 차수가 2보다 크다. 따라서 차수가 2인 노드를 간선에 녹이며 없앨 수 있다. 없앤 후에 남아있는 정점 개수에 따라 실제로 그 그래프가 $K_5$나, $K_{3,3}$이 되는지 확인하면 된다. $K_5$는 모든 정점 사이에 간선이 있는지 확인만 하면 되므로 까다롭지 않으며 $K_{3,3}$인지 확인하는 방법은 여러가지가 있을 것으로 생각된다.



E. Meteor Shower


$n$개의 볼록다각형이 y = 0 직선 위에 주어진다. 이 때 원점에서 보이지 않는 볼록다각형의 개수를 세는 문제다.

우선, 주어진 볼록다각형들을 아래 그림처럼 아래로 볼록한 볼록 체인으로 바꿀 수 있다.


원점 기준으로 봤을 때, 볼록다각형의 위쪽은 쓸모가 없으므로 아래쪽 부분을 볼록체인으로 가지고 있는다. 그리고 볼록체인의 각 점을 각도 순서로 정렬해서 번호를 매긴다. 그러면 위 세 개의 볼록체인을 다음과 같이 구간으로 표현할 수 있다: [1-5], [4-9], [8-12]

이제 제일 오른쪽 각도 구간(번호가 작은쪽이 오른쪽)부터 시작해서 반시계방향으로 모든 각도 구간에 대해 가장 앞에 있는, 즉, 원점에서 봤을 때 보이는 볼록체인이 무엇인지 구할 것이다. 이는 볼록 체인이 set(집합) 구조에 insert 되고, erase 된다고 생각할 수 있다. 따라서 set의 정렬기준을 볼록체인이 앞에 있는지 뒤에 있는지 잘판단해주면 단순한 set 사용으로 이를 해결할 수 있다.



H. Project Team


$m$명의 일꾼이 있고, $n$일 동안 일해야한다. 일꾼은 여러 가지의 휴가 계획을 가지고 있다. 휴가 계획이 없는 때에는 무조건 일한다. 모든 일꾼은 $p$일 이상 $p'$일 이하 일하고, $i$번째 날에는 $q_i$명 이상 $q_i'$명 이하 일해야한다. 한 일꾼은 여러 휴가 계획이 있을 수 있는데, 한 휴가 계획은 $[r, r']$일 사이에 적어도 $d$일 이상 쉬어야함을 의미한다. 일꾼을 휴가 계획을 포함하여 모든 조건을 만족시킬 수 있는지 판단하고 만족한다면 각 일꾼이 어느 날 쉬는지 출력하는 문제다.

이 문제는 L-R max flow 문제(Circulation problemMaximum flows with Edge DemandsMax-Flow Extensions 등)로 변형할 수 있다. 간선마다 상한(일반적인 max-flow에서 유량) 뿐만 아니라 하한(lower bound) 또한 존재하며, 모든 간선에 대해서 하한과 상한을 만족하는 flow가 있는지 확인하는 문제다. 1번 입력 예제를 아래와 같이 하한과 상한이 있는 그래프로 표현할 수 있다. 아래 그래프에서 하나의 확장경로는 한 일꾼이 하루 쉬는 것을 의미한다.


L-R max flow는 여러 방법으로 해결할 수 있다.


방법 1) a번 정점에서 b번 정점으로 가는 하한 l, 상한 r인 간선이 있을 때, a번 정점에서 b번 정점으로 가는 유량 l, 비용 -1인 간선, 유량 r-l, 비용 0인 간선으로 만든 뒤 mincost-maxflow

방법 2) a번 정점에서 b번 정점으로 가는 하한 l, 상한 r인 간선이 있을 때, 새로운 source에서 b번 정점으로 가는 유량 l인 간선 추가, a번 정점에서 새로운 sink로 가는 유량 l인 간선 추가, a번 정점에서 b번 정점으로 가는 유량 r-l인 간선으로 만들고, 기존 sink에서 기존 source로 가는 유량 무한인 간선 추가 이후 최대 유량이 l의 합이 되는지 확인


아래 코드는 방법 2로 구현되어 있으며, 0.01초안에 답을 계산한다.



B. Diameter


2차원 좌표 평면에 $n$개의 점이 주어진다. 각 그룹에 속한 점들 중 제일 먼 두 점 사이의 거리의 합이 최소가 되도록 그룹을 나누는 문제다.

전체 $n$개의 점 중 제일 먼 두 점을 $t_1$, $t_2$라 하자. 자명히 $t_1$과 $t_2$는 서로 다른 그룹에 속해야한다. 또 다른 말로는 답은 $t_1$과 $t_2$사이 거리보다 같거나 작다. 이제 해야하는 것은 $t_1$과 $t_2$ 거리보다 작은 답이 존재하는지 확인하는 것이다. 답이 존재한다면 아래 그림처럼 $t_1$이 속한 그룹은 왼쪽 원 안에, $t_2$가 속한 그룹은 오른쪽 원 안에 있을 것이고, 두 원은 만나거나 교차하지 않는다.


때문에 점들을 $t_1$과의 거리 순으로 정렬하고 정렬된 상태에서 어떤 점 i를 기준으로 인덱스가 i보다 같거나 작은 점들을 $t_1$이 속한 그룹, 인덱스가 i보다 큰 점들을 $t_2$ 그룹으로 보고 답이 되는지 계산할 수 있다.



댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
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
글 보관함