노트

이 글은 인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 듣고 정리한 내용입니다. Merge Sort(병합 정렬)분할 정복법(Merge Sort, Quick Sort)분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할정복 : 각각의 작은 문제를 순환적으로 해결합병 : 작은 문제의 해를 합하여(Merge) 원래 문제에 대한 해를 구함 1. 리스트의 길이가 0 또는 1이면 이미 정렬된 것으로 본다. 그렇지 않은 경우2. 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다.3. 각 부분의 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다.4. 두 부분의 리스트를 다시 하나의 정렬된 리스트로 합병한다. 의사코드 Merge Sort(A[], p, r) { // 배열 A[p...