cubelover의 블로그

Tree Optimization

...2018. 8. 12. 18:38

트리에서 사용할 수 있는 특수한 몇몇 알고리즘들은 실제 시간복잡도가 생각한 것보다 작을 수 있다. 이 글에서는 그런 몇몇 케이스를 다룬다.


~


노드 개수가 \(A\)인 서브트리의 결과와 노드 개수가 \(B\)인 서브트리의 결과를 \(O(AB)\)의 시간에 합칠 수 있는 경우


최악의 경우 \(A\)와 \(B\)가 모두 \(O(N)\), 합치는 횟수가 \(O(N)\)이므로 \(O(N^3)\)인 것 같지만, 사실 \(O(N^2)\)이다.


~


증명


노드 개수가 \(N\)인 서브트리의 결과를 만드는 데 필요한 시간을 \(T(N)\)이라고 정의하자.


또한, 노드 개수가 \(A\)인 서브트리의 결과와 노드 개수가 \(B\)인 서브트리의 결과를 합치는 데 \(cAB\) (\(c\)는 상수) 이하의 시간이 필요하다고 하자.


\(N<A+B\)인 모든 \(N\)에 대해 \(T(N) \le cN^2\)이라고 가정하면,


\[T(A+B) \le T(A) + T(B) + cAB \le cA^2 + 2cAB + cB^2 = c(A+B)^2\]


따라서 수학적 귀납법에 의해 시간복잡도가 \(O(N^2)\)이 된다.


~


응용


이 아이디어로 ACM-ICPC Daejeon Regional 2012 J번(Slicing Tree), Coder's high 2016 Round 2: Nexon Arena C번(트리의 변화), shake! 2017 F번(단신쓴짠)을 풀 수 있다.


~


루트가 있는 트리에서, 각 노드마다 (자식들 중 높이가 두 번째로 높은 노드의 높이 + 높이가 세 번째로 높은 노드의 높이 + ... + 높이가 가장 낮은 노드의 높이)의 합으로 문제를 풀 수 있는 경우


이 경우 시간복잡도가 \(O(N)\)이다.


~


증명


노드 \(u\)의 높이를 \(h_u\)라고 하자. 높이의 정의에 따라, 노드 \(u\)의 자식들 \(v\)에 대해 \(h_u = \max_v \{h_v\} + 1\)이다.


또한, 루트를 제외하고 모든 노드의 부모는 단 한 개이므로, 트리의 루트를 \(r\)이라고 하면 모든 노드에 대해 모든 자식들의 높이 합은 다음과 같다.


\[\sum_{u \neq r} h_u = \sum_u h_u - h_r\]


모든 노드에 대해 두 번째, 세 번째, ...로 높이가 높은 노드의 높이 합은 전체 높이 합에서 첫 번째로 높이가 높은 노드의 높이 합을 뺀 것과 동일하다.


\[\sum_{u \neq r} h_u - \sum_u \max_v \{h_v\} = \sum_u h_u - \sum_u \max_v \{h_v\} - h_r = \sum_u ( h_u - \max_v \{h_v\} ) - h_r = N - h_r = O(N)\]


~


응용


이 아이디어로 가중치 없는 트리에서 세 정점의 순서쌍 (u, v, w)에 대하여, (u-v의 거리) = (v-w의 거리) = (w-u의 거리)를 만족하는 순서쌍이 몇 개나 있는지를 \(O(N)\)으로 구할 수 있다.


이 문제를 \(O(N^2)\)으로 풀면 만점이 나오는 버전이 POI에 출제되었다.


Archive: https://main.edu.pl/en/archive/oi/21/hot

Baekjoon Online Judge: https://www.acmicpc.net/problem/10122


Baekjoon Online Judge에서 \(O(N)\) 풀이로 0ms를 받았으니, 관심이 있는 분은 \(O(N^2)\) 풀이로 맞은 뒤 코드를 읽어보시기 바랍니다.

'...' 카테고리의 다른 글

Tree Optimization  (2) 2018.08.12
ONTAK 2010 Day 7 Generator  (0) 2018.07.17
BOJ Achievements  (0) 2018.05.17
Ubuntu PPTP VPN Server  (0) 2017.12.17
Baekjoon Online Judge 13538  (3) 2016.11.03
Baekjoon Online Judge 1659  (0) 2016.02.02

