문제 분해

본문

본문

바둑판처럼 생긴 동네에서 학교는 왼쪽 위 모퉁이, 집은 오른쪽 아래 모퉁이에 있다. 가로로 10블록, 세로로 10블록이다. 돌아가지 않고 오른쪽과 아래로만 걷는다면 집까지 가는 길은 몇 가지일까? 길을 하나하나 그려 세면 끝이 없다. 그런데 '바로 앞 모퉁이까지 오는 길의 수를 이미 안다면?'이라고 물으면 길이 보인다. 어려운 문제를 작은 문제로 나누어 푸는 방법을 알아보자.

가로 블록 수 세로 블록 수

그림 1. 왼쪽 위에서 출발해 각 모퉁이(칸)까지 오른쪽과 아래로만 가는 길의 수. 각 칸의 수는 위 칸과 왼쪽 칸의 수를 더한 값이다(주황이 집).

먼저 알아야 할 것재귀 구조(재귀 구조), 가지치기 탐색(가지치기 탐색), 조합(수학).

3.3.1부분 문제로 나누기

집에 도착하는 마지막 걸음은 바로 위 모퉁이에서 내려오거나, 바로 왼쪽 모퉁이에서 건너오는 두 가지뿐이다. 그래서 집까지 오는 길의 수는 위 모퉁이까지 오는 길의 수와 왼쪽 모퉁이까지 오는 길의 수의 합이다. 위 모퉁이와 왼쪽 모퉁이까지의 길의 수도 같은 방법으로 구할 수 있다. 이렇게 큰 문제의 답을 같은 모양의 더 작은 문제들의 답으로 나타내는 것이 문제 분해이다. 맨 윗줄과 맨 왼쪽 줄의 모퉁이는 한 줄로만 갈 수 있어 길이 한 가지씩이다. 이것이 더 나누지 않는 가장 작은 문제이다.

정리 3.3.1 격자 경로의 점화식

출발점에서 아래로 \(i\)칸, 오른쪽으로 \(j\)칸 떨어진 모퉁이까지의 길의 수를 \(P(i, j)\)라 하면 \[P(i, j) = P(i-1, j) + P(i, j-1),\qquad P(0, j) = P(i, 0) = 1\]이다. 이 값은 \(\dbinom{i+j}{i}\)와 같다. 작은 문제의 답을 표에 적으며 위에서 아래로 채우면 각 칸을 한 번씩만 계산한다.

그림 1에서 격자의 크기를 바꾸어 보자. 가로 4, 세로 3이면 표의 맨 끝 칸은 35이다. 각 칸의 수를 위 칸과 왼쪽 칸에서 더하기만 하면 되므로, 칸의 수만큼만 계산한다. 가로 10, 세로 10이면 끝 칸이 184756으로, 길을 하나하나 그려 세면 18만 번 넘게 그려야 하지만, 표는 121칸만 채우면 된다. 이 표를 채우는 방법은 파스칼의 삼각형을 만드는 방법과 같다.¹

3.3.2분해의 두 갈래

문제를 나누는 방식은 크게 두 가지로 이어진다. 부분 문제들이 서로 겹치지 않으면, 나누어 따로 풀고 그 답을 합치는 분할 정복이 알맞다. 리스트를 반으로 나누어 각각 정렬한 뒤 합치는 병합 정렬이 그렇다. 격자 경로처럼 같은 부분 문제가 여러 큰 문제에 거듭 쓰이면, 한 번 구한 답을 표에 적어 두고 다시 쓰는 동적 계획법이 알맞다. 그냥 재귀로 풀면 같은 모퉁이의 길의 수를 수없이 다시 계산하기 때문이다. 어느 쪽이든 '부분 문제가 무엇이고, 그 답으로 전체 답을 어떻게 만드는가'를 찾는 것이 출발점이다.

그림 2. 부분 문제가 겹치느냐가 분할 정복과 동적 계획법을 가른다.

3.3.3예제 풀이

예제 3.3.2

가로 3블록, 세로 2블록인 격자에서 표를 채워 집까지의 길의 수를 구하여라. 공사 중인 모퉁이(출발점에서 아래로 1칸, 오른쪽으로 1칸)를 지날 수 없다면 길은 몇 가지가 되는가?

맨 윗줄은 1, 1, 1, 1이다. 둘째 줄은 1, 2, 3, 4이고, 셋째 줄은 1, 3, 6, 10이다. 따라서 길은 10가지이며, \(\dbinom{5}{2} = 10\)과 같다.

