좋은 문제 해결가가 되고싶다
<프로그래밍 대회에서 배우는 알고리즘 문제해결 전략>이라는 책이 있다. PS에 관심을 보이던 내게 친구가 권유한, 구매한지 2년이 넘어 책장 한 켠에 고이 놓여있던 책이다. 1년 6개월의 현역병 생활을 마치고 돌아왔던 내가 야심차게(?) 목표로 한 책이기도 하다. 나도 좋은 문제 해결가가 되고싶었다.
문제 해결 전략! 단순한 방법에서 시작할 수 있을까?
책에서 가장 먼저 제시하는 방법은 이전에 풀어본 비슷한 문제를 떠올리라는 것이다. 그리고 그 바로 다음이 단순한 방법에서 시작하는 것이다.
돌이켜보면 난 단순함과 간결함의 독실한 신자였다. 어떤 해답을 떠올려도 내 해답은 너무 복잡하고 지저분하게 느껴졌고 실제로 그랬다. 그래서일까? 문제를 풀 때마다, 풀고 나서도 더 단순하고 더 간결한 해답을 생각해내야만 한다는 강박이 있었고 알고리즘을 구상하는 단계에서 될 것 같은 로직을 떠올리더라도 너무 비효율적이단 생각에 포기하거나 자책하곤 했다. 더 심하게는, 제시한 해답이 너무 느리거나 쓸데없이 복잡하다면 틀리다고 생각했다. (실제로 문제에서 제시된 조건을 충족시키지 못하면 오답처리되지만, 정답처리 되더라도 성에 차지 않으면 풀었다기보다는 잘못된 문제를 접한 기분이었다.)
하지만 정말 그랬을까?
무식하게 시작해라
책은 일단은 무식하게 도전해보라고 한다. 제한된 시간도, 메모리도 고려하지 말고 우선은 단순무식하게 풀어보라고 권한다. 그러면서 저자는 한 가지 예를 보여준다. 아이들에게 사탕을 나눠주는 경우를 얘기하는 문제에서 저자는 무식하게 모든 경우의 수를 확인하는 알고리즘을 작성한다. 그리고 중복되는 경우를 줄이면서 차근차근 최적화를 진행한다. 그렇게 짜잔! 완성된 결과물은 흠잡을 곳 없이 단순하고 간결하다.
난 BF가 싫어!
이쯤에서 새내기때의 일이 떠오른다. 처음 가입한 과 동아리에서 한 선배가 세미나를 하고 있었다. 서버를 하나 열었고, 2자릿수의 비밀번호를 걸어 두었는데, 이 중에서 가장 먼저 접속에 성공하는 사람에게 간식을 주겠다고 했다. 난 열심히 99에서부터 하나씩 내려가기 바빴는데 웬걸? 여기저기서 번쩍번쩍 손을 들기 시작했다. 알고 보니 비밀번호는 12였다. 아쉬움에 한탄을 하고 있는 내 모습에 웃어주던 선배의 모습이 아직도 기억난다. 사실 그 전에도, 동아리 단톡방에서 종종 비슷한 문제를 내곤 했다. 내 동기중에서는 손쉽게 문제를 해결하고 선배들에게 이쁨받는 경우도 있었는데, 아쉬웠지만 난 할 수 없는 일이라고 생각했다.
그렇다. 그 강연의 주제는 BF(Brute Force)였다. 그제서야 이전 단톡에서의 일에, 장난스럽게 출제한 선배의 생일을 물어보던 동기의 톡이 그저 장난이 아니었다는 사실을 깨달았다. 하지만 난 BF가 싫었다. 무식하게 대입해보는게 해법이었다니. 그건 우아하지 않았다. 듣기만 해도 감탄이 터져나올만큼 엄청난 알고리즘이나 트릭이 아니었단 사실에 적잖이 실망했다.
이후 알고리즘 문제를 풀 때에도, 단순 구현이나 BF문제라고 생각되면 혀를 차며 덮어버리곤 했다. 이 모습을 본 내 친구가 제발 코드 좀 짜보라고 조언했지만 난 귀담아 듣지 않았다. 내게 문제 해결이란 BF와 같은 무식한 일이 아니라, 참신한 발상과 뛰어난 통찰로 문제의 맥을 집는 더 뛰어난 무언가였다.
TDD! 하지만 와닿지 않아…
처음 test를 접했을 때의 흥분은 아직도 생생하다. 하지만 강렬했던 만큼이나 빠르게 식었다. 테스트가 실용적으로 느껴지지 않았기 때문이다. 테스트의 설계적 효용은 여전히 놀랍지만, 검증적 측면을 생각하면 물음표가 떠오른다. 100%의 branch coverage는 달성 가능해 보인다. 하지만 100%의 data coverage는 불가능하다. 그렇다면 "충분한" data coverage는 어떨까? 그리고 그만큼의 test case를 작성하는건? 그 비용은?
fuzz testing
Elm은 fuzz test를 권한다. (물론 edge case를 위한 직접 입력도 허용한다.) 처음 fuzz test의 개념을 접했을 때, 드디어 test를 이해했다고 생각했다. 하지만 이내 낙담했다. 무작위 입력을 생성하는건 쉽지만, 올바른 출력을 어떻게 판단한단 말인가? 그 답을 이미 알고있다면, 테스트할 프로그램의 존재 의의는 무엇인가? 제시된 예제가 assert_equal(add(a, b), a + b);와 같은 형태였고, 당시의 나는 이 이상 생각할 수 없었다.
scaffolding: 느리더라도 확실하게 동작하는 코드의 유용함
"느리지만 확실하게 동작하는 코드"는 필요하다. 느린 코드를 최적화하며 더 좋은 코드를 만들수도 있고, 어쩌면 더 좋은 알고리즘을 향한 idea를 얻을지도 모른다. 설령 그렇지 못하더라도, "확실하게" 동작하는 코드는 그 자체로 "불확실하지만 성능은 더 좋은" 코드를 검증하는데 사용될 수 있다.
