목차
지퍼를 열면 한 줄이 두 줄로 갈라진다. 채우면 두 줄이 다시 한 줄이 된다. 채울 때 슬라이더가 하는 일을 보면 분할 정복이 왜 이득인지가 보인다.
슬라이더는 맨 앞만 본다
지퍼를 채울 때 슬라이더는 양쪽 맨 앞 이빨만 본다. 뒤에 이빨이 몇 개 남았는지는 보지 않는다. 양쪽이 이미 줄을 맞춰 나 있기 때문에 맨 앞만 보고 물려도 결과가 흐트러지지 않는다.
정렬에서 반씩 나눠 합치는 방식이 정확히 이 동작이다. 두 뭉치가 각각 이미 정렬되어 있으면, 더 작은 쪽의 맨 앞장이 전체를 통틀어 가장 작다. 양쪽 맨 앞장만 비교하고 하나를 빼서 놓는다. 그걸 다 없어질 때까지 반복하면 합쳐진다.
그래서 두 뭉치를 합치는 데 드는 일은 카드 수만큼이다. 100장과 100장을 합치는 데 200번이면 된다. 서로 다 비교하는 게 아니다.
세 단계뿐이다
분할 정복이라는 이름은 거창한데 하는 일은 셋이다.
- 나눈다. 문제를 같은 모양의 더 작은 문제 둘로 가른다.
- 각각 푼다. 자기를 다시 부르면 된다. 더 작아졌으니 언젠가 안 쪼개지는 크기가 된다.
- 합친다. 작은 답 둘을 큰 답 하나로 만든다.
앞의 둘은 재귀 그 자체다. 분할 정복이 재귀와 다른 점은 마지막 하나뿐이고, 그 하나에 전부가 걸려 있다.
이득은 나누기가 아니라 합치기에서 나온다
여기가 이 글에서 가장 중요한 자리다. 쪼갠다고 저절로 빨라지지 않는다.
카드 200장을 한 장씩 제자리에 끼워 정리하면 대략 200 × 200이다. 100장씩 두 뭉치로 나눠 각각 정리하면 100 × 100이 둘, 그러니까 절반으로 줄었다. 그런데 여기까지는 아직 답이 아니다. 두 뭉치를 하나로 합쳐야 한다.
이때 합치는 값이 얼마냐가 전부를 정한다.
- 합치는 데 200번이면 이득이다. 20,000 + 200이 40,000보다 훨씬 작다.
- 합치는 데 다시 200 × 200이 든다면 나눈 의미가 없다. 아낀 것을 합치면서 도로 낸다.
지퍼가 값을 하는 이유가 여기 있다. 양쪽이 정돈되어 있다는 성질 덕분에 합치기가 싸다. 그 성질이 없으면 분할 정복은 아무것도 벌지 못한다.
여기서 지퍼 비유가 깨진다. 지퍼는 이빨이 번갈아 물리고 짝이 이미 정해져 있다. 병합은 그렇지 않다. 한쪽에서 연달아 다섯 개가 나올 수도 있고, 어느 쪽을 뺄지는 매번 비교해서 정한다. 지퍼에서 가져올 것은 물리는 순서가 아니라 **“슬라이더가 맨 앞만 본다”**는 것 하나다.
n log n이 어디서 나오나
이제 n log n을 직접 세어볼 수 있다.
합치는 층이 3개, 층마다 8장 → 모두 24번. 같은 8장을 한 장씩 끼워 정리하면 64번이다.
칸은 잘게 갈라지는데 줄 길이는 어느 층이든 같다. 그래서 값은 층의 개수 × 줄 길이가 된다.
깊이를 센다. 반씩 나누니 100만 개가 50만, 25만으로 줄고 스무 번쯤이면 하나가 된다. 깊이는 log n이다.
한 층에서 하는 일을 센다. 어느 층이든 그 층의 조각을 전부 합쳐야 한다. 조각이 여러 개로 갈렸어도 합쳐서 다루는 원소 수는 언제나 n개다. 위층에서 100만 개짜리 둘을 합치든, 아래층에서 두 개짜리를 50만 번 합치든, 층 전체로는 100만 번이다.
그래서 곱한다. 층이 log n개이고 층마다 n이니 n log n이다.
이 세는 방식이 잡히면 다른 분할 정복도 같은 방법으로 잴 수 있다. 깊이가 몇이고, 한 층에서 무엇을 하는가. 두 질문이면 된다.
반만 보면 log n, 다 보면 n log n
여기서 자주 어긋나는 자리가 하나 있다. 이진탐색도 반씩 나누는데 왜 log n인가.
층수는 똑같다. 갈리는 건 나눈 다음 한쪽을 버리느냐뿐이고, 그 하나가 log n과 n log n을 가른다.
차이는 나눈 다음에 있다. 이진탐색은 한쪽만 보고 나머지는 버린다. 그래서 층마다 하는 일이 한 번뿐이고, 총합이 깊이와 같아진다.
병합정렬은 양쪽을 다 본다. 버리는 게 없으니 층마다 전체를 훑고, 그래서 깊이에 n이 곱해진다.
같은 “반씩 나누기”인데 버리느냐 다 쓰느냐로 결과가 갈린다. 어떤 방법을 만났을 때 log n인지 n log n인지 헷갈리면 이걸 물으면 된다. 나눈 다음 한쪽을 버리나.
나눠도 소용없는 경우
분할 정복이 안 맞는 자리도 분명하다. 합치기가 안 싸지는 문제다.
배열에서 가장 큰 값을 찾는 일을 분할 정복으로 짤 수 있다. 반씩 나눠 각각의 최대를 구하고 둘 중 큰 것을 고르면 된다. 합치기가 비교 한 번이라 아주 싸다. 그런데 결국 n이다. 그냥 한 바퀴 훑어도 n이다.
이럴 때 분할 정복은 손해다. 재귀 호출 비용만 더 낸다. 이득이 나려면 조건이 하나 더 필요하다. 안 나누고 풀면 n보다 비싸야 한다. 정렬이 그랬다. 안 나누면 n²인데 나누면 n log n이다.
⚠️ 그래도 최대값 문제에서 분할 정복이 쓸모 있는 경우가 있다. 여러 대에 나눠 맡길 때다. 계산량은 같아도 각자가 자기 몫만 보면 되기 때문이다. 계산량을 줄이는 이득과 나눠 맡기기 좋은 이득은 다른 것이고, 뒤엣것은 규모가 커진 뒤에야 값을 한다.
실무에서: 나누고 합치는 건 이미 도처에 있다
분할 정복을 직접 짜는 일은 드물지만, 이 모양은 이름을 바꿔가며 실무 곳곳에 있다.
- 데이터를 여러 대에 나눠 담는 일 - 각 조각에서 따로 조회하고 결과를 합친다. 여기서도 어려운 건 나누기가 아니라 합치기다. 정렬이나 집계가 걸리면 각 조각의 답을 모아 다시 계산해야 해서, 합치기 비용이 샤딩의 이득을 갉아먹는다.
- 큰 데이터를 나눠 처리하고 모으는 배치 - 조각마다 세고 마지막에 더한다. 개수를 세는 일은 합치기가 덧셈이라 잘 나뉘고, 중간값을 구하는 일은 합치기가 어려워서 잘 안 나뉜다. 무엇을 계산하느냐가 나눌 수 있는지를 정한다.
- 파일을 조각내 해시를 만들고 그 해시들을 다시 해시하는 구조 - 어느 조각이 달라졌는지를 전부 비교하지 않고 위에서부터 내려가며 찾는다.
셋 다 같은 질문 위에 서 있다. 나눈 답을 합치는 게 처음부터 다시 하는 것보다 싼가. 싸면 나누고, 안 싸면 나눠봐야 손해다.
정리
- 분할 정복은 셋이다. 나눈다, 각각 푼다, 합친다. 재귀와 다른 건 마지막 하나뿐이다.
- 이득의 출처는 나누기가 아니라 합치기가 싸다는 것이다. 합치기가 비싸면 아무것도 못 번다.
- 합치기가 싼 이유는 양쪽이 이미 정돈되어 있어 맨 앞만 보면 되기 때문이다.
n log n은 **깊이(log n) × 층마다 하는 일(n)**이다. 이 두 질문으로 다른 방법도 잴 수 있다.- 나눈 뒤 한쪽을 버리면
log n, 양쪽을 다 쓰면n log n이다. - 안 나누고 풀 때 이미
n이면 나눠도 이득이 없다. 실무에서 나눌지 말지는 합치기 비용이 정한다.
다음 글은 재귀가 조용히 망가지는 자리에서 시작한다. 같은 것을 몇 번이나 다시 계산하고 있었나.