알고리즘 문제 해결 전략 - 사탕 나눠주기 문제

Intro

알고리즘 문제 해결 전략 책을 읽다가, 흥미로운 문제가 있어서 보충설명을 추가하여 정리하였다.
문제는 아래 링크에서 발췌하였다. (정오표의 틀린 내용도 보완하여 발췌하였다)
http://book.algospot.com/candy.html

사탕 나눠주기 문제

예제 문제를 하나 풀면서 점진적인 개선을 어떻게 적용할 수 있나 살펴봅시다. N(N≤30)개의 사탕을 세 명의 어린이에게 가능한 공평하게 나눠 주려고 합니다. 공평함의 기준은 받는 사탕의 총 무게가 가장 무거운 어린이와 가장 가벼운 어린이 간의 차이로 합시다. 사탕의 무게는 모두 20 이하의 정수입니다. 가능한 최소 차이는 얼마일까요?

이 문제를 푸는 가장 단순한 방법은 사탕을 나눠 주는 모든 방법을 하나씩 만들어 보는 것입니다. 각 사탕마다 셋 중 어느 어린이에게 줄 지를 결정한다고 하면 3^N, 즉 최대 205조 개의 방법을 만들어 보게 됩니다. 이는 죽기 전에 다 세어볼 수 있을까 엄두가 나지 않는 큰 수이지만, 사실 이 때 우리는 엄청나게 많은 수를 중복으로 세고 있습니다. 실제로 받은 사탕들이 서로 다르더라도 그 무게가 같다면 이 문제의 답은 같다는 점을 무시했기 때문입니다.

이 아이디어를 이용해 모든 방법을 만들어 보는 완전 탐색(6장) 대신 각 어린이가 가진 사탕의 총량을 상태 공간으로 하는 너비 우선 탐색(29장)으로 문제를 풀 수 있습니다. 이 때 각 상태는 세 어린이가 가진 사탕의 양을 표현하는 세 개의 정수입니다. 우리는 어떤 어린이에게도 사탕이 없음을 나타내는 (0, 0, 0)에서 시작해, 사탕을 하나 줄 때마다 그 어린이가 가진 사탕의 양을 늘립니다. 이렇게 하면 실제로 가진 사탕들이 다르더라도 그 무게가 같은 경우 하나의 상태로 취급해, 중복을 제거할 수 있습니다. 이 상태 공간의 크기는 얼마일까요? 사탕의 최대 무게는 20이므로, 각 어린이가 가진 사탕의 양은 0에서 20×N 사이입니다. 따라서 각 상태에 대해 방문 여부를 저장하려면 크기가 (20×N+1)3≤601^3(대략 2억)인 배열을 잡아야 합니다.

2억은 대개 시간 제한 안에 탐색할 수 있는 크기입니다만, 이 문제의 답이 최대 얼마인지 생각해 보면 이 방법을 더 최적화할 수 있습니다. 사탕을 가장 많이 받은 어린이와 가장 적게 받은 어린이의 차이가 20 이상이었다고 가정해 봅시다. 사탕의 최대 무게는 20이므로, 이때 사탕을 가장 많이 받은 어린이가 가장 적게 받은 어린이에게 사탕을 하나 준다면 이 둘이 가진 사탕의 양의 차이는 항상 감소합니다. 이렇게 하면 항상 원래보다 더 공평한 답을 얻을 수 있기 때문에, 차이가 20 이상인 경우는 절대로 최적의 답이 될 수 없다는 것을 알 수 있지요. 따라서 넉넉잡아도 사탕을 가장 많이 받은 어린이가 (20×N)/3+20 넘게 사탕을 받는 경우는 무시해도 됩니다. 그러면 실제로 할당해야 하는 배열의 크기는 (20×N^3+20)^3≤220^3(대략 1000만)으로 줄어듭니다.

이 정도면 충분히 문제를 풀 수 있을 것 같지만, 문제를 푸는 더 빠른 방법이 있습니다. 세 어린이 중 누가 가장 사탕을 적게 받고, 누가 가장 많이 받는지는 중요하지 않기 때문입니다. 세 어린이의 사탕의 총량이 (180, 190, 200)이건 (200, 190, 180)이건 우리의 답은 변하지 않지요. 따라서 세 어린이의 사탕의 총량이 항상 오름차순으로 정렬되어 있는 경우만을 탐색하도록 합시다. 서로 다른 세 수를 여섯 가지의 방법으로 나열할 수 있으므로, 이렇게 하면 경우의 수는 다시 대략 1/6으로 줄어듭니다. 결과적으로 대략 200만 개 이하의 경우의 수만을 탐색해 문제를 해결할 수 있지요. 이 과정에서 천재만이 떠올릴 수 있는 번뜩이는 영감은 필요없었지만, 처음에 생각했던 방법에 비해 검사해야 할 상태의 수가 1억분의 1로 줄어들었음을 알 수 있습니다.

