훅 — 결혼식 좌석 배치
2010년, 프린스턴 화학공학 박사과정생 Meghan Bellows는 자기 결혼식 좌석 배치에 골머리를 앓다가 갑자기 깨달았습니다 — 자기 박사 논문(단백질 아미노산 배치)과 결혼식 좌석 문제가 1:1로 대응한다는 것을.
107명, 11개 테이블. 가능한 경우의 수는 11107 — 112자리 숫자입니다. 관측 가능한 우주의 원자 수(80자리)보다도 훨씬 큽니다. 프린스턴 컴퓨터 클러스터로 36시간을 돌렸지만 진짜 최적해는 못 찾았습니다.
그래도 컴퓨터는 사람이 떠올리지 못한 안을 제시했습니다 — "신부 부모를 가족 테이블에서 빼서 오랜 친구들과 같이 앉히자". 신부 어머니가 살짝 손본 뒤 채택됐죠. 완벽 대신 충분히 좋은답의 위력입니다.
핵심 통찰
Intractability — 어떤 문제는 그냥 어렵다
외판원 문제(TSP) — 모든 도시를 한 번씩 방문하는 최단 경로 — 도시가 늘면 가능한 경로는 O(n!). 도시 10개면 약 360만 경로. 100개면 우주의 끝이 옵니다.
해법 1
Constraint Relaxation (제약 완화)
외판원 문제에서 "같은 도시를 두 번 방문해도 된다"고 제약을 풀면 'minimum spanning tree'가 됩니다. 진짜 최적해는 이보다 짧을 수 없으니하한선(lower bound)을 제공하죠. 이 방법으로 지구상 모든 도시 TSP가 최적해의 0.05% 이내까지 근사됐습니다.
해법 2
Continuous Relaxation (연속 완화)
이산("예/아니오") 선택을 분수·확률로 바꿉니다. "편지를 1/4통, 또 다른 사람에게 2/3통 보낸다" 같은 답을 얻은 뒤 반올림하거나 동전 던지기로 정수화합니다. 이 방법은 최적해의 최대 2배 안에 들어옴이 수학적으로 보장됩니다.
해법 3
Lagrangian Relaxation — '아니면 어쩔 건데?'
어린 Brian이 숙제와 잡일 불평을 늘어놓자 어머니는 말했습니다: "사실 너는 아무것도 해야 할 필요는 없어. 선생님 말 안 들어도 되고, 내 말도, 법도 안 지켜도 돼. 다만 그에 따른 결과를 받아들일지 결정하면 돼." — 라그랑지 완화의 인생 버전.
직접 해보기
배낭 문제
🎒 배낭 — 정확한 답 vs 완화한 답
용량 안에서 가치를 최대화하세요. 다음 세 가지 답을 비교해 보세요 — 완벽한 DP, 밀도 기준 그리디(연속 완화), 라그랑지 완화(무게 페널티).
배낭 용량
8kg
현재 무게
0kg
총 가치 (현재 선택)
0점
DP 최적: 19점
세 가지 답 비교
DP (정확)
19점
100%
그리디 (밀도)
18점
95% 근사
라그랑지
16점
6kg
2점/kg
페널티가 너무 작으면 무게를 어겨도 이득 → 가벼운 페널티는 합리적 무시. 페널티가 크면 자동으로 가벼운 짐만 챙김.
💡 완화(Relaxation)의 정신: 그리디는 "분수 짐도 OK"라는 연속 완화의 정수 반올림본, 라그랑지는 "꼭 지켜야 한다"를 "어기면 비용을 낸다"로 강등시킵니다. 완벽한 DP는 8개 항목엔 가능하지만, 항목이 많아지면 거의 모든 실생활 문제는 이런 완화로만 풀 수 있습니다.
역사 속의 외판원
16년간 봄가을마다 14개 카운티를 도는 순회 변호사 — 사실상 19세기판 TSP였습니다.
카네기 멜런의 그가 매년 메이저리그 야구와 NCAA 스케줄을 짭니다. 야구계 사람들은 "양키스와 메츠는 절대 같은 날 홈경기 안 한다"고 믿지만, 실제로는 시즌당 3~6번 같은 날 홈경기를 합니다. 라그랑지 완화로 일부 제약을 페널티로 바꾸기 때문입니다.
"완벽은 좋은 것의 적이다."
"문제가 어렵다는 것이 무시해도 된다는 뜻은 아니다. 다만 다른 신분의 적일 뿐. 여전히 싸워야 한다."
실생활 적용
- 💭 인생 계획: "두렵지 않다면 무엇을 할 것인가?", "복권에 당첨되면?", "모든 직업의 보수가 같다면?" — 이상화된 세계에서 시작점을 찾고 현실로 환원하라.
- 📅 일정 관리: '도시 사이를 순간이동할 수 있다면 하루 1시간 미팅 8개가 한계'라는 식으로 상한선부터 잡아라.
- 🎵 셋리스트/북투어: 통금이나 벌금을 감수할 수 있다면 그것이 합리적일 때가 있다.
- 💉 공중보건: 분수 vaccine으로 푼 다음, 0.5 이상이면 실제 배치 또는 동전 던지기.
Reflection
고민해 볼 질문들
정답이 정해져 있지 않은 열린 질문입니다. 혼자 생각해 보거나, 가까운 사람과 함께 이야기 나눠 보세요.
- 01
당신이 '불가능'이라 여기는 것 중 사실은 '비싼 일'에 불과한 것은 무엇인가요? 페널티만 감수하면 풀리는가요?
- 02
Brian의 어머니처럼 — 당신 인생에서 '사실 너는 안 해도 돼'를 적용할 수 있는 의무는 무엇인가요?
- 03
완벽을 포기하고 충분히 좋은 답을 받아들이기 가장 어려운 영역은 어디인가요? 왜 그럴까요?
- 04
이상화된 질문들 — '두렵지 않다면 무엇을 할까?', '복권에 당첨되면?' — 에 솔직하게 답한다면, 지금의 선택은 어떻게 달라질까요?