8/3~8/6 연습

2017. 8. 6. 20:48알고리즘 문풀/BOJ 연습

그 동안 쉬운 문제만 푸느라 문제 정리를 올리고 싶은 의욕이 없었다. 앞으로는 그냥 의식의 흐름대로 풀리는 문제는 적당히 필터링하겠다.


1052. 물병

http://icpc.me/1052


일단 물병을 무한정으로 사올 수 있기 때문에, 항상 답을 찾을 수 있다. 그냥 입력의 \(N\)보다 큰 최소의 \(2^p\)꼴의 숫자를 찾으면 물병을 1개로 만들 수 있기 때문에, 답은 항상 \(2N\)보다 작다는 것도 알 수 있다.

그런데 그대로 내면 당연히 4%대에서 틀리게 된다. 아이디어를 조금만 발전시키자. \(X\)개의 물병을 압축할 수 있는 최소 개수는 \(X\)를 이진수로 나타냈을 때 각 자리수의 합, 즉 \(s_2 (X)\)가 됨을 알 수 있다. 즉 물병을 더해 가면서 \(s_2 (X) \le K\)가 성립하는지를 체크해주면 되는데, 물병을 1개씩 더하면 \(O(N)\)이 되고, 그 대신 \(X \& -X\) (X의 0 아닌 최초 비트) 값을 더해주면 \(O(lg N)\)만에 문제를 해결할 수 있다.

여담인데, 이진수의 자리수 합을 직접 구현해도 되지만, GCC의 경우 __builtin_popcount라는 함수를 제공한다. CPU 연산을 이용해서 속도도 더 빠르다고 하니 사용해 보자.


Time Complexity : \(O(lg N)\)


13309. 트리 (KOI '16)

http://icpc.me/13309

http://oj.uz/problem/viiew/KOI16_tree


트리에 대한 dynamic connectivity problem이다. 갓-skykhs3의 풀이를 따랐다.

http://drugstoreoftamref.tistory.com/12 에서처럼, 각각의 노드를 DFS-numbering 하여 구간 처리를 할 수 있도록 준비한다.

세그먼트 트리를 준비하는데, 배열(리프 노드)에는 (각 노드에서 가장 높이 올라갈 수 있는 노드의 깊이)를 저장한다.


Update Query : 정점 \(u\)와 그 부모를 끊는 쿼리는 \([dt[u], ft[u]]\) (폐구간 주의!) 의 배열 값을 \(depth[u]\)로 갱신해 주는 쿼리이다. 즉, \(highest[x]\)를 \(max(highest[x], depth[u])\)로 갱신하는 쿼리 를 수행하면 된다.


Check Query : \(highest(LCA(u,v)) == max\{highest(u), highest(v)\}\) 가 성립하면 연결되어 있고, 그렇지 않다면 끊겨 있다.


Time Complexity  : \(O (LCA + Query)\) = \(O(N lg N + Q lg N) \)


14554. The Other Way (HYEA Cup '16)


정점 \(S\)에서 \(E\)로 가는 최단 경로의 개수를 묻는 문제. 킹-갓-HYEA님께서 만드신 문제라 까다롭게 처리해야 할 게 많을 줄 알았는데, 의식의 흐름대로 짰더니 풀린다(...)


당연히 최단경로는 다익스트라 알고리즘을 사용하는데, 다익스트라 알고리즘을 도는 와중에 가능한 최단 경로의 개수를 세어 주면 된다.


\(dist[v]\)를 \(S\)에서 \(v\)로 가는 최단 경로의 길이, \(cnt[v]\)를 \(S\)에서 \(v\)로 가는 최단 경로의 개수라고 하자.


다익스트라 알고리즘을 돌면서 정점 \(u\)에서 \(v\)에 가게 되었을 때, 지금 막 계산된 \(cost = dist[u] + w[u\rightarrow v]\)와 \(dist[v]\)를 비교한다.


\(cost < dist[v] : dist[v]=cost, cnt[v]=cnt[u]\), \(v\)를 heap에 넣어 준다.

\(cost = dist[v] : cnt[v] = cnt[v] + cnt[u]\)

\(cost > dist[v]\) : *아무 일도 일어나지 않았다.


답은 \(cnt[E]\).


Time Complexity : \(O(E lg V)\)

'알고리즘 문풀 > BOJ 연습' 카테고리의 다른 글

[MWT@SSHS] 모의고사 #2 풀이  (0) 2018.07.17
[MWT@SSHS] 모의고사 #1 풀이  (0) 2018.07.15
8/2 연습  (1) 2017.08.03
8/1 연습  (0) 2017.08.02
7/30 ~ 7/31 연습  (0) 2017.08.01