Stargazer

특징: Worst case에 대해서는 $O(n^2)$ 시간이지만, Average case 에 대해서는 $O(n\log n)$ 시간이 걸린다. 전략: Divide and Conquer(분할 정복): 큰 문제를 여러개의 작은 문제로 분할하여 재귀적으로 처리 후 합쳐서 해결하는 방법 *단계: 1. 분할: 작게 문제를 나눈다.(이때, 나눈 것도 해결전략이 동일한 문제여야한다.) 2. 정복: 재귀적으로 계속 작게 나누면서, 문제를 해결한다.(문제를 해결할 수 있는 가장 작은 단위 까지 나눔) 3. 조합: 해결한 문제들을 조합하여 원래 input에 대한 결과값을 리턴한다. * 분할 정복 알고리즘 수도 코드: solve(I) n=size(I) if(n