#14 분할 정복(Divide and Conquer)

 분할 정복(Divide and Conquer)은 큰 문제를 작은 문제로 쪼개서 처리하는것으로 보다 효율적으로 문제를 해결하는 방식이다.  문제를 작게 쪼갠 후 쪼개진 문제들을 또 다시 작게 쪼개는 형태로 이루어지기 때문에 보통 재귀를 사용하여 구현하게 된다.  알고리즘 문제풀이에 굉장히 자주 사용되는 기법이기 때문에 관련 문제들을 풀어보며 잘 정리해보기로 한다.

 

1. 종이의 개수(https://www.acmicpc.net/problem/1780)

 n*n 행렬로 표현되는 종이가 한가지 색으로 이루어져있다면 종이를 그대로 사용, 그렇지 않다면 같은크기로 9등분하고 각 종이들에 대해 같은 작업을 반복한다고 할 때, 작업이 끝난 후 색깔별 종이의 갯수를 구하는 문제.  전형적인 분할 정복 문제의 유형이다.  문제에서 이미 해야할 일을 모두 알려줬기 때문에 재귀를 사용하여 그대로 구현하기만 하면 해결 가능하다. 이를 해결한 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline


def sol1780():
    n = int(input())
    paper = [list(map(int, input().split())) for _ in range(n)]
    res = [0, 0, 0]

    def check(r, c, s):
        color = paper[r][c]
        # 1칸짜리 종이라면 해당 종이 색의 카운트를 1 증가 후 종이의 색을 반환
        if s == 1:
            res[color + 1] += 1
            return color

        g = s // 3
        cut = False
        # 종이를 9등분하여 재귀호출
        for i in range(r, r + s, g):
            for j in range(c, c + s, g):
                if check(i, j, g) != color:
                    cut = True

        # 쪼갠 종이들이 모두 같은 색이 아니었다면 2 반환
        if cut:
            return 2

        # 모두 같은 색이었다면 중복으로 더해진 갯수를 빼준 뒤 색(-1, 0, 1) 반환
        res[color + 1] -= 8
        return color

    check(0, 0, n)
    return '\n'.join(map(str, res))

 이 문제처럼 분할 정복을 어떻게 적용해야할지 대놓고 알려주는 문제의 경우 그것을 구현하는 것은 그리 어려운 일이 아니지만 분할 정복 문제의 경우 조금 잘못구현하면 시간초과가 발생할 정도로 시간제한이 빡빡한 경우가 많기때문에(특히 파이썬으로 푼다면 더욱) 구현의 연습자체도 어느정도 해둘 필요가 있다.  예를들어 위 코드에서도 문제대로면 종이가 모두 같은색인지 검증한 뒤 종이를 잘라야하지만 실제로 그렇게 했다간 K크기로 잘라진 종이마다 K^2 만큼의 시간을 추가로 사용하게 된다. 그렇기에 조각난 종이들이 반환한 결과를 보고 나눌 필요가 없었다면 나누지 않은 것으로 결과를 수정하는 방식을 취하였다.

 

 

2. 곱셈(https://www.acmicpc.net/problem/1629)

 자연수 a, b, c가 주어졌을 때 a의 b제곱을 c로 나눈 나머지를 구하는 매우 간단한 문제이다. 다만 a, b, c의 크기가 상당히 크고 제한시간도 짧기 때문에 단순히 a ** b % c 를 했다간 당연하게도 시간초과가 발생한다.  이 문제도 분할 정복 기법을 사용하여 중복연산을 줄이고 빠르게 해결 가능하다. 이를 해결한 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline


def sol1629():
    a, b, mod = map(int, input().split())

    def pow(a, b):
        nonlocal mod
        # b가 1일경우 a를 반환
        if b == 1:
            return a % mod

        # a의 b//2 제곱의 제곱을 구한 뒤 % mod
        res = pow(a, b // 2) ** 2 % mod

        # 만약 b가 홀수라면 a를 한번 더 곱한 뒤 % mod
        if b % 2:
            res = (res * a) % mod

        return res

    return pow(a, b)

 이런 문제들은 1번의 문제처럼 분할정복을 어떻게 적용할지를 대놓고 알려주지 않는다.  물론 이 문제의 경우 한눈에 어떻게 적용해야할지 보이는 수준의 간단한 문제지만 어려운 문제일수록 분할정복으로 접근해야한다는 생각을 하고 어떻게 분할정복 기법을 적용해야할지 아이디어를 떠올리기가 쉽지않다.  

 

 

3. 행렬 제곱(https://www.acmicpc.net/problem/10830)

 2번 문제가 자연수의 제곱을 빠르게 구하는 것이었다면 이번에는 행렬의 제곱을 빠르게 구하는 문제이다.  당연하게도 분할정복 기법을 적용하는 아이디어는 2번 문제와 거의 동일하다. 이를 해결한 코드는 다음과 같다.

 

import sys

input = sys.stdin.readline
mod = 1000


def sol10830():
    n, b = map(int, input().split())
    mat = [list(map(int, input().split())) for _ in range(n)]
    
    # 행렬의 b제곱을 구한다
    mat = matsq(mat, b)
    
    # b가 1일 경우 matmul 함수를 거치지않아 각 원소에 나머지연산이 적용되지 않을 수 있음
    for i in range(n):
        for j in range(n):
            mat[i][j] %= mod
            
    return '\n'.join([' '.join(map(str, mat[i])) for i in range(n)])
   

# 행렬의 거듭제곱
def matsq(m, x):
	# x가 1이라면 m 반환
    if x == 1:
        return m
        
    # m^(x//2)의 제곱을 구한 뒤 x가 홀수라면 m을 한번 더 곱해준다
    res = matsq(m, x//2)
    res = matmul(res, res)
    if x % 2:
        res = matmul(res, m)
    return res
    

#행렬의 곱셈
def matmul(a, b):
    res = [[0] * len(a) for _ in range(len(b[0]))]
    for i in range(len(a)):
        for j in range(len(b[0])):
            for k in range(len(b)):
                res[i][j] += (a[i][k] * b[k][j])
            # 각 원소를 계산한 뒤 나머지연산 
            res[i][j] %= mod
    return res

행렬의 곱셈이나 거듭제곱은 다른 문제에도 종종 활용될 수 있어 기억해두면 도움이 될 수 있다.

 

 

4. 피보나치 수 6(https://www.acmicpc.net/problem/11444)

 피보나치 수열의 n번째 수를 구하는 문제이다.  동적계획법을 사용한 방법의 경우 O(N)의 시간으로 피보나치 수를 구할 수 있지만, 이 문제의 경우 n이 최대 1,000,000,000,000,000,000까지 올라갈 수 있기 때문에 더 빠른 알고리즘이 필요하다.  하지만 3번의 행렬의 거듭제곱을 활용하면 더 빠르게 피보나치 수를 구할 수 있다. 피보나치 수열의 점화식인 F(N) = F(N-1) + F(N-2)를 행렬의 형태로 나타내면 아래와 같은 형태가 된다

즉, 1 * 2 행렬의 초기값을 (F(0), F(1)) 로 잡고 2 * 2 행렬 ((0, 1), (1, 1)) 의 N-1 제곱을 곱해준 뒤 행렬의 두 번째 값을 취하면 F(N)을 구할 수 있다. 물론 N이 0 또는 1인 경우는 예외적으로 처리를 해둘 필요가 있다. 이 방식은 분할 정복 기법을 적용한 행렬의 거듭제곱이 O(logN)의 시간복잡도를 가지기 때문에 O(logN)의 시간으로 피보나치 수를 구할 수 있다. 이를 구현한 코드는 다음과 같다.

 

import sys

input = sys.stdin.read
mod = 1000000007


def sol11444():
    n = int(input())
    # n이 1 이하일 경우 자기자신을 반환 
    # F(0) = 0, F(1) = 1
    if n <= 1:
        return n
        
    # 초기 피보나치 행렬 (0, 1)에 ((0, 1), (1, 1))의 n-1 제곱을 곱해준다
    f = [[0, 1]]
    o = [[0, 1], [1, 1]]
    f = matmul(f, matsq(o, n - 1))

	# 계산이 끝난 후 피보나치 행렬의 두 번째 요소가 n번째 피보나치 수가 된다.
    return f[0][1]


# 행렬의 곱셈
def matmul(a, b):
    r, c, m = len(a), len(b[0]), len(b)
    res = [[0] * c for _ in range(r)]
    for i in range(r):
        for j in range(c):
            for k in range(m):
                res[i][j] = (res[i][j] + a[i][k] * b[k][j]) % mod
    return res


# 행렬의 거듭제곱
def matsq(m, x):
    if x == 1:
        return m
    res = matsq(m, x // 2)
    res = matmul(res, res)
    if x % 2:
        res = matmul(res, m)
    return res


if __name__ == '__main__':
    print(sol11444())