Stargazer

단순 합병 문제: 두 시퀀스 A, B를 오름차순으로 주어진다고 할때, 두 시퀀스를 하나로 합병한, 정렬된 시퀀스 C를 구하라(C 크기 = n) 합병 전략: A,B의 최소값 중 더 작은값을 C에 넣는데, 만약 최소값이 A 에 있다고 가정하면, A의 최소값을 C에 넣고, A의 나머지와 B, 그리고 C 를 재귀적으로 함수를 호출하여 합병을 한다.(분할 정복) 합병 수도코드: Merge(A,B,C) if(A is empty) rest of C = rest of B else if(B is empty) rest of C = rest of A else if (first of A

특징: 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