분할정복
- 분할정복
- 한 문제를 비슷한 여러 하위 문제로 나누어서 재귀적으로 해결하고 이를 합쳐서 원래 문제를 해결
- 퀵소트, 머지소트
- 분할(divide)
- 원래 문제르 분할하여 비슷한 여러 하위 문제로 나누기
- 하위 문제 규모가 충분히 작으면 탈출조건을 걸어주기!
- 정복(conquer)
- 나누어진 하위문제를 정복
- 정복의 방법으로 재귀 활용
- 합치기(combine)
- 분할정복의 장점
- 어려운 문제를 작은 문제로 나눔으로써 어려운 문제를 쉽게 해결
- 작은문제를 분할, 같은 작업을 더 빠르게 처리
- 분할정복의 단점
- 함수를 재귀적으로 호출한다는 점에서 함수 호출로 인한
오버헤드
가 발생한다.
- 스택에 다양한 데이터를 보관하고 있어야 하므로
스택 오버플로우
가 발생하거나 과도한 메모리 사용하게 된다.
- 분할정독을 사용하는 알고리즘 설계 방법
퀵 정렬
- 퀵 정렬은 분할정복 전략을 사용하는 방법 중에서도 중요한 작업은 분할단계에서 일나납니다.
- 분할
- 피벗 설정하기
- 배열에서 아무 요소나 골라 분할랍니다.
- 피벗 설정기준(맨 앞의 값, 맨 뒤의 값, 중간값)
- 파티션하기
- 배열 안의 요소들을
- 피벗보다 작거나 같은요소는 피벗의 왼쪽으로 보내고
- 나머지 요소는 모두 오른쪽으로 보낸다
- [피벗보다 작은 애들][피벗][피벗보다 큰 애들]
- [9, 7, 5, 11, 12, 2, 14, 3, 10,
6
]
- [5, 2, 3][6][9, 7, 11, 12, 14, 10]
- 정복 (분할)
- [5, 2,
3
]
- [9, 7, 11, 12, 14,
10
]
- [9, 7]
- [11, 12,
14
]
- [11,
12
]
- 이 두파트를 재귀적으로 분할하여 정렬한다.
- 더 이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제
- 결합
array = [5, 4, 8 , 9, 1, 3]
- 퀵소트 : 피벗보다 작거나 같은 요서/ 피벗보다 큰 요소를 재귀적으로 정렬하여 정복한다.
병합정렬
- 분할 단계에서는 거의 아무것도 하지 않고 모든 중요한 작업들이 결합단계에서 일어난다.
- 분할
- 정복
- 입력 배열을 같은 크기의 2개 부분배열로 분할한다.
- 결합 (정복)
- 정렬된 배열들을 하나의 배열에 병합
- 정렬된 두 하위 배열을 하나의 정렬된 배열로 결합한다.
- 병합정렬 방법
- 리스트위 중간 지점을 찾는다
- 중간값을 기준으로 반으로 나눈다
- 결합(정복)
- 정렬된 두 하위 배열을 하나의 정렬된 배열로 결합한다.