[문제해결기법] 4. 자료구조2

1. 트리 지름

트리의 두 정점 u, v의 거리의 최댓값

 

(1) O(n^3) : brute force

(2) O(n^2) : u를 고정하고 bfs한다.

(3) O(n)

트리에서 임의의 정점 x를 선택하고 x에서 가장 먼 정점 y를 찾는다.(bfs)

이후 y에서 가장 먼 정점 z를 찾는다. 그러면 y와 z가 가장 멀리 떨어져있는 정점 쌍이다.

 

증명

원하는 답이 두 정점 u와 v이다.

그렇다면 3가지 가능성이 있는데, x에서 가장 먼 점이 y라고 하면

(1) x = u / x = v

(2) y = u / y = v

(3) x,y,u,v 모두 다른 경우

 

(1)과 (2)는 위 알고리즘의 답이 맞다는 것이 자명하다. (3)의 경우는 u~y 경로와 u~v 경로가 거리가 같은 경우 이외에는 없어야 한다.

 

x,y,u,v가 모두 다르다고 하자. 그러면 x~y의 경로와 u~v의 경로가 교점 t가 있을 수도 있고, 없을 수도 있다.

만약 교점 t가 존재한다면, t~y가 t~u, t~v보다 멀어야 한다. (x~y가 가장 멀어야 하므로)

그렇다면, u~t~y가 u~t~v보다 멀다. 이는 u~v가 답이라는 가정에 모순이다.

 

교점이 존재하지 않는다면, 정의상 a~y가 a~b~u, a~b~v보다 멀다. (x~y가 가장 멀어야 하므로)

u~v와 u~y를 비교하면, u~b는 공통이므로 b~a~y와 b~v를 비교할 때 a~y가 a~b~v보다 멀어야 하므로 b~a~y가 b~v보다 멀고,

u~v거리가 u~y보다 짧아야 한다. 이는 u~v가 답이라는 가정에 모순이다.

 

 

2. 연습문제 : 전도

 

최교수는 전류가 통하는 새로운 소재를 개발하고 있다. 이 소재의 단면은 M x N 격자 형태인데, 격자의 윗면은 외부이고 격자의 아랫면은 내부라고 하자. 검은색 칸은 전류를 절연하고, 흰색 칸은 전류가 통한다. 외부에서 내부로 서로 인접한 흰 칸을 통해서 전류가 흐를 수 있다. 대각선으로 인접한 흰 칸끼리는 전류가 통하지 않는다. 전류가 외부에서 내부로 흐를 수 있는지 없는지를 구하는 프로그램을 작성하시오. 예를 들어, 왼쪽 그림은 전류가 통하는 경우이고 오른쪽 그림은 전류가 통하지 않는다.

-> bfs / dfs 로 풀이 가능

 

 

3. 과반수 찾기

정수 배열 A[n]에서 n/2번 이상 나오는 원소 x를 찾기.

 

(1) O(n^2) : brute force로 각 원소마다 자기 뒤에 나오는 횟수를 세어본다.

(2) O(n log n)

- 배열을 정렬 후 차례대로 원소를 읽으면서 바로 직전 원소와 같은지 비교한다.

- 정렬에 O(n log n), 원소를 읽는 데에 + O(n)

(3) O(n)

그룹의 맨 처음 원소의 수 = 다른 원소의 수가 되도록 그룹을 나눈다.

만약 과반수로 나오는 값이 있다면 가장 마지막 그룹의 맨 앞 값이다.

첫번쨰 원소는 비교되지 않고, 다른 원소들은 최대 n-1번 다른 원소와 비교된다.

마지막 그룹의 첫 원소가 과반수인지 점검하는데에 n-1번 비교. 총 O(n) 시간.

 

- 주장 : n개의 원소 중 과반수인 원소가 x라고 하면, 위 방법 이후 맨 왼쪽 한 그룹을 제거하더라도 남은 원소 중 과반수인 원소는 x이다.

- 증명

첫번째 원소는 x이거나 x가 아니다.

만약 첫번째 원소가 x라면, x가 나온 횟수만큼 다른 원소들이 첫 그룹에 포함된다.

같은 횟수만큼 x와 다른 원소들이 제거되므로 남은 원소 중 여전히 과반수 이상이 x이다.

첫번째 원소가 x가 아니라면, 첫 원소를 y라고 하자.

x가 가장 많이 제거되는 경우는 yyyyxxxx 같은 경우인데,

이 경우에도 여전히 같은 횟수만큼 x와 다른 원소들이 제거되므로 남은 원소 중 과반수 이상이 x이고 다른 경우에도 마찬가지다.

 

(4) O(n)

과반수의 원소가 m이라고 하고, 각 원소마다 자신이 m이면 count += 1, 아니라면 count -= 1을 해준다.

과반수가 있다면 count 값이 양수이다.