[ 알고리즘 ] 분할정복법

@ 궁금한 이유

문제 풀이 방법중에 하나로 완전 탐색이 안될 경우 사용하는 방법중에 하나라서 공부하고 싶었다. 

---

@ 공부

분할 정복법( Divide & Conquer )

> 문제를 소문제로 분할

> 각각의 소문제를 해결

> 소문제의 해결 결과를 이용하여 전체 문제를 해결

 

# 대표적인 정렬

## 합병정렬 ( Merge Sort )

> 재귀 호출을 이용한 대표적인 정렬

정확히 가운데를 나누고 나서 각각을 다시 합병정렬 해서 합친다.

T(N) : N 개의 숫자를 정렬하는데 걸리는 시간 

T(N) = 2* T(N/2) + O(N)

> O(N log N)

## 퀵정렬 ( Quick Sort )

> 재귀호출을 이용한 대표적인 정렬

> 피벗 기준으로 작은 것은 왼쪽에 큰 것은 오른쪽으로 나누고

> 작은 문제 2개를 다시 피벗으로 정렬 

> 분할 정복법은 거의 대부분 재귀를 통해서 구현하는 경우가 많다.

 

## 연속 부분 최대합을 분할 정복법으로 풀어 보기

완전탐색법으로 하면 : 연속된 부분을 선택하였을 때, 그 최대 합을 출력

전체시간: 가능한 경우의 수 * 하나의 경우에 걸리는 시간

소문제1, 소문제2 각각의 최대합을 구하자 하지만 중간에 자른 부분을 포함한 것은 고려하지 않았다.

> 자른 지점까지 고려 한다면 전체경우를 고려 하게 된다.