어떻게 반으로 쪼개 정복하기

반으로 쪼갠다

앞에서 큰일은 작은 단계로 쪼갠다고 했다. 여기서는 한 걸음 더 나간다.
문제 덩어리를 반으로 쪼개고, 그 반을 또 반으로, 그것을 또 반으로 쪼갠다.
그러면 조각이 점점 작아져요.

반으로 쪼개기를 누를 때마다 덩어리가 반씩 갈라진다. 조각은 점점 작아진다.

쪼갤 때마다 다룰 양이 절반으로 준다.
큰 더미는 막막했지만 작은 조각 하나는 훨씬 만만하다.
사전에서 반씩 갈라 찾던 바로 그 느낌이에요.

조각은 겹치지 않는다

여기서 아주 중요한 점이 있다. 반으로 쪼갠 두 조각은 서로 겹치지 않는다.
왼쪽 더미와 오른쪽 더미는 같은 옷을 나눠 갖지 않으니, 한쪽에서 한 일을 다른 쪽이 또 할 필요가 없다.
둘은 완전히 따로예요.

두 조각을 하나씩 눌러 비추면 겹치는 부분이 하나도 없다. 서로 따로(독립)라서 각자 풀어도 부딪치지 않는다.

겹치지 않는다는 이 성질은 생각보다 중요하다.
조각이 겹치지 않으니 한쪽 답이 다른 쪽 답을 망치지 않는다.
겹치는 문제를 만나면 이야기가 달라지는데, 그건 또 다른 길이에요.

작은 조각을 푼다

계속 반으로 쪼개다 보면 더는 쪼갤 수 없는 아주 작은 조각이 나온다.
옷 한 장, 숫자 한 개 같은 것이다.
그 정도로 작으면 고민할 것도 없이 바로 풀려요.

가장 작은 조각(바닥)을 하나씩 누르면 바로 풀린다. 더 못 쪼갤 만큼 작으니 고민 없이 풀리고, 풀린 조각은 초록으로 바뀌어요.

큰 문제를 한 번에 풀려고 끙끙대지 않는다.
끝까지 쪼갠 다음 풀기 쉬운 작은 조각만 하나하나 푼다.
어려운 일 하나를 쉬운 일 여럿으로 바꿔 버린 거예요.

합쳐 올린다

작은 답들이 생겼으니 이제 거꾸로 올라간다.
작은 답 둘을 합쳐 조금 큰 답을 만들고, 그 둘을 또 합쳐 더 큰 답을 만든다.
쪼갠 만큼 합치다 보면 맨 위에 전체 답이 서요.

합쳐 올리기를 누를 때마다 풀린 조각이 둘씩 하나로 합쳐진다. 맨 위에서 전체 답이 완성돼요.

쪼갤 때는 아래로, 합칠 때는 위로 간다.
조각이 겹치지 않았으니 합칠 때도 깔끔하다. 왼쪽 답과 오른쪽 답을 한데 모으기만 하면 된다.
이것이 반으로 쪼개 정복하기, 곧 분할 정복이에요.

쪼개고, 풀고, 합치고

한 줄로 모으면 이렇다. 반으로 쪼개고, 겹치지 않는 조각을 각각 풀고, 다시 합쳐 올린다.
카드를 반씩 나눠 정렬하던 방법은 이 틀을 그대로 따르고, 사전에서 반씩 찾던 방법은 찾는 값이 없는 쪽을 아예 버려서 한쪽만 풀면 되는 경우다.
큰 것도 쪼개면 작아져요.

세 걸음을 차례로 눌러 한 바퀴 따라간다. 반으로 쪼개기 → 작은 조각 풀기 → 합쳐 올리기. 조각이 겹치지 않는다는 점이 핵심이에요.

여기서는 조각들이 서로 깔끔하게 떨어져 있어서 한 번 푼 조각을 다시 풀 일이 없었다.
그런데 조각들이 서로 겹쳐서 같은 것을 자꾸 다시 풀어야 한다면 어떻게 될까?
다음 레슨에서는 쪼개기를 스스로 되풀이하는 재귀를 먼저 보고, 그 갈림길은 바로 그다음에 만나요.