알고리즘 시험 준비 - [3/13 Files] - 2019-09-04

 

Convex - Hull 은 모든 점을 포함하는 점을 이어주는 것이라고 보면 된다. 

 

 

 

1. 먼저 y 축으로  Sorting을 한다. 

2. sorting을 했을 경우 젤 작은 점 기준으로 또 x 축으로 sorting을 한다. 

3. 그리고 먼저 3개의 점을 넣는다. 

4. 그리고 4번쨰점부터 계속 방향이 왼쪽으로 가는지 확인한다. 아닐 경우는 pop을 통해 제일 마지막으로 들어간 거를 빼준다. 

 

4번에 대한 설명이다. pb -> pa -> pk 했을때 right 이면 pa를 뺸다 아니면 pk를 넣는다.

 

 

Graham Scan 은 O(nlogn)이 젤 dominate 하다. 이건 sort 할떄 쓰인다고 보면 될듯

 

 

왜 Left 인지 vector 로 설명을 할수 있다. 

 

외적 곱을 했을때 양수이어야 왼쪽이다 그게 중요하다

 

0이면 그냥 같은 라인이라고 한다. 

 

https://rfriend.tistory.com/tag/%EA%B2%B0%ED%95%A9%EB%B2%95%EC%B9%99

 

 

그리고 Graham-Scan은 O(nlogn) 이고 Graham-scan-core 은 O(n)이다.

 

 

Convex-Hull을 절반으로 나눠서 접근할수도 있다. 

 

 

 

Master’Theoreom 을 통해 O(nlogn)이 나온다.

 

식에서 O(n) 이 나오는 이유는 n개의 point을 합치기 때문이다.

 

P1 에 대해서 젤 왼쪽꺼랑 오른쪽 기준으로 나누는 거였구나. 신기하네