7.1 분할 정복_도입(1)

1. 분할 정복(Divide & Conquer)이란?

• 주어진 문제를 둘 이상의 부분 문제로 나눈 뒤 각 문제에 대한 답을 재귀 호출을 이용해 계산하고, 각 부분 문제의 답으로부터 전체 문제의 답을 계산하는 방법
• 일반적인 재귀 호출과 다른 점은 문제를 한 조각과 나머지 전체로 나누는 대신 거의 같은 크기의 부분 문제로 나누는 것이다.

 

2. 분할 정복을 사용하는 알고리즘의 3 가지 구성 요소

먼저, 분할 정복을 사용하기 위해서는 문제를 둘 이상의 부분 문제로 나누는 자연스러운 방법이 있어야 한다.

• 문제를 더 작은 문제로 분할하는 과정(Divide)
• 각 문제에 대해 구한 답을 원래 문제에 대한 답으로 병합하는 과정(Merge)
• 더이상 답을 분할하지 않고 곧장 풀 수 있는 매우 작은 문제(Base case, 기저 사례)

---

3. 예제 1 : 수열의 빠른 합

(1) 1부터 n까지의 합을 재귀 호출을 이용해 계산하는 함수(fastsum(n))를 분할 정복을 통해 구현

 

먼저, fastsum(n)은 다음과 같이 표현 가능한다.

위 알고리즘의 3 가지 구성 요소중 첫 번째 요소를 활용하여 1부터 n까지의 합을 다음과 같이 2 부분으로 분할한다.

 

그리고 분할된 부분의 뒷 부분인 ((n/2 + 1) + ... + n)는 다음과 같이 표현 가능하다.

따라서, 분할된 앞 부분이 fastsum(n/2)임을 생각하면 fastsum(n)은 다음과 같다.

(2) 이 아이디어를 구현한 코드

def fastsum(n):
    # 기저 사례 1 : n == 1
    if n == 1:
        return 1
    
    # 기저 사례 2 : n이 홀수
    if n % 2 == 1:
        return fastsum(n-1) + n

    return 2 * fastsum(n/2) + (n / 2) * (n / 2)

• fastsum(n)은 호출될 때마다 최소한 두 번에 한 번꼴로 n이 절반으로 줄어든다.(n이 짝수인 경우 n을 절반으로 줄여 계산)
• 책의 설명은 n을 이진법으로 표현하여 호출 횟수를 계산하지만 n이 절반씩 줄어드는 비슷한 경우인 이진 탐색을 생각하면 시간 복잡도는 O(logN)로 나타남을 알 수 있다.

---

4. 예제 2 : 행렬의 거듭 제곱

(1) 문제 분할

• 위 아이디어를 이용해 행렬 A의 거듭제곱은 A^m을 분할 정복으로 구할 수 있다.
• 먼저, 행렬의 거듭제곱은 A^m은 다음과 같이 분할할 수 있다.

(2) 구현 코드

def pow(a, m):
    # 기저 사례 1: A^0 == 1
    if m == 0:
        return 1
    
    # m이 홀수인 경우
    if m % 2 > 0:
        return pow(a, m-1) * a

    half = pow(a, m / 2)

    return half * half

• 사실, 이 코드는 행렬의 거듭 제곱이 아니라 어떤 수의 거듭 제곱을 구하는 방법이다.
• 책에 나와있는 코드를 참고하자면 m=0인 경우 행렬의 항등 행렬을 반환하는 과정을 구현해야 하지만 문제의 분할 방법에 대한 이해가 중요하기 때문에 따로 진짜 행렬의 거듭 제곱을 구하는 방법은 생략한다.
• m이 홀수인 경우 m-1을 통해 짝수로 만들어 재귀 호출을 진행하는데 m이 31이라고 가정하면 A^15과 A^16로 분할하는 것이 더 좋지 않은가 생각할 수 있다.
• 하지만 실제로 A^15과 A^16으로 분할하여 재귀 호출을 할 경우 A^1와 A^30로 분할하여 호출하는 것에 비해 중복하여 호출하는 횟수가 많아진다.
• 이는 같은 문제라도 어떻게 분할하느냐에 따라 시간 복잡도 차이가 커진다는 것을 보여주는 예이다.

---

github : Algorithmic_Problem_Soving_Strategies/code7_1.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies

github : Algorithmic_Problem_Soving_Strategies/code7_2.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies