원문: Pragmatic Programmers Newsletter (Translated by Google Gemini)

저는 제 자신의 조언을 무시했고, 하루를 꼬박 날렸으며, 제가 저 자신의 최악의 고객임을 다시 한번 증명하고 말았습니다. (하지만 절망하지 마세요. 글 마지막에 쿠폰 코드가 있습니다.)

저희의 새로운 유통사는 요금을 청구할 항목들을 만들어내는 데 특별한 재능이 있습니다. 그런 항목이 수십 가지나 되죠. 저희는 순수익에 대해 로열티를 지급하기 때문에, 모든 청구 항목을 하나하나 맞춰봐야 합니다. 간단하죠, 안 그런가요?

문제는 “권당” 발생하는 비용은 한 정산서에 나오고, “총액 공제” 항목은 다른 정산서에 나온다는 겁니다. 게다가 각 총액 항목 안에는 어떤 이름표도 없이 뒤죽박죽 섞인 비용들이 숨어있곤 합니다. 저희가 받는 것이라고는 날짜 두어 개와 무작위로 보이는 총액 하나가 전부입니다. 그러면 저희는 그 총액을 특정 비용들의 어떤 조합과 맞춰봐야 하는 것이죠.

코딩 인터뷰에 단골로 등장하는 이야기로 치자면, 이건 바로 **부분 집합 합 문제(Subset Sum problem)**입니다. 숫자 더미를 받아서, 어떤 조합이 주어진 합계와 일치하는지 알아내는 문제 말입니다.

이건 NP 문제입니다. 크고, 무시무시한 실행 시간을 자랑하죠.

저는 그걸 알고 있었습니다. 그리고 그것이 바로 함정이었습니다.

그 위험한 사실 하나로 무장한 채, 저는 최적화에 착수했습니다. 가지치기(Pruning) 전략. 가능성 높은 쌍으로 묶기. 심지어 각 숫자의 마지막 자릿수만 사용하는 정말 정신 나간 아이디어까지 동원했습니다. 아무래도 제가 제 자신을 미워하나 봅니다.

몇 시간이 증발했고 점심은 차갑게 식었습니다. 저는 ‘다음번 묘수(trick)는 이걸 해결해 줄 거야’라며 스스로를 계속 설득했습니다.

마침내 그럴싸해 보이는 무언가를 만들었지만, 모든 부분 집합을 다 잡아내는지 확신할 필요가 있었습니다. 그래서 비교 테스트를 위해 무차별 대입(brute-force) 버전을 작성했습니다.

img

저는 그 코드를 실행시키고 의자를 뒤로 밀었습니다. 녀석이 몇 시간 동안 낑낑대며 돌아가는 동안 강아지 산책이나 할 생각이었죠. 하지만 제가 채 일어서기도 전에, 프롬프트가 깜빡이며 돌아왔습니다.

이럴 리가 없는데. 분명 버그일 겁니다. 하지만 출력 결과는 멀쩡해 보였습니다.

저는 속성 기반 테스트(property-based tests)로 마구 돌려봤습니다. 전부 초록불(통과)이었습니다. 실행은 밀리초 단위로 끝났습니다.

저는 수많은 무대에 서서 도널드 크누스(Knuth)의 불멸의 명언을 인용해왔습니다. “섣부른 최적화는 모든 악의 근원이다.” 그래놓고는, 바로 그 제단 위에 하루를 통째로 제물로 바치고 만 것입니다.

의사여, 너 자신부터 고쳐라.