공사 중인 모퉁이를 0으로 두고 다시 채우면, 둘째 줄은 1, 0, 1, 2이고, 셋째 줄은 1, 1, 2, 4이다. 따라서 길은 4가지로 준다. 조합 공식은 막힌 모퉁이가 있으면 바로 쓸 수 없지만, 표를 채우는 방법은 그 칸만 0으로 바꾸면 그대로 통한다. 즉 문제를 부분 문제로 나누어 두면 조건이 바뀌어도 쉽게 대응할 수 있다. 그래서 문제 분해는 공식을 모르는 문제를 푸는 일반적인 방법이 된다.

아래 탐구 카드에서 여러 문제의 부분 문제를 찾고, 그 답으로 전체 답을 만드는 식을 세워 보자.

파스칼의 삼각형은 파스칼보다 수백 년 앞서 중국의 양휘, 페르시아의 알카라지가 이미 알고 있었다. 각 수가 바로 위 두 수의 합이라는 규칙이 격자 경로의 점화식과 같다.

마무리

문제 분해는 큰 문제의 답을 같은 모양의 작은 문제들의 답으로 나타내는 일이며, 격자 경로에서는 각 모퉁이까지의 길의 수가 위와 왼쪽 모퉁이의 길의 수의 합이다. 부분 문제가 겹치지 않으면 분할 정복, 겹치면 표에 답을 적어 두는 동적 계획법으로 이어진다. 그래서 처음 질문의 10 × 10 동네에서 집까지 가는 길은 표 121칸을 채워 184756가지로 구할 수 있다.

탐구 1

원판 n개 문제를 원판 n−1개 문제로 바꿀 수 있을까?

문제 분해 · 부분 문제와 전체 문제의 관계 · 하노이 탑

원판 수 n = 3

옮긴 횟수 / 최소: 0
호출 스택 깊이: 0
관계: T(n) = 2T(n−1) + 1

호출 스택 (아래가 먼저 부른 것)

파이썬 코드

규칙: 한 번에 원판 하나만, 맨 위의 원판만 옮기고, 작은 원판 위에 큰 원판을 놓을 수 없다. 목표는 A의 원판을 모두 C로 옮기는 것이다. 기둥을 눌러 직접 풀어 볼 수도 있다.

질문원판 3개는 손으로 몇 번 해 보면 풀린다. 그런데 원판이 7개, 20개로 늘면 어떤 순서로 옮겨야 할지 막막한다. 원판 수가 몇 개이든 통하는 풀이를 어떻게 찾을 수 있을까?
복원재귀 함수는 자기 자신을 더 작은 입력으로 호출하고, 기저 사례에서 멈춘다. 함수를 부를 때마다 호출 스택에 새 칸이 쌓이고, 끝나면 빠진다.
설명가장 큰 원판에 주목한다. 이것을 A에서 C로 옮기려면 그 순간 나머지 n−1개가 모두 B에 있어야 한다. 그러면 전체 문제는 세 부분으로 분해된다. ① 원판 n−1개를 A에서 B로 옮기기, ② 가장 큰 원판을 A에서 C로 옮기기, ③ 원판 n−1개를 B에서 C로 옮기기. ①과 ③은 원판 수만 하나 적고 모양이 같은 부분 문제이다. 원판 1개는 그냥 옮기면 되는 기저 사례이다.
연결전체 문제와 부분 문제 사이의 관계를 식으로 쓰면 이동 횟수 T(n) = 2T(n−1) + 1, T(1) = 1이다. 이 관계를 따라가면 T(n) = 2ⁿ − 1이 되고, 이보다 적게 옮기는 방법은 없다. 분해할 때 찾아야 하는 것은 ① 부분 문제가 무엇인지, ② 부분 문제의 답으로 전체 답을 어떻게 만드는지, ③ 더 쪼개지 않는 가장 작은 경우가 무엇인지이다.
적용n = 3에서 먼저 기둥을 눌러 직접 풀어 보고, 처음부터를 누른 뒤 재귀 한 단계씩 따라가 보자. 가장 큰 원판(주황)이 움직이는 순간 호출 스택에는 무엇이 있는가? 그때 B에는 원판이 몇 개 있는가? n을 1씩 늘리며 최소 이동 횟수가 어떻게 변하는지 표로 적어 보자.
판단분해는 아무렇게나 나눈다고 되는 것이 아니다. "원판을 위에서부터 하나씩 옮긴다"처럼 나누면 부분 문제가 원래 문제와 같은 모양이 아니어서 재귀로 이어지지 않는다. 또 하노이 탑의 두 부분 문제는 기둥만 다를 뿐 같은 크기라서, 원판이 하나 늘 때마다 일이 두 배가 된다. 분해가 곧 빠른 풀이를 뜻하지는 않는다.

확인조건이 달라지면

원판 10개짜리 하노이 탑을 최소 횟수로 옮기려 한다. 원판 9개를 옮기는 최소 횟수가 511번이라는 것을 알 때, 원판 10개의 최소 횟수는?

