수학과 시의 만남 고대의 시적 수수께끼를 풀다

여러분, 수학 문제를 풀면서 시를 읽어야 했던 경험이 있으신가요? 이번 포스트에서는 여러분을 독특하고 흥미로운 수학적 여정으로 안내합니다. 바로 1600년대의 고대 시로 작성된 수학 문제를 해결하는 이야기입니다.

 

시로 만나는 수학 문제
1984년 발간된 한 수학책에서 발견된 이 문제는 단순한 수학 퍼즐이 아닙니다. 문제 자체가 고풍스러운 영어 시로 작성되어 있습니다. 시의 일부를 살펴보겠습니다:

"Divide these glowing gems in two, with careful heart and ear.
Let both your crafted vessels hold a weight so nearly shared,
That harmony between them stands, in balance bright and fair."

여기서 '보석(gems)'은 숫자를, '그릇(vessels)'은 리스트 또는 집합을 의미한다고 해석할 수 있습니다. 이 문제는 주어진 숫자 리스트를 두 부분으로 나누어 각 부분의 합이 최대한 같도록 만드는 것입니다.

문제를 풀어보자
문제를 간단히 정리하면 다음과 같습니다:
- 입력: 정수 리스트
- 출력: 두 부분 리스트로 나뉜 결과, 이때 각 리스트의 합 차이가 최소화되어야 함.

예제
입력: [3, 1, 4, 2, 2]
출력: ([2, 4], [3, 1, 2])

이 예제에서는 리스트를 [2, 4]와 [3, 1, 2]로 나누었을 때, 각 리스트의 합이 모두 6으로 같아집니다. 즉, 차이가 0이 됩니다.

파이썬 코드로 해결하기
아래는 이 문제를 해결하는 파이썬 코드입니다:

from itertools import combinations

def minimize_difference(lst):
total_sum = sum(lst)
n = len(lst)
# 가능한 모든 부분집합 생성
best_diff = float('inf')
best_split = ([], [])
for i in range(1, n//2 + 1):
for subset in combinations(lst, i):
subset_sum = sum(subset)
other_sum = total_sum - subset_sum
diff = abs(subset_sum - other_sum)
if diff < best_diff:
best_diff = diff
best_split = (list(subset), [x for x in lst if x not in subset])
return best_split

예제 사용

lst = [3, 1, 4, 2, 2]
result = minimize_difference(lst)
print("Split lists:", result)

코드 설명
1. **부분집합 생성**: `itertools.combinations`를 사용해 가능한 모든 부분집합을 생성합니다.
2. **합 계산**: 각 부분집합의 합과 나머지 요소들의 합을 계산합니다.
3. **차이 비교**: 두 리스트의 합 차이가 최소가 되는 경우를 찾습니다.
4. **결과 반환**: 최적의 두 리스트를 반환합니다.

성능과 한계
이 코드는 리스트가 작을 때는 효과적으로 작동하지만, 리스트가 커질수록 가능한 조합의 수가 기하급수적으로 증가하기 때문에 성능 문제가 발생할 수 있습니다. 따라서 더 큰 입력에 대해서는 동적 프로그래밍과 같은 최적화 알고리즘을 고려해야 합니다.

마무리하며
이 고대의 시적 수수께끼는 단순한 수학 문제를 넘어, 수학과 문학이 만나는 독특한 지점을 보여줍니다. 여러분도 한 번 이 문제를 직접 풀어보세요! 그리고 더 나은 알고리즘이 떠오른다면 꼭 공유해 주세요.