문제의 특성상 그림이 설명에 중요한 역할을 하나,
포스트에 그리기가 번거로우므로 생략하고, 노트에 있는 그림을 참고한다.


문제 정의 : 평면 상의 n개의 점들 중 가장 가까운 한 쌍을 찾아라.
- 이 문제의 입력은 그래프가 아니라 x좌표, y좌표가 주어진 점들의 집합이다.

Alg.
1. 입력을 x축 기준으로 정렬해서 반으로 나눈다.
2. 재귀적으로 호출한다.
3. (merge sort를 사용하여) y축 기준으로 정렬하며 합친다.


* 반으로 나뉠때 가운데에 잘린 것들은 어떻게 비교할 것인가? ( 하나는 왼쪽에, 다른 하나는 오른쪽에 있는 경우 )

- 왼쪽에서 찾은 제일 짧은 선과 오른쪽에서 찾은 제일 짧은 선, 둘 중에 더 짧은 선을 d라 하자.
- x축의 중심에서 왼쪽으로 d, 오른쪽으로 d만큼의 영역을 "밴드"라 하자.

- 밴드 안의 특정한 점에 대해서 y축 방향으로 d만큼 차이나는 점과의 거리만 보면 된다.
- 그리고 그 점들은 무조건 10개 이하이다.
  -> 거리가 d인 정사각형 안에 d보다 긴 거리를 가지는 점들은 최대 3개까지 밖에 넣지 못한다.

- 밴드 안에 있는 점들을 y축 기준으로 정렬해야 한다.
- 한 레벨에서 nlogn 만큼의 시간을 쓰기 때문에, 전체 알고리즘의 수행시간은 n(logn)^2 이 된다.

* 밴드 안에 있는 점들만 보면 되지만, 모든 점들을 sort하는 것이 더 좋다.

왜냐하면 밴드 안에 있는 점들만 sort하려면 각 레벨마다 "그 레벨의 밴드 안에 있는 점들"을 y축을 기준으로 새로 정렬해야 하지만,
애초에 모든 점들을 sort하겠다고 한다면, 합치면서 merge sort를 사용할 수 있기 때문이다.
또한, 모든 점을 sort 해도, 실제 스캔은 밴드 안에 있는 점만을 찾아서 계산하기 때문에
작업이 크게 늘어나지 않는다. ( 밴드 밖에 있는 점을 건너뛰는 시간이 더해질 뿐이다.)
- 합치면서 merge sort를 하게 된다면, 한 레벨에서 n만큼의 시간을 쓰게 되고,
 전체 알고리즘의 수행시간이 nlogn이 된다.
- 기존의 작업은 아래 레벨에서의 결과물이 현재 레벨에서 아무 도움이 되지 않는다.
 ( 밴드의 위치는 레벨마다 다르기 때문에 현재 레벨에서 다시 정렬을 수행해야 한다.)
 merge sort를 사용하면 아래 레벨에서의 결과물이 현재 레벨에서 도움이 된다.
 ( 양쪽 배열이 이미 정렬되어 있으므로, merge기법을 통해 간단히 합칠 수 있게 되는것.)


'학부 전공 > 알고리즘' 카테고리의 다른 글

Selection  (0) 2010.10.29
Tape에 데이터 담기  (0) 2010.10.11
Job Scheduling  (0) 2010.10.08
Dijkstra 알고리즘  (0) 2010.10.08
Kruskal 알고리즘  (0) 2010.10.08

문제 정의 : k등을 찾아라!

- Sorting 보다 빨라야 도움이 된다. ( 퀵소트에서 중간값을 찾는 경우 등)

- 토너먼트 식으로 한다면? 
1등을 찾는데에는 n, 2등을 찾는데에는 n + logn, 3등을 찾는데에는 n + 2logn,
k등을 찾는데에는 n + klogn이 걸리게 된다.

- Selection Sort를 k번째 까지 수행한다면?
kn 시간이 걸림 -> k가 n/2이면 O(n^2)이 걸리게 된다.

- Quick Sort를 k등 근처에서 수행한다면?
최선의 경우 O(n)에 끝나지만,
최악의 경우 O(n^2)이 걸리고 평균적으로 O(n)이 된다.

-> Selection 문제를 "최악의 경우에도" n^2이 안 걸리게 풀 수 있는 알고리즘이 있을까?
-> 있지만, 슬프게도, 실용적이지는 않다.


* Approximate Median

정의 : rn등부터 (1-r)n등 사이의 원소. (단, 0 < r < 1)

