/*elice*/ 분할정복법

1.  재귀호출을 이용한 문제 해결

---

 

 

재귀호출은 분할정복법 이외에도 자주 나오는 개념이기 때문에, 재귀호출의 중요성을 강조해왔습니다.

 

 

 

재귀함수의 올바른 디자인 및 해석

재귀함수를 디자인 하기 위한 세 가지 단계

 

1) 함수의 정의를 명확히 한다

2) 기저 조건에서 함수가 제대로 동작하게 작성한다

3) 함수가 제대로 동작한다고 가정하고 함수를 완성한다

 

 

 

아래의 실습에서 가장 먼저 시도해야 하는 것은 '완전탐색'입니다.

완전탐색으로 풀기 위해서는, O(n)의 시간복잡도가 걸리게 됩니다.

따라서 해당 문제에서는 완전탐색이 동작을 할 수 있지만 기저조건 중 하나는 정렬된 이라는 문장을 볼 수 있습니다.

 

 

 

 

 

n개의 숫자가 정렬되어 있다는 점을 이용한 방법으로는 이진탐색이 있습니다.

이진탐색에서는 중간값을 찾고 탐색을 시작합니다. 찾고자하는 값이 중간값보다 작다면 큰 쪽을 버리고, 크다면 작은 쪽을 버리는 식으로 진행합니다.

이진탐색의 최악 탐색시간의 경우 O(log n)입니다.

 

 

 

 

2. 분할정복법

---

 

 

분할정복법에 대하여 알아보겠습니다. 사실 우리는 분할정복법에 대해 배웠습니다.

 

 

분할정복법

문제를 소문제로 분할

각각의 소문제를 해결

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

 

 

소문제를 나누고 나뉘다보면 기저조건을 만족할 수 있게 됩니다.

그런데 분할정복은 어렵습니다.

어떤 작은 문제로 분할을 해야할 지 헷갈릴 수 있습니다.

 

그렇기 때문에,

 

수학적 문제 해결 능력이 가장 중요합니다. 키보드 대신에 노트와 펜을 들고 생각하는 것이 좋습니다.

아래와 같은 합병정렬은 분할정복법의 대표적인 예제입니다.

 

 

 

 

합병정렬의 아이디어는 반으로 나눈뒤, 왼쪽 리스트와 오른쪽 리스트를 각각 정렬되도록 합니다.

 

 

 

 

그리고 정렬된 왼쪽과 오른쪽을 합치면 전체 정렬된 배열로 구성됩니다.

 

 

어떻게 합칠까요?

 

각 리스트의 맨 앞에 있는 요소를 비교합니다. 왼쪽 리스트에서는 2가 제일 작고, 오른쪽 리스트에서는 1이 제일 작습니다.

각 리스트에서 제일 작은 요소를 비교해서 빼게 됩니다.

만약 값이 같다면 왼쪽에서 요소를 빼줍니다.

 

 

합병 정렬의 시간복잡도

합병정렬의 시간복잡도는?

n개를 정렬하는데 드는 시간 = T(n)

 

 

T(n) = T(n/2) + T(n/2)

 

절반 정렬 T(n/2) + 정반 정렬 T(n/2)의 시간이 들고, 이 둘을 합치는데 드는 시간은 왼쪽과 오른쪽 리스트의 요소를 하나하나 비교하게 되므로

T(n) = T(n/2) + T(n/2) + O(n)이게 됩니다.

 

합병정렬에서도 리스트의 길이가 1인 경우가 기저조건입니다.

그러므로 n이 1이 될때까지 2로 나누는 횟수는 log n번입니다.

 

다시 말해 합병 정렬의 시간복잡도는 log n x O(n) = O(n log n)입니다.