티스토리 뷰

1. 방 배정하기 (room)

수용인원이 A, B, C인 세 종류의 방이 있다. 이 방들을 적절히 예약하여 정확히 N명의 사람이 묵을 수 있도록 하는 문제다.


N이 최대 300으로 굉장히 작기 때문에 아래 DP 배열을 정의하고 값을 채우면 된다.

D[i] = 정확히 i명의 사람이 묵을 수 있도록 예약할 수 있는가 (있으면 true, 없으면 false)


점화식은 다음과 같다:

D[i] = D[i-A] OR D[i-B] OR D[i-C]



2. 곡선 자르기 (cut)

N개의 꼭짓점으로 이루어진 직교 단순 다각형이 주어진다. 이를 수평선 y=0으로 자른 뒤 윗부분으로 살렸을 때 선분들이 한 개 이상의 봉우리를 이루는 모양이 나온다. 봉우리들 중에서 다른 봉우리에 의해 포함되지 않는 봉우리의 개수와 다른 봉우리를 포함하지 않는 봉우리 개수를 구하는 문제다.


단순 다각형이란 같은 꼭짓점을 공유하는 두 선분을 제외한 나머지 선분 쌍이 서로 만나거나 교차하지 않는 다각형을 의미한다. 이 문제의 핵심은 봉우리를 잘 찾는 것이다. 봉우리를 찾는 방법은 아래에 첨부된 코드의 22번째 줄부터 32번째 줄까지를 참고하자.


봉우리를 찾은 이후에, 각 봉우리를 [a, b]와 같은 구간으로 나타낼 수 있다. 그리고 단순 다각형이라는 조건 때문에, 모든 구간 쌍은 포함 관계가 없으면서 교차하지 않는다. 봉우리를 구간으로 표현하면 문제의 각색을 전부 제하고 다른 구간에 의해 포함되지 않는 구간의 개수와 다른 구간을 포함하지 않는 구간의 개수를 구하는 문제가 된다. 이는 구간들을 왼쪽 점 기준으로 정렬한 뒤에 손쉽게 해결할 수 있다.



3. 줄 서기 (line)

1부터 N까지 서로 다른 수로 이루어진 크기가 N인 수열, 즉, 크기가 N인 순열(permutation)에 대한 모든 inversion의 정보들이 주어진다. 이 때, 원래의 순열을 복원하는 문제다.


풀이1)

맨 왼쪽 수부터 차례대로 수를 찾아나간다. i번쨰 수는 1부터 N까지 등장하지 않은 수 중에서 k번째로 작은 수가 되는데, 여기서 k는 (i번째 수보다 오른쪽에 있으면서 작은 수의 개수+1)이 된다. 등장하지 않은 수 중에서 k번째로 작은 수를 구하는 작업은 Fenwick tree를 통해 $O(\lg N)$ 시간에 구할 수 있다. 전체 시간복잡도는 $O(M+N \lg N)$이 된다.



풀이2)

수열의 각 원소마다 자신보다 작은 수의 개수를 세어줄 것이다. i번째 원소보다 작은 수의 개수를 cnt[i]라고 하자. 처음에 자신보다 왼쪽에 있는 수는 모두 작다고 가정하고, 자신보다 오른쪽에 있는 수는 모두 크다고 가정한다. 즉, 초기에 cnt[i] = i-1이 된다.


그리고 (a, b)라는 inversion이 입력으로 들어오면 처음 했던 가정 중 일부가 깨지게 된다. 즉, a번째 원소는 b번째 원소보다 왼쪽에 있으면서 더 크게 되기 때문에 cnt[b]가 1 줄어들게 되고, b번째 원소는 a번째 원소보다 오른쪽에 있으면서 더 작기 때문에 cnt[a]가 1 줄어들게 된다. 새로운 inversion에 대한 정보가 들어올 때마다 이처럼 cnt 배열의 값을 관리해줄 수 있다.


전체 시간복잡도는 $O(N+M)$이 된다.



4. 산만한 고양이 (cat)

N개의 정점과 M개의 간선이 있는 무방향성 그래프가 주어진다. 이 그래프에서 정확히 한 개의 정점을 없애 모든 싸이클을 없앨 수 있는 정점들을 모두 구하는 문제다.


이 문제를 해결하기 위해 여러 가지 접근이 떠오른다. 모든 싸이클을 없앨 수 있는 정점이란, 모든 싸이클에 포함된 정점이라고 접근을 할 수도 있다. 그렇지만 풀이는 정점을 없애고 났을 때 남은 모든 연결 요소가 트리가 된다는 사실에 접근해야 편하다.


우선, DFS 트리라는 것을 알아두면 매우 편하다. DFS 트리는 그래프에서 절점이나 절선을 구할 때 주로 이용된다. 왼쪽 그림과 같은 그래프가 있을 때, 오른쪽 그림의 트리는 가능한 DFS 트리 중 하나다. DFS 방문 순서에 따라 DFS 트리의 모양은 달라질 수 있다. 기존 그래프에서 모든 간선은 DFS 트리에서 tree edge(아래로 향한 실선 화살표) 혹은 back edge(위로 향한 점선 화살표) 둘 중 하나가 된다.


어떤 한 정점을 지웠을 때 남은 연결 요소가 모두 트리가 되는지는 DFS 트리를 만들어놓고, 서브트리에 포함된 back edge의 수로 판단할 수 있다. DFS 트리를 만드는 방법과 판단의 자세한 로직은 코드를 참고하자.



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