[알고리즘] 분할정복법(Divide and Conquer)이란?

분할정복법이란?

풀기 어려운 문제를 작은 크기의 부분 문제로 재귀적인 분할을 한 후
부분 문제의 해답을 다시 합병하여 답을 얻는 접근 방법이다. 

 

---

언제 분할정복법을 사용하는가?

1. 최적 부분 구조를 가지고 있을 때

 

=> 문제를 만났을 때 

1. 부분 문제로 쪼개지는가?
2. 부분 문제의 해답이 전체 문제의 해답에 유효한가? 

 

---

어떻게 분할정복법을 사용하는가?

 

1. 해답의 구조를 파악해 어떻게 subproblem(부분문제)으로 나눌 지(최적 부분 구조 만족하도록) 결정한다. -> 일반화된 n번째에 대한 생각

2. 분할한 부분 문제의 해답을 종합해 전체 문제의 답을 구한다. 

---

예시

예시1)

n개의 수 중에서 최대 값 구하기(find_max)

 

def find_max1(A):
    if len(A) == 1: return A[0]
    else: return max(A[0], find_max1(A[1:]))

- 알고리즘 설명 : A[0]과 A[1:]으로 분할하여 재귀적으로 반복해 최댓값을 찾는다.

- 선형 재귀호출

- 시간 복잡도 T(n) = T(n-1) + c,  T(1) = c -> T(n) = nc = O(n)

 

def find_max2(A):
    if len(A) == 1: return A[0]
    else: return max(find_max2(A[:len(A)//2]), find_max2(A[len(A)//2:]))

- 알고리즘 설명 : 반씩 나눠서 양쪽에서 최댓값을 찾는 방법 

- 이진 재귀호출

- 시간 복잡도 T(n) = 2T(n/2) + c, T(1) = c -> T(n) = c(1+2+...+2^k) = O(2^k) = O(n)

 

 

---

 

예시2)

a^n을 계산하기- n을 양의 정수로 가정(power)

 

def power1(a, n):
    if n == 1: return a
    return a * power1(a, n-1)

- 알고리즘 설명 : n이 1이 될 때까지 반복해서 곱해줌 

- 선형 재귀호출

- 시간 복잡도 T(n) = T(n-1) + c = O(n)

 

def power2(a, n):
    if n == 0: return 1
    if n % 2 == 1:
        return power2(a, n//2) * power2(a, n//2) * a
    else:
        return power2(a, n//2) * power2(a, n//2)

- 알고리즘 설명 : a^6 = a^3 * a^3 이렇게 되는 지수법칙을 이용하는 것, n이 홀수면 '//' 했을 때 소수점 버리기 때문에 a를 한번 더 곱해줘야함! 그래서 n이 홀수일 때와 짝수일 때를 케이스를 나눠서 코드 작성 

- 이중 재귀 호출

- 시간 복잡도 T(n) = 2T(n/2) + c = O(n)

 

def power3(a, n):
    if n == 0: return 1
    p = power2(a, n//2)
    if n % 2 == 1:
        return p * p * a
    else:
        return p * p

- 알고리즘 설명 : power2 코드에서는 같은 결과에 대한 재귀호출을 반복적으로 부르기 때문에 비효율적임. 재귀호출을 먼저 하고 연산을 하면 반복적인 재귀 호출을 피할 수 있음  

- 선형 재귀호출

- 시간 복잡도 T(n) = T(n/2) + c = ... = O(logn)

 

---

예시3)

피보나치수 구하는 방법

 

def fibonacci1(n):
    if n <= 1: return n
    return fibonacci1(n-1) + fibonacci1(n-2)

- 알고리즘 설명: n번째 피보나치 수를 리턴하기 위해서 n-1, n-2를 재귀호출한다.

- 지수시간이 걸리는 매우 느린 알고리즘

 

 

def mult_matrix(A,B):
    n = len(A)
    C=[[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j]+=A[i][k]*B[k][j]
    return C

def power(A, n):
    if n == 1: return A
    B = power(A, n//2)
    if n % 2 == 0:
        return mult_matrix(B, B)
    else:
        return mult_matrix(A, mult_matrix(B, B))
    

def fibonacci2(n):
    if n == 1: return A
    a = [[1, 1], [1, 0]]
    An = power(a, n)
    return An[1][0]

- 알고리즘 설명: 위의 행렬식을 이용하면 power3의 방법으로 행렬의 제곱을 해서 O(logn)만에 fn을 계산 가능하다. 

- 시간복잡도 : O(logn)

 

 

예시4)

하노이탑

 

 

예시5)

이진 탐색

 

slicing 이용해 재귀적으로 이진 탐색

def binary_search1(A, K):
    if len(A) < 1:
        return -1
    m = len(A)//2
    if A[m] < K:
        binary_search1(A[m+1:], K)
    elif A[m] > K:
        binary_search1(A[:m], K)
    else:
        return m

- 알고리즘 설명: 정렬이 되어있는 상황에서 슬라이싱을 하면서 범위를 반씩 줄여나가며 탐색을 하는 방법. 슬라이싱 이용하기 때문에 복사하는 시간이 걸려서 수행시간이 늘어나는 단점이 있다. 

- 시간복잡도: T(n) = T(n/2) + cn = O(n)

 

 

 

slicing 이용하지 않고 재귀적으로 이진 탐색

def binary_search2(A, l, r, k):
    if 1 > r:
        return -1
    m = (l+r)//2
    if A[m] > k:
        binary_search2(A, l, m, k)
    elif A[m] < k:
        binary_search2(A, m+1, r, k)
    else:
        return m

- 알고리즘 설명: 슬라이싱 이용하지 않고 2개의 인자로 인덱스 접근을 하기 때문에 시간복잡도 면에서 좋음.

- 시간복잡도: T(n) = T(n/2) + c = O(logn)

 

 

slicing 이용하지 않고 비재귀적으로 이진 탐색

def binary_search3(A, k):
    l, r = 0, len(A)
    while l - r >= 0:
        m = (l+r)//2
        if A[m] > k:
            r = m - 1
        elif A[m] < k:
            l = m + 1
        else:
            return m

- slicing 이용하지 않아 메모리 낭비가 적고, 비재귀적이라 재귀호출의 부담이 없는 가장 바람직한 이진 탐색 코드