- 매우 약한 정의이기는 하지만 이렇게 주어져도 문제 없다는 것이 증명되어 있음. ( = 그냥 믿으세요! )
- r = 0.3으로 고정한다.

Alg.
  1. 배열을 5개씩 분할
  2. 각 분할의 중간값을 찾는다.
  3. 중간값들 중 실제 중간값을 찾는다.

결론 : 3번에서 찾은 '실제 중간값'은 반드시 rn등과 (1-r)n등 사이에 존재한다.


* 정확성 증명

입력이 ㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇㅇ 이라고 한다면

1번에서
ㅇㅇㅇㅇㅇ | ㅇㅇㅇㅇㅇ | ㅇㅇㅇㅇㅇ | ㅇㅇㅇㅇㅇ | ㅇㅇㅇㅇㅇ 
- 단, 실제로 나누는 것이 아니고 그렇게 생각하는 것.


2번을 이해하기 쉽게 배열을 세로로 나타내면

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 
ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 
ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 
ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 
ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

- 위에 있을수록 큰 값, 아래에 있을수록 작은 값.

- 3번째 줄, 즉 가운데 값이 각 분할된 배열의 중간값이다.


가운데 값을 기준으로 각 분할된 배열을 정렬한다.
(여기서는 증명 과정을 알아보기 쉽도록 정렬을 하지만, 실제 구현에서는 모든 분할 배열을 정렬할 필요없이,
 3번째 줄의 진짜 중간값만 찾으면 된다.)
ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 
ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 
ㅇ | ㅇ | ㅇ | ㅇ | ㅇ |  <- 정렬되어 있음.
ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 
ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

1,2, 4,5번째 줄은 좌우로는 크기비교를 할수 없지만, 위의 것보다는 작고, 아래의 것보다는 크다.


3번에 의해 찾은 실제 중간값을 ☆ 이라 하자.

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 
ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 
ㅇ | ㅇ | ☆ | ㅇ | ㅇ | 
ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 
ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

- 위에서 빨간색으로 표시된 것들은 무조건 ☆보다 큰 값이다.
- ☆의 위에 있는 값들은 분할된 배열이 정렬되어 있기때문이고, ☆의 오른쪽에 있는 값들은 3번째줄을 기준으로 정렬했기 때문이고,
☆의 오른쪽 위에 있는 값들은 
 ☆ < (☆의 오른쪽) < (☆의 오른쪽)의 위
이기 때문이다.

- 따라서, 예제의 입력된 배열에는 ☆보다 큰 값이 최소한 8개 존재하며,
 입력된 배열이 n개 일때, ☆보다 큰 값이 최소한 (대략) 3n/10개 존재한다.
 -> 즉, ☆이 아무리 커도 상위 30%이내에는 들어갈 수 없다.


위와 같은 식으로,

ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 
ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 
ㅇ | ㅇ | ☆ | ㅇ | ㅇ | 
ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 
ㅇ | ㅇ | ㅇ | ㅇ | ㅇ | 

- 위에서 빨간색으로 표시된 것들은 무조건 ☆보다 작은 값이다.
- ☆의 아래에 있는 값들은 분할된 배열이 정렬되어 있기때문이고, ☆의 왼쪽에 있는 값들은 3번째줄을 기준으로 정렬했기 때문이고,
☆의 왼쪽 아래에 있는 값들은 
 ☆ > (☆의 왼쪽) > (☆의 왼쪽)의 아래
이기 때문이다.

- 따라서, 예제의 입력된 배열에는 ☆보다 작은 값이 최소한 8개 존재하며,
 입력된 배열이 n개 일때, ☆보다 작은 값이 최소한 (대략) 3n/10개 존재한다.
 -> 즉, ☆이 아무리 작아도 하위 30%이내에는 들어갈 수 없다.


=> 따라서 ☆이 전체 입력의 30% ~ 70% 사이에 존재한다.
=> Approximate Median이 성립함.


 * 3번에서 "실제 중간값"을 찾기 위해서 Quick sort를 호출한다.
그리고 그 Quick sort는 pivot을 찾기 위해 Approximate Median을 호출한다.
=>Quick sort ( 이하 QS )와 Approximate Median ( 이하 AM )이 상호재귀함수로서 작동한다.

- QS(n)은 AM(n)과 QS(0.7n)을 호출한다.
   -> 입력된 것을 그대로 AM으로 보내 pivot을 찾고, 그 pivot은 최악의 경우에도 70%안쪽이므로 0.7n으로 다시 QS를 호출할 수 있다.

