[Algorithm] Divide and Conquer (2)
이 글은 포스텍 오은진 교수님의 CSED331 알고리즘 수업의 강의 내용과 자료를 기반으로 하고 있습니다.
알고리즘 3주차 첫 번째 강의 노트이다.
Divide and conquer의 좀 더 심화적인 예제들에 대해서 배울 것이다.
참고로 2.Matrix Multiplication 부터는 시험에 안나온다 ㅎㅎ
1. Closest pair of pointsPermalink
이렇게 점들의 집합이 있을 때, 이 중에서 가장 짧은 거리를 가지는 pair을 구하는 알고리즘을 만들어보자.
정말 간단하게 생각한다면, 그냥 모든 pair을 조사하면 될 것이다.
그러나 이건 O(n2)으로, 좀 느린 편이다.
성능 향상을 위해 divide and conquer을 적용해보자.
-
Divide: x median을 구한다
-
Conquer: 각 subset에서 closest pair을 구한다
-
Combine: 다른 subset까지 고려하여 closest pair을 찾는다
참고: 이 알고리즘은 x축, y축 각각의 기준으로 소팅된 배열을 미리 전달받는다고 가정하고 풉니다. (preprocess)
Divide - Conquer을 거치고 나면 아래와 같은 모습이 될 것이다.
이제 combine을 해야 하는데, 생각해보면 기껏 나눠서 구해놓은 걸 합쳐서 다시 구하면 무슨 의미가 있는건가..?? 싶을 것이다.
바로 이 부분이 알고리즘의 핵심이다. 놀랍게도, combine을 선형시간에 할 수 있다!
아이디어는 제약을 활용하여 추가적으로 계산해야 하는 pair의 경우의 수를 최대한 줄이는 것이다.
왼쪽 subset에서 구한 closest pair의 길이를 δ1, 오른쪽은 δ2라고 하자.
우리가 관심있는 것은 min(δ1,δ2)=δ보다 작은 pair이다.
그렇다면 δ보다 작아질 가능성이 있는 점들만 고려하면 된다.
곧, 이렇게 median line으로부터 좌우로 δ거리 만큼만을 신경쓰면 된다는 것이다.
나중을 위해서 y축으로 정렬도 해놓자.
이제 이 영역을 더 잘게, δ/2 길이의 정사각형으로 나눠보자.
이렇게 나누면 매우 놀라운 사실을 알아낼 수 있다.
각 정사각형에는 2개 이상의 점이 들어갈 수 없다
왜 그럴까? 간단하다.
만약 2개 이상의 점이 들어간다면, δ보다 작은 pair가 생겨버리고, 이는 모순이기 때문이다.
그럼 이 사실로부터 또 다른 놀라운 사실을 알아낼 수 있다.
2행 이상 차이나는 두 점은 무조건 그 거리차가 δ 이상이다
이는 우리가 조사해야 하는 점의 숫자를 획기적으로 줄여준다.
한 행에는 4개의 박스가 들어가고, 2행 이상 차이나는 것은 버리면 되므로 11개의 박스(= 11개의 점)만 비교하면 된다!
사실 대부분의 사이트에서는 7개로 설명한다. 이는 박스의 기준점을 어떻게 잡느냐의 차이이다.
이렇게 점을 기준으로 박스를 나누면 7개라고 볼 수 있고,
이렇게 기준점 없이 그냥 나누면 11개라고 볼 수 있는 것이다.
어떻게 풀어도 상관은 없다. 다만 계수가 더 작은 쪽이 좋지 않나 싶다.
여하튼, y축 기준으로 아래에서부터 올라오면서, 각 점에 대해서 최대 11개의 점만 비교해보면 된다는 것이고, 이는 combine이 선형시간에 이뤄진다는 것을 의미한다!
Time complexityPermalink
이제 time complexity를 구해보자.
median을 구하고 분할하는데 O(n)
sub problem은 2T(n/2)
pre-sorting이 되어있으므로 combine 단계에서, 중앙으로부터 δ 거리 안에 있는 점들을 모으고 이들을 정렬하는데 O(n)
따라서 T(n)≤2T(n/2)+O(n)→T(n)=O(nlogn) 이다!
2. Matrix MultiplicationPermalink
matrix multiplication은 우리가 배운대로 그냥 하면 O(n3)이 걸린다.
상당히 느리다고 할 수 있다.
사실 딱히 개선점이 보이지도 않는다.
연산들이 전부 독립처럼 보이기 때문이다.
그런데, 놀랍게도 스트라센 이라는 사람이 이걸 줄이는 방법을 찾아냈다.
우선 divide and conquer을 적용해보자
그런데 이렇게 되면, 8개의 sub problem이 생긴다.
곧 T(n)≤8⋅T(n/2)+O(n2)=>T(n)=O(n3)이므로 달라지는게 없다는 것을 알 수 있다.
스트라센은 이 공통점이 없어보이는 연산을 놀랍게도 7개의 sub problem으로 줄이는 데에 성공했다.
complexity를 계산해보면 약 O(n2.81)로, 조금 나아졌음을 알 수 있다.
최신 연구 상으로는 1.5 정도까지 떨어졌다고 한다.
3. Polynomial multiplicationPermalink
다항식의 곱셉을 해보자.
A(x)=a0+a1x+⋯+adxd 와 B(x)=b0+b1x+⋯+bdxd가 있다.
이 두 다항식의 곱을 C(x)=A(x)⋅B(x)=c0+c1x+⋯+c2dx2d 이라고 하자.
우리가 일반적으로 하는 것처럼 C(x)를 구하려면 얼마나 걸릴까?
우선 ck=a0bk+a1bk−1+⋯+akb0=∑ki=0aibk−i 이므로, ck를 구하는데에는 O(k)만큼 걸린다.
0≤k≤2d이므로, 총 ∑2dk=0O(k)=O(d2)만큼의 시간이 걸린다!
과연 이걸 향상시킬 수 있을까?
놀랍게도, 가능하다! 무려 O(dlogd)으로 말이다.
1. Another Repres. of polynomialsPermalink
우리는 현재 다항식을 계수들로 표현하고 있다. (a0,a1⋯)
알고리즘의 핵심은 다항식을 이것과는 다른 방식-distinct points-로 표현하는 것이다.
예를 들면 이런 식이다.
어떻게 이게 가능할까?
이는 아래의 theorem 때문이다.
A degree d polynomial is uniquely characterized by its values at any d+1 distinct points
이렇게 distinct points로 표현하는 방법은 기존의 계수 표현법과 자유롭게 전환이 가능하다.
이 전환을 evaluataion, interpolation이라고 한다.
이제 이것을 다항식의 곱셈에 적용해보자.
C(x) 는 2d+1개의 distinct points로 표현될 수 있으므로, 각 point xi에 대해 C(xi)=A(xi)B(xi)를 구해주면 되는 것이다.
2. Evaluation by divide and conquerPermalink
위 알고리즘에서 가장 핵심은 evaluation이다. 유일하게 복잡도를 줄일 수 있는 단계이기 때문이다.
그럼 어떻게 해야 줄일 수 있을까?
Divide and conquer를 적용하기 위해, A(x)를 짝수항과 홀수항으로 쪼개보자.
짝수항을 Ae(x)=a0+a2x+a4x2+⋯+adxd/2 로 묶고
홀수항을 Ao(x)=a1+a3x+a5x2+⋯+ad−1xd/2−1 로 묶으면
A(x)=a0+a1x+⋯+adxd를 Ae(x2)+xAo(x2) 로 표현할 수 있다.
이제 n≥2d+1개의 distinct points를 ±x0,±x1,⋯,±xn/2−1로 잡아보자.
그러면 놀랍게도,
A(xi)=Ae(x2i)+xiAo(x2i)
A(−xi)=Ae(x2i)−xiAo(x2i)
위 두 식은 서로 계산해야 할 것이 겹쳐지게 된다!
이로 인해, n개의 point에 대해 계산해야 하는 문제가 n/2개의 point에 대해 계산해야 하는 2개의 소문제로 나눠지게 된다.
따라서, T(n)=2T(n/2)+O(n)→O(nlogn)이 되어 향상된 다항식 곱셈 알고리즘을 얻을 수 있다.
3. Evaluation by FFTPermalink
근데 이렇게 해서 재귀가 가능할까?
곰곰히 생각해보자. n/2에서 n/4로 가려면 x20,x21,⋯,x2n/2−1를 ±으로 2개씩 묶어야 하는데, 전부 다 양수라서 묶을 수가 없다.
어떻게 해야할까?
제곱해서 음수가 될 수 있는 수, complex number를 도입하면 된다!
그럼 어떤 complex number를 잡아야 할까?
이를 알아보기 위해 과정을 reverse engineer 해보자.
재귀의 끝 T(1)에서 +1을 point로 잡았다고 해보자.
그럼 T(2)에서는 √+1=±1이 point일 것이고,
T(4)에서는 √1=±1,√−1=±i가 point일 것이다.
이걸 일반화하면, T(n)에서는 zn=1의 complex solution들이 point가 된다는 것을 알 수 있다.
zn=1를 풀기 위해서는 드무아브르의 정리를 알아야 하는데, 기억이 나지 않는 분들은 여기에서 3-1 단위근과 이형방정식을 보면 된다.
결론적으로 zn=1의 해는 zk=cos2kπn+isin2kπn,k=0,1,2,⋯,n−1 이다.
여기에 오일러 정리를 끼얹어서 다시 한번 정리해보자.
ω=e2πi/n라고 하면, n개의 해는 각각 1,ω,ω2,⋯,ωn−1이 된다.
이 해들의 기하학적 의미는 단위원에 내접하는 정 n각형의 꼭짓점이라 할 수 있다.
위 그림에서 보다시피, n이 짝수라면 ωn/2+j와 ωj는 서로 ±의 관계를 가짐을 알 수 있다.
곧, (ωj)2를 T(n/2)의 point로 잡을 수 있고, 이같은 방식으로 재귀를 하면 된다.
이렇게 허수를 도입해서 푸는 알고리즘을 FFT(fast fourier transform)이라고 한다.
아래는 FFT의 수도코드이다.
4. 출처 및 참고Permalink
-
https://casterian.net/archives/92 ↩
Leave a comment