주메뉴바로가기.. 본문바로가기

[주말N수학] 세기의 난제 '짐 쌓기'

카카오스토리 네이버밴드 구글플러스

2019년 02월 09일 11:00 프린트하기

상자 채우기 문제란? 부피가 제각각인 물건을 가장 적은 수의 상자에 효과적으로 집어넣는 방법을 찾는 문제다. 넣을 물건이 10개만 넘어도 물건을 넣는 방법이 362만 8800가지가 넘어 일일이 계산해서는 답을 찾을 수 없는 ‘난제’다. 따라서 최적의 근삿값을 찾는 방법으로 문제를 푼다. 동아사이언스
상자 채우기 문제란? 부피가 제각각인 물건을 가장 적은 수의 상자에 효과적으로 집어넣는 방법을 찾는 문제다. 넣을 물건이 10개만 넘어도 물건을 넣는 방법이 362만 8800가지가 넘어 일일이 계산해서는 답을 찾을 수 없는 ‘난제’다. 따라서 최적의 근삿값을 찾는 방법으로 문제를 푼다. 동아사이언스

꽃샘추위가 끝나면 본격적인 이사의 계절이 시작합니다. 이사의 첫 단계는 짐을 싸서 이삿짐을 운반하는 트럭에 싣는 겁니다. 실제 이삿짐을 포장하고 트럭에 쌓는 걸 보면 빈 공간을 최소화하면서도 물건이 손상되지 않게 해 놓은 모습에 감탄이 나올 정도입니다.

 

이삿짐을 싣는 트럭을 큰 상자라고 보고 가장 적은 수의 차량을 이용해서 이사를 하려면 트럭 안에 물건을 빈 공간 없이 효율적으로 넣는 방법을 찾아야 합니다. 수학자들도 30년 이상 연구해 온 ‘상자 채우기 문제’입니다.

 

짐이 많을수록 풀기 어려운 상자 채우기 문제

 

이 문제는 정확한 답을 구하는 것이 거의 불가능하다고 알려진 ‘NP 완전 문제’의 여러 사례 중 하나입니다. 어떤 문제를 몇 단계의 수식 계산을 통해 풀 수 있을 때 이 단계를 시간 개념에 비유해 ‘다항 시간’이라고 부릅니다. NP 문제는 다항 시간 안에 답을 찾는 법은 모르지만 답이 옳은지 확인하는 데 얼마의 다항 시간이 필요한지는 알 수 있는 문제를 말합니다. NP 문제 중에서도 NP 완전 문제는 매우 어려운 문제의 집합을 말합니다

 

상자 채우기 문제가 NP 완전 문제인 이유는 쌓아야 할 물건이 많을수록 공간을 채우는 방법의 수가 기하급수적으로 증가하기 때문입니다. 물건이 몇 개밖에 안 된다면 직접 해 보거나 간단한 계산으로 답을 알아낼 수 있지만 물건이 많아질수록 쌓는 위치와 순서를 정하는 경우의 수가 ‘지수적’으로 증가합니다.

 

지수적이라는 말은 기하급수적이라는 말과 같습니다. 예를 들어 3개의 상자 A와 B, C를 트럭에 싣는 순서를 생각해 보면 ABC, ACB, BAC, BCA, CAB, CBA 이렇게 6가지(3!=3×2×1)입니다. 물론 직육면체 모양의 상자에서 어떤 면을 바닥에 닿게 쌓는지는 무시한 경우의 수입니다. 그런데 상자의 개수를 10개로만 늘려도 경우의 수가 362만8800가지(10!)로 걷잡을 수 없이 커집니다. 보통 이사를 할 때 쓰는 박스는 적게 잡아도 10개가 넘으니까 풀기 어려운 NP 문제라고 볼 수 있겠죠? 이건호 숭실대학교 산업·정보시스템공학과 교수는 “NP 문제에서 최적의 경우를 찾으려면 경우의 수를 일일이 따져봐야 하는데, 슈퍼컴퓨터를 이용해도 평생 답을 못 찾을 수 있다”고 설명했습니다.

 

알고리듬으로 상자 채운다

 

