06. 여행지에서의 쇼핑 문제
<알고리즘 행성 여행자들을 위한 안내서>
힘들이지 않고 높은 산악 지역을 돌아다니기 위해 원주민들이 활용하는 또 다른 트릭은 산봉우리를 포기하는 것이다. 목적지에 도달하기 위한 대다수의 조합 문제들은 우리가 늘 목적지에 관한 최상의 해결책을 찾으려고 하기 때문에 어려워진다. 우리가 지극히 일반적인 해결책을 찾는 데 만족한다면, 일은 훨씬 더 간단해진다. 이 일반적인 해결책을 ‘근사치(approximation)’라고 한다. 관광객들은 쇼핑할 때 근사치를 활용한다.
여행지에서 보석을 사려는 관광객은 극히 드물다. 휴가지에서는 쇼핑하더라도 대부분 그냥 가볍게 하기 마련이다. 요즘에는 어느 한 나라의 물건을 세계 곳곳에서 구입할 수 있기 때문에 중요한 것은 현지 가격과 자기 나라에서의 가격을 비교해 비용을 가능한 한 많이 절감하는 것이다. 당신이 꼭 사고 싶어 하는 물품 목록이 있다고 하자. 물품마다 자기 나라에 돌아가서 살 때 절약할 수 있는 일정한 절감액과 중량이 있을 것이다. 구매 물품의 중량 역시 빼놓지 않고 숙고해야 할 부분이다. 항공사의 제한 중량을 초과하는 바람에 물품을 구입할 때 절감한 비용보다 더 많은 비용을 추가 지불하지 않으려면 말이다. 가능한 한 돈을 많이 아끼기 위해선, 당신의 구매 희망 목록 중에서 어떤 물품을 구입할 것인지 잘 선별해야 한다.
간단한 알고리즘을 적용해보자. 먼저, 그램당 얼마나 많은 돈을 절감할 수 있는지에 따라 물품들을 분류한다. 이는 ‘뱅 포 벅(Bang for Buck:본전을 뽑을 수 있는 가치)’에 따른 분류법이다. 그런 다음, 그 순서에 따라 물품들을 차례로 구입한다. 제한 중량을 초과하는 물품이 나올 때까지 말이다. 이 경우, 제일 마지막에 구입한 물품은 제한 중량을 초과하기 때문에 다시 교환해야 한다. 그렇다면 애초에 왜 이 물품을 구입한 걸까? 그 이야기도 곧 나온다!
과연 이게 좋은 아이디어일까? 자, 당신의 구매 희망 목록에 물품이 세 개 있다고 가정해보자. 풀오버 두 개와 재킷 한 개다. 당신의 짐가방에는 1,400g을 더 넣을 여유가 있다. 풀오버 두 개는 똑같은 제품으로, 짐가방을 정확하게 꽉 채운다. 개당 무게는 700g이며, 각각 10유로의 비용 절감 효과가 있다. 재킷은 이보다 조금 더 무거운 755g이다. 무게가 더 나가는 대신 풀오버보다 그램당 비용 절감 효과는 더 크다. 이 재킷은 현지에서 사는 것이 총 15유로 싸다. 이때 뱅 포 벅 알고리즘에 따르면 가장 먼저 재킷을 선택해야 한다. 그러고 나면 두 번째 물품을 담을 공간은 더 이상 남지 않는다.
그런데 어쩌면 풀오버 두 개를 구입하는 것이 더 나을지도 모른다. 그렇게 하면 제한 중량을 최대한 활용해서 총액상 더 많은 금액을 절감하게 되기 때문이다. 이렇게 보면, 뱅 포 벅 알고리즘이 언제나 최고의 솔루션을 찾아내는 건 아니다.
뱅 포 벅 알고리즘으로 할 수 있는 것으로, 풀오버 700g 중에서 645g만 구입해 제한 중량을 정확하게 다 활용하는 방법이 있다(물론 실제로 옷을 팔거나 살 때 이렇게 하는 사람은 없을 것이다). 바로 여기에 쇼핑 문제의 어려움이 있다. 이 경우, 당신은 수학자들이 얘기하는 것처럼 반드시 정수 결정을 내려야만 한다. 즉 풀오버를 온전히 다 사거나 아니면 구입하는 것을 아예 포기해야 한다.
정수 결정은 이른바 분할 결정보다 더 어려운 경우가 많다. 분할 결정에 따르면 구입할 물품의 일부만 구입할 수 있다. 아마 정육점에서 이 같은 일을 해봤을 것이다. 정육점에서 다진 쇠고기 700g을 구입하는 건 전혀 문제가 되지 않는다. 하지만 커틀릿용 고기 700g을 구입하려면, 정육점 주인은 가능한 모든 조합을 저울 위에서 일일이 시험해봐야 할 것이다. 어쩌면 그는 곧바로 “정확하게 700g은 어렵습니다”라고 말할 수도 있다. 그런데 정육점 주인은 냉장고에 정확히 700g이 되는 그 어떤 커틀릿용 고기의 조합도 없다고 정말로 자신할 수 있는 걸까?
쇼핑 문제는 NP 하드 문제다. 물론 커틀릿용 고기 구입 문제도 마찬가지다. 하지만 쇼핑 문제는 근사치로 어림셈할 수 있다. 항공사가 배려심이 있어서 중량이 약간 초과하는 것은 눈감아준다고 가정해보자. 이 경우, 뱅 포 벅 알고리즘에서 제한 중량을 약간 넘어서는 물품을 꼭 다시 교환할 필요는 없다. 이렇게 되면 총액에서 중량 제한을 엄격하게 지킨 완벽한 쇼핑 사례보다 적어도 두 배를 절약하게 된다.
그러나 유감스럽게도 항공사들은 이런 배려심이 없다. 그래도 우리는 다음과 같이 할 수 있다. 첫째, 제한 중량을 넘어서지 않는 범위에서 그 제한에 최대한 가깝게 최고의 뱅 포 벅 물품들을 선별해 구입하는 것이다. 이게 아니라면 둘째, 두 물품 중 어떤 것이 나중에 집에 돌아갔을 때 더 많은 돈을 아끼게 되는지에 따라, 비록 중량을 초과하더라도 물품을 딱 한 가지만 구입하는 것이다. 이 방법으로 우리는 최적의 쇼핑을 할 때 절감할 수 있는 금액의 적어도 2분의 1은 더 절감하게 된다. 이것이 바로 제2근사치(Second approximation)다. 왜냐하면 이상적인 경우가 이 근사치 해결책보다 최대 두 배는 더 좋기 때문이다. 이제 제2근사치는 그렇게 멋지게 들리지 않는다. 안 그런가? 우리는 쇼핑 문제를 이보다 더 근사하게 해석해낼 수 있다. 다만 그렇게 하기가 너무 힘들 뿐이다.
