분할 정복

퀵 정렬 알고리즘 개념퀵 정렬은 분할 정복 알고리즘(문제를 더 작은 2개의 문제로 분리해서 해결한 후 결과를 모아서 원래 문제를 해결하는 방법)의 하나로 찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)기사가 개발했다. 가장 자주 사용하는 정렬 알고리즘으로 빠른 수행 속도가 특징이다. 기본적인 퀵 정렬은 아래 3단계를 반복하며 정렬한다. 기준(Pivot; 피벗) 요소 선택 — 주로 배열의 중간 요소를 기준으로함기준 요소보다 작은 요소는 왼쪽으로 이동, 기준 요소보다 큰 요소는 오른쪽으로 이동이동시킨 왼쪽 / 오른쪽 요소들에 대해 1~2번 작업 반복 구현Basic Quick Sort💡 구현하기 쉽지만 항상 새로운 left / right 배열을 생성해 비교한 요소를 추가하므로 ..

분할 정복 (Devide & Conquer)개념분할 정복은 “큰 문제를 작은 문제 단위로 쪼개면서 해결해나가는 방식"이다. 미국 수학자 폰노이만이 1945년에 개발한 알고리즘이다. 퀵소트, 병합 정렬이 분할 정복 방법을 통해 구현한다.예전엔 테이프를 이용해 데이터를 저장했다. 테이프 드라이브에 저장된 데이터는 항상 처음부터 순차적으로 읽어야 하기 때문에 데이터를 정렬하기 어려웠다. 이런 테이프 드라이브의 문제점을 극복하기 위해 병합 정렬 알고리즘이 탄생했다. 분할 : 문제를 더 이상 분할할 수 없을 때까지 동일 유형의 여러 하위 문제로 나눈다정복 : 가장 작은 단위의 하위 문제를 해결하며 정복한다조합 : 하위 문제에 대한 결과를 원래 문제에 대한 결과로 조합한다 예시분할 정복은 구조는 동일하지만 더 작은..