술병은 한정, 만들고 싶은 칵테일은 많고
홈 바(home bar)를 꾸려본 사람이라면 누구나 겪는 고민이 있어요. 칵테일 레시피는 수백 가지인데, 진·럼·베르무트·비터스... 재료를 다 사려니 돈도 공간도 감당이 안 돼요. 그래서 자연스럽게 이런 질문이 떠오르죠. "딱 10병만 산다면, 어떤 조합을 사야 만들 수 있는 칵테일 종류가 제일 많아질까?" 이 글은 바로 이 술꾼의 고민을 수학 최적화 문제로 멋지게 풀어낸 이야기예요.
이게 뭐냐면, 정수계획법(MILP)
여기서 쓰인 도구가 MILP(혼합 정수 선형 계획법)예요. 이름이 거창한데 풀어보면 별거 아니에요.
먼저 선형 계획법(LP)은 "여러 제약 조건 안에서 어떤 값을 최대(또는 최소)로 만들까"를 찾는 방법이에요. 예를 들어 "예산 안에서 이익을 최대로" 같은 문제죠. 그런데 현실엔 "0.5병을 산다"가 말이 안 되는 경우가 많아요. 술병은 사거나(1) 안 사거나(0) 둘 중 하나잖아요. 이렇게 답이 정수여야 하는 조건이 붙으면 그게 바로 정수계획법이에요. 'M(혼합)'은 정수 변수와 일반 변수가 섞여 있다는 뜻이고요.
칵테일 문제를 이 틀에 넣어볼게요. 각 재료마다 "살까 말까"를 나타내는 0 또는 1짜리 스위치 변수를 둬요. 그리고 칵테일 하나하나에 대해 "이 칵테일에 필요한 재료를 전부 샀다면 만들 수 있다"는 규칙을 걸어요. 마지막으로 "총 구매한 병 수는 N개 이하"라는 예산 제약을 붙이고, 만들 수 있는 칵테일 개수를 최대로 하라고 풀이기(solver)에게 던지면 끝이에요.
왜 이게 어려운 문제일까
얼핏 "그냥 인기 재료부터 사면 되잖아?" 싶지만, 함정이 있어요. 진을 사면 진 토닉도 되고 마티니도 되지만, 마티니는 베르무트가 또 있어야 완성되거든요. 재료들이 서로 얽혀 있어서, 하나를 더 사는 게 다른 여러 칵테일을 한꺼번에 열어주기도 하고 아무 효과가 없기도 해요. 이건 컴퓨터과학에서 최대 커버리지(maximum coverage) 문제라고 부르는, 무작정 다 따져보면 경우의 수가 폭발하는 어려운(NP-hard) 종류예요. 그래서 똑똑한 풀이기가 필요한 거죠. 다행히 요즘 솔버들은 이 정도 규모는 순식간에 최적해를 찾아줍니다.
업계 맥락: 이건 사실 '운영 최적화'의 축소판
재미로 칵테일을 예로 들었지만, 똑같은 수학이 산업 현장 곳곳에서 돌아가요. 물류 회사가 어느 창고에 어떤 물건을 둘지, 항공사가 승무원 스케줄을 어떻게 짤지, 통신사가 기지국을 어디에 세울지... 전부 "한정된 자원으로 최대 효과"를 찾는 같은 종류의 문제거든요. 파이썬에선 PuLP, 구글의 OR-Tools 같은 무료 라이브러리로 누구나 짤 수 있고, 더 큰 규모는 Gurobi 같은 상용 솔버를 써요. 머신러닝이 요즘 대세지만, 이런 운영 연구(Operations Research)는 정답이 수학적으로 보장되는 영역에서 여전히 강력한 무기예요.
한국 개발자에게
이 글의 진짜 가치는 "최적화가 멀리 있는 게 아니다"라는 깨달음이에요. 우리는 보통 이런 문제를 for 문 여러 개로 무식하게 돌리거나 적당히 휴리스틱(어림짐작 규칙)으로 때우는데, 사실 PuLP 몇십 줄이면 수학적으로 최적인 답을 받을 수 있거든요. 배달 경로 짜기, 회의실·근무 스케줄 배정, 재고 발주량 결정처럼 실무에서 흔히 만나는 "뭘 골라야 제일 이득일까" 문제에 그대로 응용돼요. 한 번 익혀두면 평생 써먹는 도구라, 주말에 칵테일 예제로 PuLP를 만져보는 걸 강력 추천해요.
핵심 한 줄: "한정된 재료로 최대한 많은 칵테일"이라는 술자리 고민이, 알고 보면 물류·스케줄링과 똑같은 정수계획법 문제이고, 무료 도구로 누구나 풀 수 있어요.
여러분은 실무에서 "이거 그냥 감으로 정했는데 최적은 아닐 것 같다" 싶었던 선택의 순간이 있었나요? 어떤 문제를 최적화로 풀어보고 싶은지 댓글로 던져봐요.
🔗 출처: Hacker News