3. 분할 정복(divide-and-conquer) 설계 전략

안녕하세요

공상 개발입니다.

 

이번 시간에는 재귀(Recursion) 알고리즘에 대해서 알아보는 시간을 가지겠습니다.

---

 

1. 분할 정복법(divide-and-conquer) 2. 재귀(recursion) 알고리즘

 

---

 

# 분할 정복법(divide-and-conquer)

 

분할 정복 설계 전략

 

step1(분할) 문제를 (하나 이상의) 더 작은 문제로 분할합니다.

step2(정복) 작은 문제들을 각각 재귀적으로 정복(해결)합니다.

step3(통합) 필요한 경우, 작은 문제에 대한 해답을 통합하여 원래 문제의 해답을 구합니다.

 

하향식(top-down) 접근 방식

상위 사례의 해답을 더 작은 사례에 대한 해답을 재귀적으로 구함으로써 문제를 해결합니다. 대표적인 분할 정복 정렬 알고리즘으로는 병합 정렬과 퀵 정렬이 있습니다.

 

---

 

# 재귀(recursion) 알고리즘

 

재귀는 문제에 대한 해답을 같은 속성의 더 작은 문제들에 대한 해답으로부터 구하는 방법입니다. 쉽게 말해 함수(메서드)에서 자기 자신을 호출(self-call)하는 구조입니다.

 

이해를 돕기 위해 factorial를 계산하는 재귀 알고리즘을 보겠습니다.

 

 

출력 값

 

5를 입력하면 factorial(5) == 5*factorial(4) factorial(4) == 4*factorial(3) factorial(3) == 3*factorial(2) factorial(2) == 2*factorial(1) factorial(1) == 1 retrun 되는 값은 5*4*3*2*1

 

---

 

이어서 배열의 합을 구하는 로직을 생각해봅시다. 1. 반복 알고리즘으로 해답을 구한다. 2. 재귀 알고리즘으로 해답을 구한다.

반복 알고리즘 arr_sum([n] arr) sum=0           for i=0, ..., n-1           sum+= a[i]       return sum 시간 복잡도 T(n)= O(n)

재귀 알고리즘 1 arr_sum(last)                        if(last ==0) return a[last];                              return arr_sum(last-1)+a[last]; 단계마다 문제의 크기가 1씩 줄어듭니다. 시간복잡도는 T(n) = O(n) "반복적 치환"

재귀 알고리즘 2 arr_sum(low, high)                        if(low == high) return a[low];                mid = (low + high) / 2                                                     return arr_sum(low, mid) + arr_sum(mid + 1, high) 단계마다 절반 크기의 문제가 두 개씩 생겨남 시간 복잡도 T(n) = T(n/2) + T(n/2) + 1 = 2T(n/2)+1

 

재귀 알고리즘 2의 경우에는 이해가 안 되시는 분도 계실 것 같아 아래에 로직을 설명합니다.

 

크기가 6인 배열이 있다고 생각해 봅시다.

재귀 알고리즘 2로 문제를 해결하려면, 아래와 같이 그림을 그리면 편합니다.

 

 

mid == 2 1. arr_sum(0,2) + arr_sum(3, 5) 2. arr_sum(0,2)는 mid == 1, arr_sum(0,1) + arr_sum(2,2) 3. arr_sum(0,1)는 mid == 0, arr_sum(0,0) + arr_sum(1,1) 4. arr_sum(3, 5)는 mid == 4, arr_sum(3,4) + arr_sum(5,5) 5. arr_sum(3,4)는 mid ==3, arr_sum(3,3) + arr_sum(4,4) 6. return a[0]+a[1]+a[2]+a[3]+a[4]+a[5]

 

위의 로직은

arr_sum(low, mid) + arr_sum(mid + 1, high) 코드의 재귀적인 동작을 말로 풀어서 설명한 것입니다.

 

---

 

 

작성된 내용 중 잘못된 정보나 접근이 있을 시, www.instagram.com/hong_.98/을 통해 말씀해 주시면 감사하겠습니다.

 

좋은 하루 보내세요.