분할정복 & 재귀 알고리즘 기본 개념

분할정복법 (Divide and Conquer)

문제를 작게 쪼개서 해결한 뒤, 다시 합쳐서 전체 문제를 푸는 방식

3단계 과정

1. 분할(Divide): 문제를 더 작은 하위 문제로 나눈다.
2. 정복(Conquer): 하위 문제를 재귀적으로 해결한다.
3. 통합(Combine): 하위 문제들의 해를 합쳐서 원래 문제를 해결한다.

특징

• 하향식(Top-Down) 접근
• 대표 알고리즘: 병합정렬, 퀵정렬
• 동적 프로그래밍은 이와 반대로 상향식(Bottom-Up) 방식 사용

 

재귀 알고리즘 (Recursion)

자기 자신을 호출해서 문제를 해결하는 방식

특징

• 문제를 더 작은 동일한 문제로 줄여나감
• 종료 조건(Base Case) 꼭 있어야 함 → 없으면 무한 호출 = 스택 오버플로우 발생
• 구조가 간단하고 우아한 코드 작성 가능
• 일부 **꼬리 재귀(Tail Recursion)**는 반복문으로 쉽게 바꿀 수 있음

예제1)

def factorial(n):  #n!을 계산하는 재귀알고리즘
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)
    
def gcd(n,m): #자연수 n과 m의 최대공약수를 계산하는 재귀알고리즘
    if m == 0:
        return n
    else:
        return gcd(m, n%m)

 

예제2)

배열의 합을 구하는 알고리즘 (반복 vs 재귀)

반복

def arr_sum(n, a):  #크기가 n인 배열 a의 합을 구하는 반복 알고리즘
    sum = 0
    for i in range(n):
        sum += a[i]

    return sum

단순 반복구조이므로 시간복잡도는 T(n) = O(n)

 

 

재귀(재귀 + 분할정복)

 

def arr_sum(a, low, high):  #배열 a[low ... high]의 합을 구하는 재귀 알고리즘
    if low == high: #basecase
        return a[low]
    mid = (low + high) // 2
    return arr_sum(a, low, mid) + arr_sum(a, mid + 1, high)
    
arr = [1,2,3,4,5]
print(arr_sum(arr,0,len(arr)-1))

시간복잡도 T(n) = T(n/2) + T(n/2) + c(분할시간)

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

 

---

 

a 는 상수여야 함.

---

분할정복을 피해야 하는 경우

분할정복이 항상 효율적이지는 않음

크기 n을 거의 유지한 채, 여러 개로 나누는 경우 시간복잡도 = O(2^n)

문제를 작게(n/2) 나누는게 아니라 n-1씩 줄어들음. n-1, n-2 ....

 

대표적 예시로 피보나치 수열에서

fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

 

이게 한 번만 호출되는 게 아니라,
두 개의 하위 문제를 푸는데

• fibonacci(n-1) 도 거의 크기가 n 이고
• fibonacci(n-2) 도 꽤 크다 (나눠도 크기가 n 처음상태와 비슷함)

즉, 문제를 풀면서 작게 나누는 게 아니라
거의 비슷한 크기의 문제 2개를 또 풀고 있게됨.