- AM(n)은 QS(0.2n)을 호출한다.
   -> 입력을 5개씩 분할하고 각 분할된 배열의 중간값만을 QS로 보내 실제 중간값을 찾는다. 


* Selection 문제를 푸는 시간을 t(n)이라 하면

t(n) = n + t(2n/10) + t(7n/10)

t(n) <= Cn이라고 가정하면

t(n) = n + 2Cn/10 + 7Cn/10 
      = 9Cn/10 + n
      = (9C+10)*n/10 

C가 커질수록 (9C+10)/10 의 값이 작아진다.
( C가 10일때 10, 20일때 19, 30일때 28 .........)

즉 t(n) <= 10n

따라서 t(n) = O(n)



'학부 전공 > 알고리즘' 카테고리의 다른 글

Closest Pair  (0) 2010.10.29
Tape에 데이터 담기  (0) 2010.10.11
Job Scheduling  (0) 2010.10.08
Dijkstra 알고리즘  (0) 2010.10.08
Kruskal 알고리즘  (0) 2010.10.08


- 입력 D에는 단위 데이터들이 저장되어 있고, 데이터마다 길이(L)와 사용빈도(F)가 저장되어 있다.
- 매번 read한 후에 full rewind 한다고 가정한다.

- 문제의 목표는 read시간의 기대값을 최소화 하는 것.

 * 알고리즘
- 길이가 짧을수록, 빈도가 높을수록 앞부분에 둔다.
- F(i)/L(i) 값이 큰 것부터 앞에 둔다.
 -> F(i) - L(i) , F(i)^2 / L(i) , 등등의 값 또한 사용할 수 있는데 왜 F(i)/L(i) 값을 쓰는것이 가장 좋은가?

 * 증명
- d1,d2,d3,d4,d5,..... dn 순서가 정답이고, F(i)/L(i)가 감소하는 순서가 아니라고 가정하자
 -> 즉, 정답 중에 F(k)/L(k) < F(k+1)/L(k+1)인 k가 적어도 1개 존재한다.

- S' = d1,d2,d3,,,,,,,d(k+1), d(k),,,,,,,,dn 이라고 하자. ( d(k)와 d(k+1)의 순서를 바꾼 것 )
- S의 기대값 t = F(1)*L(1) + F(2)*( L(1)+L(2) ) + F(3)*( L(1)+L(2)+L(3) + ............
.....+ F(k)*( L(1)+L(2)+...+L(k) ) + F(k+1)*( L(1)+L(2)+...+L(k+1) ) + ... + F(n)*( L(1)+L(2)+...+L(n) )

- S'의 기대값 t' =  F(1)*L(1) + F(2)*( L(1)+L(2) ) + F(3)*( L(1)+L(2)+L(3) + ............
.....+ F(k+1)*( L(1)+L(2)+...+L(k-1)+L(k+1) ) + F(k)*( L(1)+L(2)+...+L(k+1) ) + ... + F(n)*( L(1)+L(2)+...+L(n) )
- t - t' = F(k+1)*L(k) - F(k)*L(k+1)
          = L(k)*L(k+1)*( F(k+1)/L(k+1) - F(k)/L(k) ) > 0

- t > t' 이다. 정답의 기대값인 t보다 작은 t' 존재하는 것은 모순이다.
따라서 가정은 거짓이다.


 * F(i)/L(i)값을 쓰는 이유는 기대값을 계산하고 비교하는데에서 F(i)/L(i)값이 등장하기 때문이다.

'학부 전공 > 알고리즘' 카테고리의 다른 글

Closest Pair  (0) 2010.10.29
Selection  (0) 2010.10.29
Job Scheduling  (0) 2010.10.08
Dijkstra 알고리즘  (0) 2010.10.08
Kruskal 알고리즘  (0) 2010.10.08


- unit time에 실행가능한 job들이 존재.
- 시간 d(i) 이전에 job i를 수행하면 이익 P(i)
- job은 이익으로 내림차순 정렬되어 있다.

- S(k) = i 는 job i가 k시간에 끝나도록 schedule했다는 의미.
- deadline이 n보다 큰 job은 없다고 가정

 * 구조
- 첫번째 job부터 시작하여 d(i)보다 작고 S(k)=0 인 가장 큰 k에 대해 S(k) = i

 " 알고리즘이 최적의 solution을 얻는다. "
- feasible : deadline을 위반한 job이 없는 schedule
- promising : feasible하면서 최적 solution으로 "확장"될 수 있는 schedule
- 확장 : job i+1, job i+2, ........ job n 들 중에서만 job을 추가함

 " 알고리즘의 모든 단계에서 S는 promising 하다 "
base) 최초에 S는 promising하다. 모든 k에 대해서 S(k) = 0이기 때문이다.
step) 알고리즘이 i-1번째 job을 추가했을때 promising 하다면, i번째 job을 추가했을때 promising 한가?
- 최적 solution 중 하나를 Sopt라 하자.
- 알고리즘은 job i를 가지고 두가지 동작을 할 수 있다. job i를 버리거나, job i를 k에 추가하는 것이다.
1) 알고리즘이 job i를 버렸다는 것은, deadline 앞에 빈 칸이 없을 때이다. 이런 경우의 Sopt에는 i가 없다.
따라서 여전히 promising하다.
2) 알고리즘이 job i를 k번째에 추가했다고 하자. 이 때에도 두 가지 경우가 생긴다.
- i를 추가한 S를 S'라 하자. 즉, S'(k) = i
 2-1) job i가 Sopt에서 k'에 schedule되어 있음. 즉, Sopt(k') = i