Comment +2

ONTAK 2010 Day 7 Generator

...2018. 7. 17. 04:30

입력으로 정수 i(0 ≤ i ≤ 10)가 들어오면, genzaw.zip의 gen$i.out에 있는 내용을 출력하는 문제이다. 단, 소스코드는 10만자를 넘을 수 없다.


그래서 genzaw.zip을 까 보면, 가장 작은 gen0.out을 제외하고 200KB 정도 되는 파일부터 3MB 정도 되는 파일까지 다양하다. 물론 이걸 그대로 출력할 수는 없고, 파일 형태를 보고 생성한 알고리즘을 유추해서 문제를 풀어야 한다.


각 파일마다 푸는 방법이 많이 다르므로, 파일마다 힌트와 풀이를 정리해서 올린다.


~


gen0.out


예제 출력에 해당한다.




~


gen1.out


알파벳이 적힌 파일이다.




~


gen2.out


수열이 적힌 파일이다.




~


gen3.out


#과 .이 적힌 파일이다.




~


gen4.out


0과 1이 적힌 파일이다.




~


gen5.out


폴란드어가 적힌 파일이다.




~


gen6.out


T[$number]="$string";이 적힌 파일이다.




~


gen7.out


#과 .이 적힌 파일이다.




~


gen8.out


#과 .이 적힌 파일이다.




~


gen9.out


#과 .이 적힌 파일이다.




~


gen10.out


수열과 행렬이 적힌 파일이다.




'...' 카테고리의 다른 글

Tree Optimization  (2) 2018.08.12
ONTAK 2010 Day 7 Generator  (0) 2018.07.17
BOJ Achievements  (0) 2018.05.17
Ubuntu PPTP VPN Server  (0) 2017.12.17
Baekjoon Online Judge 13538  (3) 2016.11.03
Baekjoon Online Judge 1659  (0) 2016.02.02

Comment +0

BOJ Achievements

...2018. 5. 17. 23:18

NORMAL


100문제 이상 풀기

1000회 이상 제출하기

하루에 10문제 이상 풀기

7일 연속으로 매일 문제 풀기

북마크 기능 사용하기

한 게시글에 좋아요 1개 이상 받기

학교/회사 등록하기

슬랙에서 이야기하기

풀이 작성하기

그룹 만들기

문제 만들기

데이터 추가하기

대회 참가하기

나만 푼 문제 만들기

맞은 사람 목록 맨 위에 올라가기

숏코딩 목록 맨 위에 올라가기

Daily 로또(10948번)에서 맞았습니다 받기

Text로 10문제 이상 풀기


~


HARD


1000문제 이상 풀기

10000회 이상 제출하기

하루에 30문제 이상 풀기
30일 연속으로 매일 문제 풀기

한 게시글에 좋아요 10개 이상 받기

아이디 변경하기

블로그에 글 쓰기

대회 개최하기

스페셜 저지 추가하기

틀렸던 코드 재채점으로 맞았습니다 받기

데이터를 추가해서 맞은 사람 100명 이상 감소시키기

시간제한과 동일한 수행시간으로 맞았습니다 받기

수행시간, 메모리 사용량, 코드 길이 모두 동일한 결과 받기

모든 언어로 맞았습니다 받기

모든 문제에 제출하기

언어 랭킹 1위 달성하기

랜덤 게임~~(10944번)에서 맞았습니다 받기

Text로 50문제 이상 풀기


~


INSANE


10000문제 풀기

하루에 100문제 이상 풀기

365일 연속으로 매일 문제 풀기

한 게시글에 좋아요 100개 이상 받기

모든 언어로 모든 결과 받기

로또(10947번)에서 100점 받기

랜덤 게임~~~~(10946번)에서 100점 받기

Text로 100문제 이상 풀기

'...' 카테고리의 다른 글

Tree Optimization  (2) 2018.08.12
ONTAK 2010 Day 7 Generator  (0) 2018.07.17
BOJ Achievements  (0) 2018.05.17
Ubuntu PPTP VPN Server  (0) 2017.12.17
Baekjoon Online Judge 13538  (3) 2016.11.03
Baekjoon Online Judge 1659  (0) 2016.02.02

Comment +0