퀵 정렬
-
[n524] 알고리즘 (2)AI 부트캠프 2022. 1. 28. 10:21
Divide and Conquer(분할 정복) 방법 분할과 정보는 큰 문제를 작은 단위로 나눠서 푸는 알고리즘 방법이다. 재귀 호출과의 차이점은 재귀의 경우 같은 함수 코드를 재호출 하는 것이며, 분할 정복은 비슷한 작업을 재진행 하는 점이다. 즉, 분할 정복은 같은 함수 코드를 재호출 하는 것은 아닐 수 있다. 문제 분할을 스텝 1~5 방향으로 했다면, 문제 해결은 스텝 5~1 방향으로 되어야 한다. 즉 문제를 분할 하는 과정과 해결하는 과정이 있다. 퀵정렬과 병합정렬(Quick Sort and Merge Sort) 둘 다 분할과 정복 (divide and conquer) 개념으로 문제를 해결한다. 보통, 퀵 정렬이 병합 정렬 시간 복잡도는 둘 다 O(nlogn)이다. 퀵 정렬은 좌 우로 나눠서 재귀적..