k' = k 일 경우, S'는 promising하다.
k' < k 일 경우, Sopt(k)와 Sopt(k')를 교환한다. 조건에 위배되는것이 없으므로, 여전히 promising하다.
k' > k 일 경우는 불가능하다. 알고리즘에서 deadline과 k 사이에는 빈칸이 없기 때문이다.
 2-2) job i가 Sopt에 없을 경우
- 최소한 Sopt(k)는 0이 아니라는 것을 알 수 있다. Sopt(k)를 x라 하자.
- x는 i 보다 더 나중에 나오는 job이다. 따라서 이익이 더 작거나 같다. 따라서 S'opt(k)를 i로 교체한다.
- 그래서 S'는 promising 하다.


'학부 전공 > 알고리즘' 카테고리의 다른 글

Selection  (0) 2010.10.29
Tape에 데이터 담기  (0) 2010.10.11
Dijkstra 알고리즘  (0) 2010.10.08
Kruskal 알고리즘  (0) 2010.10.08
Prim 알고리즘  (0) 2010.10.07

- Shortest Path 문제를 풀기 위한 알고리즘

 * 구조
1. 모든 node의 dmin값을 V0부터 자신까지의 weight로 한다.
2. V0를 T에 넣고, T에 없는 node중 dmin값이 가장 작은 node를 u라 하고, u를 T에 추가.
3. T에 없는 모든 node의 dmin 값을 기존 값과 dmin(u) + g(u,w) 중에서 더 작은 값으로 보정.
4. T의 개수가 n이 될 때까지 2,3을 반복.

 * 증명
-  알고리즘이 SP문제를 정확히 풀어내는지 증명.

1. u가 T에 포함되어 있으면 dmin(u)는 global SP. ( = d(u) )
2. u가 T에 포함되어 있지 않으면 dmin(u)는 dt(u) ( T에 있는 node만 사용했을 때의 S.P)

1,2를 증명하기 위해, 수학적 귀납법 사용
base) 최초에 V0만 T에 포함되어 있을때, 1,2는 모두 성립한다.
step) T의 개수가 k 일 때 증명이 성립한다고 가정하자. 그리고 알고리즘이 T에 u를 추가하여 T'이 되었다고 하자.
- 추가되기 전의 dmin(u) = dt(u) 이다. ( 알고리즘이 dt가 아닌 dmin값을 설정하는 일이 없다.)
- dmin(u) = d(u) 이다. 즉, V0에서 u까지의 SP는 현재 T에 있는 node들 만으로 이루어져 있다.
-> 그렇지 않다면, V0와 u사이에 v라는 node가 존재한다. v는 T에 포함되지 않는 node이다.
d(u)는 dt(u)보다 작다. 그리고 dt(v)는 d(u)보다 작다. 
-> dt(u)보다 작은 dt(v)가 존재한다. 이것은 모순이다. (알고리즘은 u를 추가했으므로)
 따라서 알고리즘이 추가하는 u의 dmin(u)는 d(u)이다.
-> 1 성립.

- T'에 속하지 않는 node w를 고려해보자. 
- 알고리즘이 u를 추가하기 직전의 dmin(w) = dt(w)이다. (수학적귀납법 step과정에서 가정한 사실)
  u를 추가하고 나서는 dmin(w) = dt'(w)가 되어야 한다.
