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

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

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

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

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

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

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

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

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

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

img

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

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

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

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

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