[python] 알고리즘_분할정복(Divide and Conquer)

정의 : 문제를 즉각 해결할 수 있을 때까지 재귀적으로 둘 이상의 하위 문제(Sub-problem)들로 나누고(Divide) 문제를 해결한 다음(Conquer) 그 결과를 이용해 다시 전체 문제를 해결하며 합치는 방법

분할정복 알고리즘이란?

분할정복 방식으로 해결되는 문제들은 예를 들면 다음과 같다.

① 정렬문제(퀵 정렬 - 참조, 병합 정렬 - 참조)
② 큰 숫자 곱하기(Karatsuba 알고리즘) : n자리 수 2개를 곱하여 결과를 나타내는 알고리즘
③ 이진 탐색(Binary Search - 참조)
④ Closest Pair of Points 문제 : 모든 point의 쌍의 거리 중 최소의 거리를 찾는 문제
⑤ Strassens's 알고리즘 : 두 행렬을 곱하는 효과적인 알고리즘
⑥ Cooley-Tukey Fast Fourier Transform(FFT) 알고리즘 : 가장 일반적인 FFT 알고리즘

분할정복의 핵심 진행방식은 다음과 같다.

① 분할 : 동일한 타입의 하위 문제로 큰 문제를 분할한다.
② 정복 : 재귀적으로 하위 문제들을 해결한다.
③ 병합 : 적절히 해결된 결과를 사용해 큰 문제를 해결한다.

그렇다면 분할 정복과 동적 프로그래밍은 같은 걸까?

분할 정복과 동적 프로그래밍은 주어진 문제를 작게 쪼개서 하위 문제로 해결하고 연계적으로 큰 문제를 해결한다는 점은 같다.
차이점은, 분할 정복은 분할된 하위 문제가 동일하게 중복이 일어나지 않는 경우에 쓰며, 동일한 중복이 일어나면 동적 프로그래밍을 쓴다는 것이다.

예를 들어, 병합 정렬은 앞에서 구한 값을 중복해서 구할 필요는 없다. 그에 반해 피보나치 수열은 앞서 구한 값이 반복해서 사용된다.
그래서 병합 정렬은 분할 정복으로, 피보나치 수열은 동적 프로그래밍으로 해결이 가능한 것이다.

또한, 분할정복은 Top-Down만 가능하지만 동적 프로그래밍은 Bottom-up도 가능하다.

백준 2630번 - 색종이 만들기

문제 링크 - https://www.acmicpc.net/problem/2630
이 문제는 분할정복 알고리즘이 처음이라 조금 어렵게 풀었다.
작은 문제로 나누어 재귀함수를 호출해야 하는데, 적절한 변수를 사용하는 방법이 처음에는 감이 안 잡혔다.
또한 입력을 받는 방법도 시간을 효율적으로 사용하기 위해 input()이 아닌, sys.stdin.readline()를 썼다.

import sys
N = int(input())
arr = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

count_white = 0
count_blue = 0

def check_square(x, y, n):
    global count_blue, count_white
    color = arr[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if arr[i][j] != color:
                check_square(x, y, n//2)
                check_square(x+n//2, y, n//2)
                check_square(x, y+n//2, n//2)
                check_square(x+n//2, y+n//2, n//2)
                return
    if color == 1:
        count_blue += 1
    else:
        count_white += 1


check_square(0, 0, N)
print(count_white)
print(count_blue)

백준 1992번 - 쿼드트리

문제 링크 - https://www.acmicpc.net/problem/1992
이 문제는 위에 색종이 문제와 유사하며, 괄호를 어디서 출력해주어야 할지를 고민하며 풀었다.
예상치 못하게 문자열을 입력받는 방법으로 시스템 함수를 쓰다보니 개행문자가 포함되어서
처리하여 원하는 형식의 이차원 배열을 만드는 부분이 시간이 좀 걸린 것 같다.

import sys

N = int(input())
arr = []
for n in range(N):
    row = list(sys.stdin.readline().strip())
    arr.append(row)

def quad_tree(x, y, n):
    value = arr[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if arr[i][j] != value:
                value = '-1'
                break
    
    if value == '-1':
        print('(', end = '')
        quad_tree(x, y, n//2)
        quad_tree(x, y+n//2, n//2)
        quad_tree(x+n//2, y, n//2)
        quad_tree(x+n//2, y+n//2, n//2)
        print(')', end = '')

    elif value == '0':
        print(0, end='')
    elif value == '1':
        print(1, end='')

quad_tree(0, 0, N)