분할 정복 알고리즘

1.선택 문제 

*선택 문제 해결을 위한 간단한 방법

ex)n개의 숫자들 중에서 k번쨰로 작은 숫자를 찾는 문제

1)최소 숫자를 k번 찾음 

-단, 최소 숫자를 찾은 뒤에는 입력에서 최소 숫자를 제거함 

-최악의 경우 시간 복잡도 O(kn)

2)숫자들을 정렬한 후, k번쨰 숫자를 찾음 

-최악의 경우 시간 복잡도 O(nlogn)

2.최근접 점의 쌍 찾기 문제 

*2차원 평면상의 n개의 점이 입력으로 주어질 때, 거리가 가장 가까운 한쌍의 점을 찾는 문제

분할정복 알고리즘 적용 

평면 판을 반으로 나누고 각판에 가까운 점을 구하고 

두점중 가장 가까운 점으 거리로 x 값으로 두고 

x값 사이의 점들의 거리를 구하고 

판과 판사이의 가장 가까운 점을 구한다 

시간 복잡도 => O(nlog²n)

3.분할 정복을 적용하는데 있어서 주의할 점 

1. 입력이 분할될 때마다 분한된 부분 문제의 입력

크기의 합이 분할 되기 전의 입력 크기보다 매우 커지는 경우

ex)피보나치 수 계산 알고리즘 (재귀 호출) 피보나치는 배열사용하면 된다