helloahram

병합 정렬일단 반으로 나누고, 나중에 합쳐서 정렬한다  1. 하나의 리스트를 두 개의 균등한 크기로 분할하고 2. 분할된 부분 리스트들을 정렬해서 3. 정렬된 부분 리스트들을 합친다  퀵 정렬과의 차이점 병합 정렬 Merge Sort퀵 정렬 Quick Sort시간 복잡도최악의 경우에도 O(N* logN) 보장 최악의 경우 O(N^2)진행 방법 정확히 반절씩 나눈다 피벗 값에 따라서 편향되게 분할할 가능성이 있다공간 복잡도메모리 활용 비효율적(기존의 데이터를 담을 추가적인 배열 공간 필요)  Merge Sort 를 Python 으로 구현해보기  1번 방식mergeSortdef mergeSort(a): # a 의 길이가 1 이하이면 끝 if len(a)  Mainif __name__ == "__m..

분할 정복 Divide and Conquer큰 문제를 작은 문제들로 나누어 각 작은 문제를 해결한 후, 그 해를 결합하여 원래 문제를 해결하는 방법  기본적으로, 크고 복잡한 문제를 더 풀기 쉬운 작은 문제들로 나누고각각을 해결한 후 다시 합쳐서 문제를 해결하는 개념에서 출발한다 1. 분할 Divide 큰 문제를 더 작은 하위 문제로 나눈다2. 정복 Conquer 각 하위 문제를 재귀적으로 해결한다, 하위 문제가 충분히 작아지면 직접 해결    (하위 문제의 크기가 더 이상 나눌 수 없는 단위에 이르면 재귀 호출을 멈추고 해결)3. 결합 Combine 해결된 하위 문제들을 결합하여 원래 문제에 대한 해답을 구한다 * Divide 를 설계하면 Conquer 과정이 자동으로 쉬워지기 때문에 문제를 어떻게 나..