답을 찾기 어려운 NP 문제라고 해서 아무 것도 할 수 없는 건 아닙니다. 정답은 아니더라도 해에 가까운 답을 구하면 좀 더 효과적으로 상자를 쌓을 수 있으니까요. 특히 수출하고 수입하는 상품을 배에 실을 때 쓰는 컨테이너에 효과적으로 짐을 싣기 위해서는 상자 채우기 문제를 푸는 게 아주 중요합니다. 그래서 학자들과 물류 기업들은 정답에 가까운 최적의 해를 찾는 알고리듬을 연구하고, 컴퓨터 프로그램으로 만들어 실제 현장에서 활용합니다.

 

김태현 CJ대한통운 종합물류연구원 컨설팅팀장은 “해외수출입 물류를 담당하는 부서에서는 상자 채우기 문제에서 최적의 답을 구해 주는 프로그램을 활용하고 있다”고 밝혔습니다. 예를 들면 수출할 물건의 종류와 물건을 담은 상자의 가로, 세로, 높이, 개수, 그리고 상자를 세우거나 눕혀 넣을 수 있는지 여부 등의 정보와 컨테이너의 크기를 입력하면 빈 공간을 최소화하는 상자 채우기 방법을 답으로 내놓는 프로그램입니다.

 

정찬윤 CJ대한통운 종합물류연구원 책임컨설턴트는 “학계에서는 물건을 실을 때 도착지 순서에 맞게 먼저 꺼낼 물건을 문에 가까운 쪽에 실으면서 최적의 답을 주는 방법과, 컨테이너의 무게가 한쪽으로 쏠리지 않게 해 주는 방법 등 다양한 조건을 고려한 알고리듬을 연구하고 있고 일부는 실제로 활용 중”이라고 말했습니다.

 

옷감 자르기도 상자 채우기 문제라고?

 

상자 채우기 문제는 활용 분야가 무척 다양합니다. 3차원 공간이 아닌 2차원 평면을 생각해 볼까요? 얇고 넓은 옷감을 잘라서 옷을 만들려고 합니다. 남아서 버리는 옷감이 적을수록 좋겠죠?

 

2차원 상자 채우기 문제는 종이를 만드는 공장에서 다양한 면적의 종이들을 만들 때 버려지는 종이를 최소화하는 데 적용할 수 있다. 게티이미지뱅크
2차원 상자 채우기 문제는 종이를 만드는 공장에서 다양한 면적의 종이들을 만들 때 버려지는 종이를 최소화하는 데 적용할 수 있다. 게티이미지뱅크

이 문제는 2차원의 상자 채우기 문제라고 볼 수 있습니다. 상자 채우기가 쌓는 것이라면 여기서는 옷감을 효율적으로 자르는 최적의 방법을 찾는 겁니다. 종이를 만드는 공장에서도 크고 넓은 종이를 잘라서 A3와 A4 등 다양한 크기로 만들 때 2차원 상자 채우기 문제를 활용하면 버려지는 부분이 적게 만들 수 있답니다.

 

문제를 1차원으로 단순화시키면 또 다른 문제에도 활용할 수 있습니다. 보통 1차원은 선으로 생각하지만, 시간이나 해야 하는 일의 순서도 1차원으로 생각할 수 있는 개념입니다. 따라서 물건을 만드는 공장에서 주어진 다양한 일을 한 사람에게 몰리지 않으면서도 적절한 수의 사람들에게 분배할 때도 상자 채우기 문제를 적용할 수 있습니다.

 

차원에 따라 다른 상자 채우기 문제의 활용 분야. 게티이미지뱅크
차원에 따라 다른 상자 채우기 문제의 활용 분야. 게티이미지뱅크

이상운 강릉원주대 멀티미디어공학과 교수는 “여러 개의 중앙처리장치(CPU)를 이용한 컴퓨터 계산을 할 때도 작업 일정을 분배하는 데 활용할 수 있다”고 설명했습니다.

 

관련기사 : 수학동아 2월호 Part 3. 세기의 난제 ‘짐 쌓기’

카카오스토리 네이버밴드 구글플러스

2019년 02월 09일 11:00 프린트하기

 

혼자보기 아까운 기사
친구들에게 공유해 보세요

네이버밴드 구글플러스

이 기사가 괜찮으셨나요? 메일로 더 많은 기사를 받아보세요!

8 + 3 = 새로고침
###
과학기술과 관련된 분야에서 소개할 만한 재미있는 이야기, 고발 소재 등이 있으면 주저하지 마시고, 알려주세요. 제보하기

관련 태그뉴스