분할 정복(Divide and Conquer)

분할 정복은 재귀로 구현하는 것이 일반적

Divide

• 큰 문제를 작은 문제로 분할

• 기저 사례(base case)를 잘 설정하여 일정 기준 이상 분할되지 않도록 해야 함

Conquer

• 작은 문제의 답을 모아, 큰 문제의 답을 구함

예시 - 피보나치 수열

def fibo(N):
	if N <= 2:
    	return 1
	return fibo(N - 1) + fibo(N - 2)

N이 2 이하일 때, 1 반환 → 기저 사례(base case)
F(1) 값을 3번, F(2) 값을 5번 계산하여, F(6)을 구함
→ 큰 문제를 작은 문제로 분할 + 작은 문제들의 답으로 큰 문제의 답을 구함

예시 - Z

크기가 $2^n\times 2^n$인 2차원 배열이 존재, $n$의 값이 주어질 때, $r$행 $c$열을 몇 번째로 방문하는지 알고 싶다.

import sys
result = 0
def sol(n, x, y):
	global result
    if x == r and y == c:
    	print(int(result))
        return
	if not (x <= r < x + n and y <= c < y + n):
    	result += n * n
        return
	sol(n / 2, x, y)
	sol(n / 2, x, y + n / 2)
	sol(n / 2, x + n / 2, y)
	sol(n / 2, x + n / x, y + n / 2)
    
n, r, c = map(int, sys.stdin.readline().split(' '))
sol(1 << n, 0, 0)

pseudo code

전역 변수 result를 0으로 초기화

함수 $sol(n, x, y)$를 정의:
만약 $x$가 $r$이고 $y$가 $c$인 경우:
 result를 정수로 변환하여 출력 및 return
 만약 $(x, y)$에서 시작해서 크기가 $n$인 사각형이 $(r, c)$를 포함하지 않는 경우:
   result에 $n \times n$ 을 더하고 return
 4개의 재귀 호출을 사용하여 사분면으로 나눔:
 $sol(\frac{n}{2}, x, y)$를 호출 (4사분면)
 $sol (\frac{n}{2}, x, y + \frac{n}{2})$를 호출 (1사분면)
 $sol (\frac{n}{2}, x + \frac{n}{2}, y)$를 호출 (3사분면)
 $sol (\frac{n}{2}, x + \frac{n}{2}, y + \frac{n}{2})$를 호출 (2사분면)

사용자로부터 $n, r, c$ 를 입력 받음

$sol(2^n, 0, 0)$ 호출

백트래킹(backtracking)

• 답이 될 수 없는 경우는 탐색 대상에서 제외하여 효율적으로 답을 구하는 알고리즘

• 가지치기(pruning)를 통해 연산량을 유의미하게 줄여줌

• 가지치기를 사용하기 위해서는 현재 상태에서 도달할 수 있는 상태가 모두 답이 될 수 없음을 보여야 함

• 정확한 시간 복잡도를 구하기 어려움

예시 - 스도쿠(Sudoku)

가로, 세로 $3 \times 3$ 모두에, 1에서 9까지의 숫자를 중복되지 않게 한 번씩 사용해야 함. 스도쿠를 하다 보면, 명확한 근거 없이 일단 대입해봐야 하는 분기점이 존재. 대입해 보고 현재 상태에서 스도쿠를 완성할 수 없다면, 분기점으로 다시 돌아옴 → 백트래킹

예시 - Nqueen

$N \times N$ 크기의 체스판에 $N$개의 퀸을 서로 공격하지 못하게 놓아보자. 단, 퀸은 같은 행, 열, 대각선 위에 있는 말을 공격할 수 있다.

분할 정복과 백트래킹의 차이

공통점: 주로 재귀적인 방식으로 해결

차이점

• 분할 정복은 하위 문제를 해결하고, 결과를 결합하여 문제 해결

• 백트래킹은 문제 해결을 위해 모든 가능한 선택을 시도한 후, 가능성이 없다고 판단되면 이전 단계로 되돌아가거나 이전 결정을 변경