[C++ Algorithm] Ch4. 분할 정복

4.1 들어가며

자료구조와 알고리즘

• 자료구조: 다양한 데이터 저장 방식, 그 안에 저장된 데이터에 접근하는데 필요한 비용 결정
• 알고리즘: 데이터에 대한 정확한 정의와 데이터 변환 순서

분할정복

주어진 문제를 작은 부분 문제로 나눔 -> 나눠진 각 부분 문제의 솔루션을 구함 -> 각 부분 문제 솔루션을 합쳐서 전체 문제에 대한 솔루션을 구하는 방식

• 이진검색, 퀵 정렬, 병합 정렬, 행렬 곱셈 등

4.2 이진 검색

이진검색의 개념

정렬된 리스트에 대하여 데이터를 이분화하여 검색하는 방법

이진검색의 동작 과정

현재 배열의 크기를 range, 찾으려는 데이터를 n이라 간주하고, 배열은 오름차순으로 정렬되어 있다고 간주

1. 배열의 가운데 원소를 m이라고 설정, m과 n을 비교함
2. m = n일 경우 n을 찾은 것이므로 검색 중단
3. 아닐 시, range수정
   • n < m인 경우: m 오른쪽의 원소 제거
   • n > m인 경우: m 왼쪽의 원소 제거
4. range에 두개 이상의 원소가 남아있다면 1단계로 이동
5. 그렇지 않을 경우, 주어진 배열에 n이 존재하지 않는 것이므로 검색 종료

선형 검색과의 비교

선형검색: 시퀀스(배열) 전체 원소를 방문하면서 해당 원소가 n과 같은지 확인

• 효율적이지 않음
• 배열이 정렬되어있다는 것을 이용 X
• 시간복잡도 O(n)

=> 이진검색이 우세

4.3 분할 정복 이해하기

분할정복의 개념

주어진 문제를 작은 부분 문제로 나누어서 해결하는 방식

1. 분할(divide): 주어진 문제를 야러 부분 문제로 나눔
2. 정복(conquer): 각 부분 문제에 대한 해답을 구함
3. 결합(combine): 각 부분 문제에 대한 해답을 결합하여 전체 문제에 대한 해답을 구함

철쁠쁠 Divide and Conquer!

4.4 분할 정복을 이용한 정렬 알고리즘

정렬 알고리즘의 조건

• 모든 데이터 타입에 대해 동작해야 함
• 많은 양의 데이터를 처리할 수 있어야 함 (컴퓨터의 메인 메모리보다 큰 용량의 데이터)
• 점근적 시가 복잡도 측면이나 실제 동작 시에 빠르게 동작해야 함

병합 정렬

많은 원소로 구성된 전체 집합을 작은 크기(부분 배열의 크기가 1일 때까지)의 부분집합으로 나눠 각각을 정렬하고, 정렬된 부분집합을 오름차순 또는 내림차순 순서를 유지하며 합치는 방식

• 모든 데이터를 메인 메모리에 불러올 수 없는 경우에도 사용 가능(대용량의 데이터 정렬 가능)

퀵 정렬

원본 배열을 작은 크기의 부분 배열로 나누고, 각 부분 배열을 정렬한 후, 그 결과를 합쳐서 전체 정렬된 배열을 생성

• 핵심연산은 ‘분할’
• 평균 실행 시간을 줄이는 것이 목표

[퀵 정렬의 분할 연산 방법]

1. 입력 배열이 주어지고, 입력 배열 중 피벗(키) 원소 P선택 -> 배열의 첫 번째 원소를 피벗으로 선택
2. 피벗 다음의 배열의 첫 번째 원소에서부터 피벗보다 큰 값(R)을 탐색, 배열의 끝 원소에서부터 피벗보다 작은 원소(L)를 탐색
3. 탐색 성공 시, 두 값의 위치를 바꿈
4. 2-3의 과정을 반복
5. R과 L이 교차 시, P를 해당 자리로 이동 -> P는 정렬을 완료했을때 실제로 있어야 할 자리임
6. P중심 왼쪽과 오른쪽의 배열에 대해서 1-5과정을 반복

병합 정렬과 퀵 정렬의 점근적 시간 복잡도

알고리즘	최선의 경우	평균	최악의 경우
병합 정렬	O(nlogn)	O(nlogn)	O(nlogn)
퀵 정렬	O(nlogn)	O(nlogn)	O(n^2)

퀵 정렬의 경우 피벗 선택에 따라 실행시간이 달라짐(중간 위치의 원소를 피벗으로 선택하는 경우 최상의 효과)