d라이브러리

드디어 이삿날! ‘매스 익스프레스’라는 문구가 쓰여 있는 조끼를 입은 이삿짐센터 아저씨들이 오셨어. 그런데 이 아저씨들은 뭔가 남다른 것 같아. 상자에 짐을 넣고 나르는 게 아니라 옮길 물건들을 기록하면서 컴퓨터에 뭔가를 입력하는 거 있지? 대체 뭘 하는 거지?

상자 채우기 문제란?

부피가 제각각인 물건을 가장 적은 수의 상자에 효과적으로 집어넣는 방법을 찾는 문제다. 넣을 물건이 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차원의 상자 채우기 문제라고 볼 수 있어요. 상자 채우기가 쌓는 것이라면 여기서는 옷감을 효율적으로 자르는 최적의 방법을 찾는 거죠. 종이를 만드는 공장에서도 크고 넓은 종이를 잘라서 A3와 A4 등 다양한 크기로 만들 때 2차원 상자 채우기 문제를 활용하면 버려지는 부분이 적게 만들 수 있답니다.

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

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