보충설명

1

예제 문제를 하나 풀면서 점진적인 개선을 어떻게 적용할 수 있나 살펴봅시다. N(N≤30)개의 사탕을 세 명의 어린이에게 가능한 공평하게 나눠 주려고 합니다. 공평함의 기준은 받는 사탕의 총 무게가 가장 무거운 어린이와 가장 가벼운 어린이 간의 차이로 합시다. 사탕의 무게는 모두 20 이하의 정수입니다. 가능한 최소 차이는 얼마일까요?

문제는 다음과 같다.
최대 30개의 사탕을 3명의 어린이에게 나누어주려고 한다.
사탕의 무게는 1~20의 정수이다.
받은 사탕 무게의 합이 가장 큰 어린이와, 가장 가벼운 어린이의 무게 차는 최소 얼마일까?

2

이 문제를 푸는 가장 단순한 방법은 사탕을 나눠 주는 모든 방법을 하나씩 만들어 보는 것입니다. 각 사탕마다 셋 중 어느 어린이에게 줄 지를 결정한다고 하면 3^N, 즉 최대 205조 개의 방법을 만들어 보게 됩니다. 이는 죽기 전에 다 세어볼 수 있을까 엄두가 나지 않는 큰 수이지만, 사실 이 때 우리는 엄청나게 많은 수를 중복으로 세고 있습니다. 실제로 받은 사탕들이 서로 다르더라도 그 무게가 같다면 이 문제의 답은 같다는 점을 무시했기 때문입니다.

N개의 사탕을 3명의 어린이에게 나누어주는 경우의 수는 3^N개이다 (중복순열)
N=30일 경우 경우의 수는 약 205조 개가 된다
여기서 간과한 점은 각 어린이가 어떤 사탕들을 받았느냐가 아닌, 각 어린이가 받은 사탕 무게의 합이 중요하다는 점이다
받은 사탕의 개수나 각 사탕의 무게는 별도로 카운팅할 필요 없다

3

이 아이디어를 이용해 모든 방법을 만들어 보는 완전 탐색(6장) 대신 각 어린이가 가진 사탕의 총량을 상태 공간으로 하는 너비 우선 탐색(29장)으로 문제를 풀 수 있습니다. 이 때 각 상태는 세 어린이가 가진 사탕의 양을 표현하는 세 개의 정수입니다. 우리는 어떤 어린이에게도 사탕이 없음을 나타내는 (0, 0, 0)에서 시작해, 사탕을 하나 줄 때마다 그 어린이가 가진 사탕의 양을 늘립니다. 이렇게 하면 실제로 가진 사탕들이 다르더라도 그 무게가 같은 경우 하나의 상태로 취급해, 중복을 제거할 수 있습니다. 이 상태 공간의 크기는 얼마일까요? 사탕의 최대 무게는 20이므로, 각 어린이가 가진 사탕의 양은 0에서 20×N 사이입니다. 따라서 각 상태에 대해 방문 여부를 저장하려면 크기가 (20×N+1)3≤601^3(대략 2억)인 배열을 잡아야 합니다.

30개의 사탕을 3명의 어린이에게 나눠주는 방법이 아닌, 3명의 어린이가 받은 사탕 무게의 합의 경우의 수를 카운팅할 것이다
각 어린이가 가진 사탕 무게의 합이 될 수 있는 범위는, 0 ~ (20xN)이다 (20xN인 경우는 무게가 20인 모든 사탕을 다 받았을 경우)
즉, 20xN+1개의 경우의 수이다
어린이가 3명이므로, (20xN+1)^3개의 경우의 수가 존재하고, 최대 601^3 (약 2억)개가 될 수 있다
205조 개에서 2억 개로 경우의 수를 줄인 것은 굉장히 큰 차이라고 할 수 있겠다.
연산시간 관점에서나, 메모리 사용 관점에서나 모두.

4

2억은 대개 시간 제한 안에 탐색할 수 있는 크기입니다만, 이 문제의 답이 최대 얼마인지 생각해 보면 이 방법을 더 최적화할 수 있습니다. 사탕을 가장 많이 받은 어린이와 가장 적게 받은 어린이의 차이가 20 이상이었다고 가정해 봅시다. 사탕의 최대 무게는 20이므로, 이때 사탕을 가장 많이 받은 어린이가 가장 적게 받은 어린이에게 사탕을 하나 준다면 이 둘이 가진 사탕의 양의 차이는 항상 감소합니다. 이렇게 하면 항상 원래보다 더 공평한 답을 얻을 수 있기 때문에, 차이가 20 이상인 경우는 절대로 최적의 답이 될 수 없다는 것을 알 수 있지요. 따라서 넉넉잡아도 사탕을 가장 많이 받은 어린이가 (20×N)/3+20 넘게 사탕을 받는 경우는 무시해도 됩니다. 그러면 실제로 할당해야 하는 배열의 크기는 (20×N^3+20)^3≤220^3(대략 1000만)으로 줄어듭니다.

