알고리즘 11

기하문제를 현실에서 생각보다 많이 풀고 있다.

분할과 정복을 배우는 와중에 기하를 배우는 이유는 두 개의 방식으로 풀리는 알고리즘이 있기 떄문에

CLosest Pair: 가장 가까운 쌍 찾기

 

사람처럼 직관적으로 푸는 것은 힘들다. x,y좌표로 주어진다.

(3,2) (3,7), (5,5)

 

직관 -> 숫자로 바꿀 수 있는 문제는 바꾸는 것이 좋다

 

기하문제의 특징: 같은 문제를 1차원,2차원,3차원에서 생각할 수 있다.

현실은 3차원이기 떄문에 3차원 문제를 풀 일이 종종 있다. 하지만 난이도는 크게 차이 난다. 

2차원 기하도 의미있는 경우가 많기 떄문에 2차원을 많이 푼다!

 

---

1차원에서 먼저 생각해보자.

가장 가까운 점찾기와 가장 먼 점 찾기는 같은문제일까 다른문제일까? 다른문제이다.

shortest는 빨리 푸는 방법이 있지만 longest문제는 평생 빨리 푸는 법이 없을 것

 

가장 가까운 점 찾기 문제: sorting을 하면 된다.

비교만 하는 상황에서 nlog n이 필요하다. 

 

가장 먼 점은 가장 작은값, 가장 큰 값을 찾으면 된다.

sorting보다 쉬운 문제임

---

 

O(N^2) - easy 이 방법을 말한 것이 당연히 아님

O(Nlog N)

 

 

사람이 이해하기 위해 빨간 줄을 그어 7개 7개로 나눔

일단 왼쪽에서 답을 구하고 오른쪽에서 답을 구한다. (재귀)

문제는 답은 둘중에 하나가 아닐 수 있다는 것

 

 

 

왼쪽과 오른쪽의 선 중에 길이가 더 짧은 것을 D라고 하자

원래 경계선에서 D만큼의 거리에 선을 긋고 확인한다.

 

일직선에서 생각해봐도 마찬가지

x축만보고 정렬하고 반으로 쪼개 짧을 길이 만큼을

중앙선에서 앞뒤 경계를 확인 

 

문제는 성능임

 

이렇게 있는 경우라면?

 

문제: 경계가 이렇게 그려진다.

비교하는 과정만으로 N^2이 나올 수도 있다..

---

첫번째 핵심 아이디어

 

이쪽의 모든 것을 비교하면 N^2이 되어 버리니까 모든 쌍을 다 비교하지 않아야 한다.

 

band안의 점에서 거리 D인 원을 그린다. 

 

왼쪽에서 원을 그렸을 때 왼쪽에는 다른 점이 있으면 안된다.

 

 

---

나와 비교가 필요한 경우 찾는 과정 

밴드 안에서 무작정 거리를 재서 비교를 하면 그것만 O(N^2)이 걸릴 수 있다.

 

두 사각형만 필요하다.

 

한 변의 길이가 D인 정사각형 하나에 점이 최대 3개까지 들어갈 수 있다. 4개는 불가

5개와만 비교하면된다. 사각형 밖은 D가 넘기 때문에

 

저 5개의 점들을 어떻게 찾을 것인가?

현재 x좌표를 기준으로 sorting되어 들어가있다. 

x좌표는 비슷비슷하겠지만 y좌표는 아래위로 왔다갔다 할 것임

 

검은 점이 (x1,y1)이라고 하면

y좌표 기준으로 +D, -D 이내인 애들을 찾으면 최대 5개가 나온다!

 

 

Y좌표로 sorting하면 된다.

밴드안의 점들만 모아서 y좌표로 sorting하자

 

만약 이렇게 있다면

 

y좌표로 정렬하면 이렇게 될 것

 

이 경우엔 이렇게

 

=> 구현의 편의를 위해서 s입장에서만 설명 (실제로는 모든 점이 같은 동작)

 

S는 자기 위쪽으로 5개를 본다.

5개의 .거리를 잰다. 6번째는 분명히 경계선을 넘어감.

4번쨰부터 넘어갈 수도 있지만 일단 5개까지 보고 제일 작은 것을 찾을 거임

 

D보다 작은 것이 나왔으면 이 안에서 찾은 것임!

 

---

<정리>

1. 전체를 x좌표로 sorting해서 갯수로 절반을 나눈다.

2. 왼쪽과 오른쪽에서 각각 최소거리를 찾는다.

3. 둘 중 최소거리만큼 경계선으로부터 그린다. = band

4. band 사이에 존재하면 더 작은 값

5. 하지만 band사이의 값을 모두 비교했을 때 O(n)이 될수도 있음

6. 5개만 봐도 된다고 알았다

7. y좌표로 정렬 후 한 점이 위로 5개까지만 보면 된다.

 

 

 

2S(n/2) : 왼쪽 절반+오른쪽 절반

n: 비교(점 하나당 상수번 비교)

y좌표로 sorting: nlog n

---

두번째 어려운 것

밴드 안의 점들만 꺼내서 y좌표로 sorting했었다.

=> sorting된 배열 안에 band안의 점만 나온다. 그래서 무조건 band안에서 붙어있는 5개만 보면되었다. 

모든 점을 y좌표로 sorting하겠다는 아이디어

밖의 점들까지 모두 정렬하면 밴드 안에 있는 5개를 봐야하니까 배열 멀리까지 가야한다.

이 과정이 O(N)이 되야 한다.

 

 

1. 배열을 따로 하나 만든다.

모두 sorting하고 밴드 안에 있는 것만 모은다. 

5개를 보면 되니까 아까 상황과 같지만 배열 추가 할당으로 느려질 수 있음

5*n

 

2. band 안의 점이 5개가 나올때 까지 간다.

그리고 이것을 다 훑어도 O(n)이 나온다는 사실

 

동그라미의 갯수가 n이 될 수 있지만 (모두 밴드 안에 있는 상황)

어느 x표를 봐도 자신을 훑고 지나간 것이 최대 5개 

이것도 5*n임

 

3. 5개짜리 배열에 이전의 o노드를 기억하고 있는다.

x는 그냥 넘어가고 o면 가장 오래된 애를 5개 배열에서 지운다.

 

 

 

 

=> 전체를 sorting하는 것응로 바꿔도 5개를 보기위해 스캔하는 부분은 성능이 똑같이 O(N)이다.

 

---

핵심 아이디어2

전체를 sorting하는 걸로 바꾸면 sorting을 안하고 merge만 하면 된다.

band안만 sorting하게 되면 나머지는 여전히 x좌표로만 sorting되어 있음 => nlog n소요

전체를 sorting하면 재귀가 끝났을 때 이미 y좌표로 sorting되어 있어 sorting이 아닌 merge로 바뀐다.

=> O(n)

 

nlogn -> n이 되어 전체 NlogN