분할 정복

Computer Science Apr 14, 2025

분할 정복이란?

프로그래밍을 하다 보면 분할 정복이라는 말을 종종 듣는다. 분할 정복... 무언가 멋있지 않은가?

분할 정복은 무엇일까? 간단하다. 큰 문제를 쪼개어 구한 뒤 합치는 것이다. 분할 정복을 이용한 알고리즘은 대표적으로 분할 정복을 이용한 거듭제곱이나 피보나치 수열, 퀵정렬 등이 있다. 어디선가 한 번쯤 들어본 것들 일 것이다. (아닌가...)

이번 글에서는 분할 정복의 원리와 구현, 그리고 다양한 응용 알고리즘을 배우자.

분할 정복의 원리

분할 정복의 원리는 아주 간단하다.

여러 번 계산해야 하는 것을 한 번 계산 후 저장해서 '재활용'하기

대표적인 분할 정복 알고리즘인 거듭제곱을 예시로 들어보자.

\(2^{100} \) 을 계산하기 위해서는 크게 두 가지 방법이 떠오를 것이다.

2를 100 번 곱하기: 단순하지만 직관적으로 쉽게 떠오르는 방법이다. 그러나 이 경우 지수가 1억, 100억...이 되면 시간 초과가 날 것 이다.
\(2^{50}\)을 구하고 제곱하기: 100 번 해야 할 계산을 쪼개어 재활용하였다.

2번 방법이 분할 정복의 원리이다. 여러 번 계산(100번)을 쪼개어 작게 만든다. 이를 한 번 계산하고(\(2^{50}\)계산) 재활용하여 더 빠르게 답을 구한다.

수열을 절반 씩 나누어 정렬하는 것이 퀵정렬의 기본 원리다. 피보나치 수열도 행렬 계산을 쪼개어 재활용한다.

분할 정복의 구현

파이썬으로 분할 정복을 구현해보자.

def cal(x,y) :
  return x*y
def f(n,x):
  if n==1:
    return x
  else:
    tmp=f (n//2,x)
    if n%2==0:
      return cal (tmp, tmp)
    else:
      return cal (tmp, cal (tmp, x))
print(f(10,2))

분할 정복을 이용한 거듭 제곱의 계산

위 코드는 아주 전형적인 분할 정복 알고리즘이다. tmp에 \(x^{n \over 2}\)를 저장, 재활용해서 O(log n)의 시간복잡도를 가지게 했다. 만약 이를 일일이 계산하려고 했다면 O(n)이었으므로 아주 효율적인 알고리즘임을 알 수 있다.

추가적인 정보: 사실 파이썬에 기본으로 제공하는 거듭 제곱 계산 (n**m)도 분할 정복을 이용한다. 그래도... 다른 문제를 푸려면 알아두는 게....

피보나치 수열

이 분할 정복을 이용한 대표적인 알고리즘, 피보나치 수열을 구하는 것이다. 일반적인 알고리즘을 먼저 보자.

n=int(input())
ans=[1,1]
for i in range(3,n+1):
  ans.append(ans[-1]+ans[- 2])
print(ans[-1])

기본적인 피보나치 수열 구하기

위 코드는 비효율적이다. DP를 이용한 알고리즘으로(DP는 다이나믹 알고리즘이다. 사실 이 녀석도 분할 정복과 유사한 면이 있다.) O(n)의 시간복잡도를 가진다. 따라서 만약 1억 번째 피보나치 수를 구하라고 한다면 C언어 기준 대략 1초가 걸리고 파이썬은 그보다 더 걸린다.

더 효율적인 코드가 있다. 분할 정복을 이용할 것이다. 그러나 이를 이해하기 위해서는 우선 행렬을 알아야 한다. 잠시 알아보고 돌아오자.

행렬

이 글에서는 행렬에 대한 자세한 내용을 다루지 않겠다. 딱 피보나치 수열에 필요한 정도만 설명한다.

다음 행렬을 생각하자.

\[\begin{pmatrix} F_{n} \\ F_{n-1} \end{pmatrix}\]

여기서 \(F_{n}\)은 n번째 피보나치 수이다. 그런 다음과 같은 식을 얻는다. 점화식이다.

\[\begin{pmatrix} F_{n} \\ F_{n-1} \end{pmatrix}=\begin{pmatrix} 1&1 \\ 1&0\end{pmatrix}\begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix}\]

행렬의 곱셉을 생각하면 이주 당연한 결과다. 이를 이용하면 다음과 같이 나타낼 수 있다.

\[\begin{pmatrix} F_{n} \\ F_{n-1} \end{pmatrix}={\begin{pmatrix} 1&1 \\ 1&0\end{pmatrix}}^{n-1}\begin{pmatrix} F_{1} \\ F_{0} \end{pmatrix}\]

단, \(F_{1}=1,\ F_{0}=0\)이라고 하자.

이 식을 이용할 것이다.

분할 정복을 이용한 피보나치 수열 구하기

\[\begin{pmatrix} F_{n} \\ F_{n-1} \end{pmatrix}={\begin{pmatrix} 1&1 \\ 1&0\end{pmatrix}}^{n-1}\begin{pmatrix} F_{1} \\ F_{0} \end{pmatrix}\]

이 식에서 분할 정복을 이용할 부분이 보이는 가? (안보임 말고...) 그렇다. \({\begin{pmatrix} 1&1 \\ 1&0\end{pmatrix}}^{n-1}\)을 분할 정복을 이용해 계산한다.

n=int(input())
def cal(a,b) :
  c=[[0,0],[0,0]]
  for i in range(2): for j in range(2):
    s=0
    for k in range(2):
      s+=a[i][k]*b[k][j]
    c[i][j]=s
  return c
def f(x):
  if x==1:
    return [[1,1], [1,0]]
  else:
    tmp=f(x//2)
    if x%2==0:
      return cal(tmp, tmp)
    else:
      return cal(tmp, cal(tmp, [[1,1], [1,0]]))
if n==1:
  print(1)
  exit()
if n==2:
  print(1)
  exit()
m=f(n-2)
ans=m[0][0]+m[0][1]
print(ans)

분할 정복을 이용한 피보나치 수열 구하기

짠!!!

여기서 n이 1, 2 일 땐 예외 처리 해주는 것을 잊지 말자.

(사실 위에서 말한 2의 거듭 제곱 계산과 달라진 것은 cal 함수 밖에 없다.)