- dt'(w)는 dt(w)와 d(u) + g(u,w) 두 값중 하나로 보정된다. 
 1) dt'(w)가 dt(w)로 보정된다면, step에서 가정한 사실에 의해서 그대로 2가 성립한다. 
 2) dt'(w)가 d(u) + g(u,v)로 보정된다면, dmin(w) = dt(w)가 성립되기 위하여
V0에서 w까지의 SP에는 u가 포함되어 있어야 하며 특히 u는 w 바로 앞에 있어야 한다. 
즉, u와 w 사이에는 node가 없어야 한다. 
- 만약 u와 w사이에 x라는 node가 있다고 가정한다면, 
x는 T에 포함된 node이고 ( x가 T에 포함되지 않는 node는 고려할 필요가 없다. 여기서는 dt(w)를 증명하면 되기 때문)
x의 SP는 u를 포함하지 않는다.(u는 이번 단계에서 추가된 node이기 때문)
- 2)에서 dt'(w)가 d(u) + g(u,v)로 보정되었으므로, w의 SP에는 u가 포함되어야 한다. 여기서 모순이 생겼다.
- 따라서 u와 w사이에는 다른 node가 없다.
- 그래서 2)의 경우에도 2가 성립한다.

모든 경우에 2가 성립하므로 step은 참이다.

따라서 알고리즘은 정확히 동작함을 증명하였다.


'학부 전공 > 알고리즘' 카테고리의 다른 글

Selection  (0) 2010.10.29
Tape에 데이터 담기  (0) 2010.10.11
Job Scheduling  (0) 2010.10.08
Kruskal 알고리즘  (0) 2010.10.08
Prim 알고리즘  (0) 2010.10.07

Minimum Spanning Tree 문제를 풀기 위한 알고리즘.


 * 구조
1. 그래프의 각 node를 각각 하나의 node를 가진 tree로 만든다.
2. 모든 edge중 cycle을 만들지 않는 가장 작은 edge를 T에 추가한다.
3. 모든 edge를 볼 때까지 2를 반복한다.

(여기서 T는 edge의 집합이다.)

 * 증명
- 알고리즘이 MST문제를 정확히 풀어내는지 증명.
- 알고리즘이 만들어낸 tree가 Spanning tree인지 증명한 후, 그 tree가 minimum tree임을 증명.

1. Spanning tree를 만든다.
- T에 포함된 edge의 개수는 n-1보다 같거나 작다. ( node의 개수와 같거나 더 많으면 반드시 cycle이 생긴다. )
- weight가 적은 edge부터 cycle을 만들지 않는 모든 edge를 추가하므로, 연결되지 않은 node가 있을 수 없다.

2. Minimum tree가 된다.
- 정답이 하나라고 가정. (즉, 같은 비용인데 다른 edge를 가지고있는 정답이 없음.)
- 정답 tree를 만드는 edge의 집합을 Tmst라고 하면, 알고리즘의 모든 단계에서 T ⊂ Tmst 가 된다.
- 따라서 알고리즘이 종료되면 T = Tmst가 된다. ( 어떤 tree에 속한 tree인데 edge의 수가 같다면 두 tree는 동일한 tree이다.)

* 2번의 "알고리즘의 모든 단계에서 T ⊂ Tmst 가 된다."를 증명하기 위해, 수학적 귀납법 사용
base) 최초에 T는 공집합이다. 
step) 알고리즘이 T ⊂ Tmst 인 T에 edge인 e를 추가해서 T'가 됬다고 하자. ( T' = T ∪ {e} )
이 때 T' ⊂ Tmst가 된다.

