칸 아카데미 알고리즘 강의를 정리 및 요약하였습니다.
복습
여태까지 배운 정리한 알고리즘은 선택 정렬과 삽입 정렬입니다. 이 정렬법의 최대 실행시간은 Θ(n^2)입니다. 배열의 크기가 클 경우 이 알고리즘들로는 꽤 오랜 시간이 걸릴겁니다. 그래서 속도가 더 빠른 정렬 알고리즘인 병합 정렬과 빠른 정렬을 배워보겠습니다.
분할 정복 - DIvide and conquer
앞으로 배울 병합 정렬과 빠른 정렬은 모두 재귀 알고리즘 설계 패러다임을 따릅니다. 이 패러다임은 "분할 정복" 으로 통칭합니다. 한 문제를 유형이 비슷한 여러 개의 하위 문제로 쪼개어 재귀적으로 해결 후 이를 합쳐 원래 문제를 해결하는 방식입니다.
분할 정복 방식은 하위 문제 각각이 원래 문제보다 범위가 작아야합니다. 그리고 탈출 조건이 필요합니다. 분할 정복을 이해하기 위해서 세 부분으로 나누어서 정리해보겠습니다.
1. 분할: 원래 문제를 분할하여 비슷한 유형의 작은 하위 문제들로 나눕니다.
2. 정복: 하위 문제 각각을 재귀적으로 해결합니다. 하위 문제의 규모가 작아지면 탈출 조건을 놓고 해결해야합니다.
3. 합치기: 하위 문제들의 답을 합친 후 원래 문제를 해결합니다.
만약 하위 문제가 두 개 생긴다면?
위 그림으로 표현할 수 있습니다. 문제를 두 개의 하위 문제로 나누고, 해결(정복)하고 다시 합쳐서 원래 문제를 푸는 과정입니다.
재귀 문제가 2개 더 확장 된다면?
그림으로 보니 더욱 이해가 직관적이네요! 분할 정복 알고리즘은 최소 두 개의 하위 문제를 생성합니다. 고로 여러번 재귀 호출이 되니 재귀 개념을 익숙하게 다룰 수 있어야합니다!