코드를 작성하다 보면 뭔가 아쉽고 찜찜한 상황이 생긴다. 눈앞에 있는 코드가 최선일까? 코드를 작성하기 전에 생각하고, 생각을 검증한 다음, 작성해야 한다. 생각하긴 쉽다! 작성하기도 쉽다! (사실 둘 다 어렵지만, 쉽다고 하자) 하지만 생각을 검증하는 건, 그 생각이 최선임을 어떻게 확신하지?

아니, 저런 방법이?

codeforces 217/a, "Ice Skating"

내가 작성한 코드는 가능한 모든 snow drifts의 unordered pair를 고려한다. N은 최대 100이었기 때문에, O(n^2)인 코드도 문제 없이 동작한다.

하지만, 더 좋은 방법이 있다. 우선 x 좌표로 정렬시킨 후, 같은 x 좌표를 가진 snow dirfts를 group하고, 다시 y 좌표로 정렬시킨 후, 같은 y 좌표를 가진 snow drifts를 group 한다면 O(NlgN)으로 동작하는 코드를 작성할 수 있다.

위 설명을 듣고 머리가 멍해졌다. 어떻게 저런 생각을! 한 없이 우울해졌다. 그래서일까 예전 일이 떠올랐다.

baekjoon no. 2309, "일곱 난쟁이"

online judge site를 처음 알게 됐을 때, 친구와 함께 문제를 풀어보기로 했다. 그렇게 선택된 문제를 읽고, 둘 다 서로를 바라보며 굉장히 찝찝해했다. "생각나는 방법은 하나밖에 없어. 하지만 이 방법이 최선일까?"

내가 떠올린 방법은 가능한 모든 7쌍의 난쟁이를 선정하고, 키를 더해서 조건에 부합하는지 가려내는 방법이었다. 너무 찝찝했다. 정말 이게 답일까? 하지만 친구도 같은 답을 생각한 거 같은데?

하지만 위 방법을 얘기했을 때, 친구는 황당한 표정으로 날 바라봤다. (고백하자면, 꽤 상처받았다) "그냥 모든 키를 더한 다음에, 가능한 모든 2쌍의 난쟁이를 선정하고, 두 난쟁이 키의 합을 전체에서 빼는 게 더 좋지 않을까?"

그래. 난 별로 영리하지 못한가 보다.

아니, 결국 이거였다고?

codeforces 52/c, "Circular RMQ"

이 문제를 풀지 못해서 해설을 들었다. 그 과정에서 처음으로 segment tree를 알았다. (세상엔 천재들이 너무 많은 듯하다) 개념은 그다지 어렵지 않았고, 그냥 그렇게 지나갈 줄 알았다.

하지만 update를 구현하지 못했다. "target_range를 받아야 하는 건 알겠어, 하지만 tree에 어떻게 적용하지? index만으로는 불충분한데? node_range만으로도 불충분해. 그렇다고 index와 node_range 모두 받는다고? 그럴 리 없어! 분명 더 좋은 방법이 있을 거야!"

결국 이틀을 고민하다 seg tree의 구현을 찾아봤고, index와 node_range를 모두 인자로 전달하는 예제를 봤지만, 둘 중 하나만으로 동작하는 코드는 찾을 수 없었다. 허무했다.

얼마나 고민해야 할까?

이미 동작하는 코드가 있다. 하지만 더 좋은 방법이 있을 것 같다. 그런 생각이 머릿속을 떠나지 않는다. 하지만 "더 좋은 방법"은 있을 수도, 없을 수도 있다.

codeforces나 baekjoon은 간단하다. 출제자나 이미 나보다 좋은 성능의 코드를 제출한 사람에게 물어보면 되기 때문이다. 하지만 현실에선 물어볼 누군가가 없다. 내게 알고리즘을 강의하시는 교수님께서 "Online judge site에서 연습하는 게 어렵게 느껴질 수 있다. 하지만 현실은 비교도 할 수 없을 만큼 더 어렵다."고 하신 데에는 이 이유도 크리라 생각한다.

그렇다면 얼마나 고민해야 할까? 이 질문이 평생 날 쫓을 거란 예감이 든다.