읽기 2

큰 문제 속에서 같은 모양의 작은 문제를 어떻게 찾을까?

읽기 · 문제 분해 · 관계식과 기저 사례

"리스트에서 가장 큰 수 찾기"를 반복문 없이 풀 수 있을까? 문제를 "앞의 n−1개에서 가장 큰 수"와 "마지막 수" 둘로 나누면, 앞쪽은 원래 문제와 똑같은 모양이고 크기만 하나 작다.

1분해할 때 묻는 세 가지

부분 문제: 원래 문제와 같은 모양이면서 크기가 작은 문제는 무엇인가? 크기를 무엇으로 잴지(원소 수, 원판 수, 지수 n 등) 먼저 정한다.
관계: 부분 문제의 답을 알고 있다면, 그것으로 전체 문제의 답을 어떻게 만드는가? 이 관계를 식으로 적은 것이 점화식(관계식)이다.
기저 사례: 더 쪼개지 않고 바로 답을 아는 가장 작은 경우는 무엇인가? 크기가 매번 줄어들어 반드시 여기에 닿아야 한다.

def biggest(a):
          if len(a) == 1:                  # 기저 사례
              return a[0]
          rest = biggest(a[:-1])           # 부분 문제: 앞의 n-1개
          return max(rest, a[-1])          # 관계: 부분 답과 마지막 수 비교

2여러 문제의 분해

전체 문제	부분 문제	전체와 부분의 관계	기저 사례
1부터 n까지의 합 S(n)	S(n−1)	S(n) = S(n−1) + n	S(1) = 1
리스트의 최댓값	앞의 n−1개의 최댓값	max(부분 답, 마지막 원소)	원소 1개
하노이 탑 (원판 n개)	원판 n−1개 옮기기 (두 번)	T(n) = 2T(n−1) + 1	원판 1개: 한 번 옮김
거듭제곱 aⁿ	a의 (n // 2)제곱	짝수면 (부분 답)², 홀수면 a × (부분 답)²	a⁰ = 1
리스트 정렬	앞 절반 정렬, 뒤 절반 정렬	정렬된 두 리스트를 합병	원소 0개나 1개
계단을 1칸 또는 2칸씩 올라 n칸에 가는 방법 수 W(n)	W(n−1), W(n−2)	W(n) = W(n−1) + W(n−2)	W(1) = 1, W(2) = 2

표의 마지막 줄은 마지막 걸음이 1칸인지 2칸인지로 경우를 나눈 것이다. 마지막이 1칸이면 그 전까지 n−1칸을 오르는 방법 수, 2칸이면 n−2칸을 오르는 방법 수만큼 있다. 관계는 "마지막 한 걸음"이나 "가장 큰 원판"처럼 마지막 결정 하나에 주목할 때 잘 보인다.

3관계의 세 가지 모양

세 모양은 이후 알고리즘 설계의 출발점이 된다. ②처럼 크기가 반씩 줄면 몇 번만 쪼개도 기저 사례에 닿는다(분할 정복). ③처럼 같은 부분 문제(n−2가 두 번, 색칠한 n−3이 두 번)가 여러 번 나타나면 한 번 구한 답을 저장해 다시 쓰는 방법(동적 계획법)이 필요해진다.

4부분 문제의 답을 믿기

재귀 코드를 읽을 때 호출을 끝까지 따라가면 금방 길을 잃는다. 대신 "biggest(a[:-1])는 앞의 n−1개의 최댓값을 정확히 돌려준다"고 믿고, 그 답으로 전체 답을 맞게 만드는지만 확인한다. 이것은 수학적 귀납법과 같은 생각이다. 기저 사례가 맞고, n−1에서 맞으면 n에서도 맞음을 보이면 모든 n에서 맞다.

판단부분 문제가 원래 문제보다 작아지지 않으면(예를 들어 biggest(a)가 다시 biggest(a)를 부르면) 재귀는 끝나지 않고, 파이썬은 RecursionError를 낸다. 또 같은 모양이라고 해서 아무렇게나 나눈 것이 좋은 분해는 아니다. 위의 최댓값 코드는 맞지만 a[:-1]이 리스트를 매번 복사하고 재귀 깊이가 n이라, 원소가 1000개 가까이 되면 파이썬 기본 재귀 한도(보통 1000)에 걸린다. 분해는 정확성을 생각하는 도구이고, 효율은 따로 따져야 한다.

확인조건이 달라지면

계단을 한 번에 1칸, 2칸, 3칸 중 하나로 오를 수 있게 바뀌었다. n칸에 오르는 방법 수 W(n)의 관계로 옳은 것은?