이 부분이 바로, 이 글을 포스팅하게 만든 부분이다.
2억 가지의 경우의 수 중, 무게 차가 20 이상인 경우에 대해서 생각해보자.
사탕의 총 무게가 가장 무거운 어린이를 A, 가장 가벼운 어린이를 C라고 하자.
사탕의 최대 무게는 20이므로, A가 C에게 사탕을 하나 주면 무게 차는 항상 감소한다고 한다. (사실은 동등 또는 감소)
예시를 통해 검증해보자.

무게 차가 20 이상인 경우는 카운팅 할 필요 없다는 사실을 확인하기 위한 과정을 묘사하는 중이다.
A의 무게가 100, C의 무게가 80이라고 가정하자. 이 때 무게 차는 20이다.
A가 C에게 무게 20의 사탕을 1개 줬다면, A의 무게는 80, C의 무게는 100이 된다.
이 때도 무게 차는 20으로 변동없다. (무게 크기 관계는 역전됐지만)

만약 A가 C에게 무게 1의 사탕을 1개 줬다면, A의 무게는 99, C의 무게는 81이며 무게 차는 18로 감소한다.
사탕의 무게가 1~20이므로, 무게 차가 20인 경우에는 A가 C에게 사탕을 1개 주더라도 무게 차가 동등 또는 감소한다는 사실을 확인했다.

무게가 20 초과인 경우는 직관적으로, A가 C에게 사탕을 1개 주면 무게 차가 항상 감소한다는 사실을 알 수 있을 것이다.

문제에서 원하는 답은, 무게 차의 최소값이다.
하지만 무게 차가 20 이상인 경우는 최소 무게 차가 될 수 없다.
무게 차가 더 작은 경우가 항상 존재하기 때문이다.
무게 차가 더 작은 경우란, 무게 차가 20 이상인 경우에서 A가 C에게 사탕을 1개 준 것과 동일한 경우를 의미한다.

그러므로 무게 차가 20 이상인 경우는 카운팅 할 필요 없다.
문제에 나와있듯이 각 어린이의 사탕 총 무게가 (20×N)/3+20 이상인 경우는 카운팅할 필요 없다.
무게 차가 최소값이 될 수 없는 경우니까.
N=30인 경우 이 무게는 최대 220이 된다 (모든 사탕의 무게가 20)

사탕 총 무게가 가장 무거운 어린이가 220일 때, 가장 가벼운 어린이는 최대 180이 될 수 있다 (나머지 한 어린이는 200)
3명의 무게 합은 600이고, 무게 차는 40이 된다

필자의 생각으로는, 220^3가지의 경우의 수는, 무게 차가 40인 경우를 제외한 모든 경우의 수로 보인다
무게 차가 20 이상인 경우를 모두 제외하면 경우의 수를 더 줄일 수 있지 않을까 생각이 든다 (개선의 여지)
정리하여, 또다시 경우의 수를 획기적으로 감소시켰다.
이미 문제를 푸는 데에는 문제가 없는 수준까지 개선시켰다고 할 수 있겠다.

5

이 정도면 충분히 문제를 풀 수 있을 것 같지만, 문제를 푸는 더 빠른 방법이 있습니다. 세 어린이 중 누가 가장 사탕을 적게 받고, 누가 가장 많이 받는지는 중요하지 않기 때문입니다. 세 어린이의 사탕의 총량이 (180, 190, 200)이건 (200, 190, 180)이건 우리의 답은 변하지 않지요. 따라서 세 어린이의 사탕의 총량이 항상 오름차순으로 정렬되어 있는 경우만을 탐색하도록 합시다. 서로 다른 세 수를 여섯 가지의 방법으로 나열할 수 있으므로, 이렇게 하면 경우의 수는 다시 대략 1/6으로 줄어듭니다. 결과적으로 대략 200만 개 이하의 경우의 수만을 탐색해 문제를 해결할 수 있지요. 이 과정에서 천재만이 떠올릴 수 있는 번뜩이는 영감은 필요없었지만, 처음에 생각했던 방법에 비해 검사해야 할 상태의 수가 1억분의 1로 줄어들었음을 알 수 있습니다.

3명 중 누구의 사탕 총 무게가 가장 무거운지는 중요하지 않다.
그러므로 3명을 무게 순으로 오름차순 배치하여 경우의 줄일 수 있다.
3명의 어린이를 배치하는 방법은 순열 P(3,3) = 3x2x1 = 6가지 이고
이 중 오름차순 배치만 카운팅 하면 되므로, 경우의 수는 1/6배가 된다.
최종 경우의 수는 220^3 / 6가지가 되었다.

구현 코드

코드 하이라이팅 출처 : https://colorscripter.com/

3^N 카운팅 코드