YS's develop story

알고리즘 ) 분할 정복법 알고리즘의 해결전략 Divide and Conquer를 분할 정복법이라고 합니다. 분할 정복법은 주어진 문제를 작은 사례로 나누어(Divide) 각각의 작은 문제들을 해결(Conquer)하는 방법입니다. 프랑스의 황제 나폴레옹이 전투에서 사용했던 훌륭한 전략에서 이름을 따왔다고 하네요. 나누어라, 그리고 정복하라.. 멋있는 말입니다... Merge Sort Best Case 시간복잡도 : O(n log n) Worst Case 시간복잡도 : O(n log n) 분할 단계 array를 두 개의 subarrays로 나눕니다. 정복 단계 각각의 subarray가 충분히 작다면 바로 정렬 합니다. 그렇지 않다면 재귀를 통해 각각을 정렬합니다. 결합 단계 정렬된두 개의 subarray를 ..