* step의 " T' ⊂ Tmst "를 증명하기 위해, 귀류법 사용.
- T'가 Tmst에 포함되지 않는다면, e 또한 Tmst에 포함되지 않는다.
( T와 T'의 차이는 e 뿐이므로 )
- Tmst ∪ {e} 는 cycle을 가진다. 
(왜냐하면 Tmst에 e를 추가하면 총 n개가 되기 때문이다. n개의 node에 n개의 edge를 가진 그래프는 cycle이 존재한다.)
- 그 cycle은 e를 포함하고 있지만, 그 cycle의 모든 edge가 T에 포함된 것은 아니다. (e는 알고리즘이 선택한 edge이기 때문에.)
- 만들어진 cycle중에서 T에 포함되지 않는 edge를 f라 하자. 
그리고 Tmst에서 f를 제거하고 e를 추가한 집합을 T''이라 하자.
- f는 e보다 weight가 더 크다.. 왜냐하면 알고리즘이 T에 e를 추가했기 때문이다.(알고리즘은 최소 weight를 가진 edge를 추가한다.)   
- 따라서 T''은 Tmst보다 더 작은 weight를 보유한 정답이다. 하지만 Tmst는 유일한 정답이다. 따라서 모순이 생겼다.

모순이 생겼으므로 가정은 거짓이다.
그래서 step의 T' ⊂ Tmst 는 참이다.

따라서 알고리즘은 정확히 동작함을 증명하였다.



'학부 전공 > 알고리즘' 카테고리의 다른 글

Selection  (0) 2010.10.29
Tape에 데이터 담기  (0) 2010.10.11
Job Scheduling  (0) 2010.10.08
Dijkstra 알고리즘  (0) 2010.10.08
Prim 알고리즘  (0) 2010.10.07

Minimum Spanning Tree 문제를 풀기 위한 알고리즘.


 * 구조
1. 최초에 하나의 node를 tree인 T에 추가.
2. 현재 tree에 인접한 edge중 가장 작은 가중치를 가진 edge를 T에 추가,(단, 그 edge는 사이클을 만들지 않음)
3. 모든 node를 추가할 때까지 2를 반복.

 * 증명
- 알고리즘이 MST문제를 정확히 풀어내는지 증명.
- 알고리즘이 만들어낸 tree가 Spanning tree인지 증명한 후, 그 tree가 minimum tree임을 증명.

1. Spanning tree를 만든다.
- 알고리즘은 매번 edge를 추가할 수 있다. (입력이 connected graph임을 가정했음)
- 알고리즘이 매번 edge를 추가할 때 마다, T는 tree임을 유지, 즉, tree의 정의 ( undirected, acyclic, connected graph )를 계속 만족함.

2. Minimum tree가 된다.
- 정답이 하나라고 가정. (즉, 같은 비용인데 다른 edge를 가지고있는 정답이 없음.)
- 정답 tree를 Tmst라고 하면, 알고리즘의 모든 단계에서 T ⊂ Tmst 가 된다.
- 따라서 알고리즘이 종료되면 T = Tmst가 된다. ( 어떤 tree에 속한 tree인데 edge의 수가 같다면 두 tree는 동일한 tree이다.)

* 2번의 "알고리즘의 모든 단계에서 T ⊂ Tmst 가 된다."를 증명하기 위해, 수학적 귀납법 사용
base) 최초에 T ⊂ Tmst 이다. (노드가 하나밖에 없으므로 포함관계 성립)
step) 알고리즘이 T에 edge인 uv를 추가해서 T'가 됬다고 하자. ( T' = T ∪ {uv} )
이 때 T' ⊂ Tmst가 된다.

* step의 " T' ⊂ Tmst "를 증명하기 위해, 귀류법 사용.
- T'가 Tmst에 포함되지 않는다면, uv 또한 Tmst에 포함되지 않는다.
( T와 T'의 차이는 uv 뿐이므로 )
- Tmst ∪ {uv} 는 cycle을 가진다. 
(왜냐하면 Tmst는 Spanning tree인데, 거기에 edge를 추가한 상황이기 때문에 반드시 cycle을 가지게 된다.)
- 그 cycle은 uv를 포함하고 있지만, 그 cycle의 모든 edge가 T에 포함된 것은 아니다. (uv는 알고리즘이 선택한 edge이기 때문에.)
- 만들어진 cycle중에서 T에 포함되지 않는 edge를 ab라 하자. 
그리고 Tmst에서 ab를 제거하고 uv를 추가한 tree를 T''이라 하자.
- ab는 uv보다 weight가 더 크다.. 왜냐하면 알고리즘이 T에 uv를 추가했기 때문이다.(알고리즘은 최소 weight를 가진 edge를 추가한다.)   
- 따라서 T''은 Tmst보다 더 작은 weight를 보유한 정답이다. 하지만 Tmst는 유일한 정답이다. 따라서 모순이 생겼다.

모순이 생겼으므로 가정은 거짓이다.
그래서 step의 T' ⊂ Tmst 는 참이다.

따라서 알고리즘은 정확히 동작함을 증명하였다.


'학부 전공 > 알고리즘' 카테고리의 다른 글

Selection  (0) 2010.10.29
Tape에 데이터 담기  (0) 2010.10.11
Job Scheduling  (0) 2010.10.08
Dijkstra 알고리즘  (0) 2010.10.08
Kruskal 알고리즘  (0) 2010.10.08

+ Recent posts

티스토리툴바