오늘의 질문

문제를 풀기 시작할 때, 나는 무엇을 끝까지 기억해야 할까?

한동안 나는 알고리즘 공부를 정답의 이름을 익히는 일에 가깝게 생각했다. 그래프가 나오면 탐색을 떠올리고, 최적화가 보이면 여러 기법을 후보로 올려 두는 식이다. 그런데 막상 손으로 문제를 풀다 보면, 이름을 안다는 사실만으로는 다음 줄의 코드를 쓸 수 없었다. 무엇을 기록해야 하는지 결정하지 못하면, 어떤 도구를 써도 생각은 금방 엉킨다.

처음의 생각: 가능한 것은 많이 남겨야 안전하다

처음에는 정보가 많을수록 안전하다고 느꼈다. 지금까지 온 경로, 시도한 선택, 실패한 경우, 앞으로의 후보를 되도록 많이 들고 가면 언젠가 필요할 것 같았다. 하지만 그 방식은 빠르게 한계에 닿는다. 같은 곳에 여러 번 도착한 기록이 쌓이고, 이미 의미를 잃은 후보도 계속 신경 써야 한다. 코드는 길어지고, 머릿속에서는 무엇이 현재 판단에 필요한 정보인지 보이지 않게 된다.

문제의 크기가 커질수록 모든 과거를 보관하는 방법은 답이 될 수 없다. 결국 어떤 정보는 남기고 어떤 정보는 버려야 한다. 중요한 것은 그 선택이 성급한 망각이 아니라는 점이다.

생각이 바뀐 지점: 상태는 기억의 목록이 아니라 약속이다

이제는 해법을 찾기 전에 먼저 묻는다. 이 사실이 앞으로 가능한 선택이나 결과를 바꿀까?

바꾼다면 상태에 남긴다. 바꾸지 않는다면, 그 정보는 과감히 요약하거나 버릴 수 있다. 예를 들어 서로 다른 두 과정이 지금부터는 똑같은 선택지와 비용을 갖는다면, 두 과정의 세부 이야기를 각각 들고 갈 이유는 없다. 둘을 하나의 상태로 묶고, 그 상태에 도달하는 더 좋은 방법만 남기는 편이 낫다.

반대로 현재까지의 순서나 아직 끝나지 않은 맥락이 다음 판단을 바꾼다면, 그것은 지우면 안 된다. 어느 후보를 먼저 처리했는지, 지금 어떤 선택의 안쪽에 들어와 있는지, 두 대상이 이미 같은 묶음인지처럼 미래의 질문에 직접 답하는 정보는 끝까지 살아남아야 한다.

그래서 상태는 단순한 변수 묶음이 아니다. 무엇을 기억하고 무엇을 잊어도 되는지에 대한 약속이다.

버리는 데는 근거가 필요하다

여기서 가장 어려운 일은 정보를 줄이는 일이 아니라, 줄여도 된다는 이유를 찾는 일이다.

어떤 후보가 이미 더 좋은 후보에게 완전히 밀렸다면 다시 볼 필요가 없을 수 있다. 어떤 경로가 더 짧은 방법으로 이미 확인되었다면 뒤늦게 도착한 경로는 의미가 없을 수 있다. 어떤 선택이 최선의 해 안으로 언제나 바꿔 넣을 수 있다면, 다른 선택을 계속 탐색하지 않아도 될 수 있다.

하지만 이런 문장은 모두 조건을 품고 있다. 비용이 달라지면 순서가 주던 보장이 사라질 수 있고, 과거의 작은 차이가 이후의 제약을 바꾼다면 같은 상태라고 묶을 수 없다. 잘못 버린 정보는 계산량을 줄여 주는 대신 정답도 함께 지운다.

그래서 나는 “이건 필요 없어 보인다”보다 “다시 필요하지 않다는 것을 무엇으로 확인할 수 있나”를 먼저 묻는 편이 좋다고 생각하게 됐다. 반례 하나를 떠올려 보는 습관도 이때 도움이 된다. 내가 버리려는 정보가 다른 결론을 만들 수 있는 작은 상황을 찾을 수 있다면, 아직 상태가 충분하지 않다는 뜻이다.

공부 방식도 달라졌다

기법의 정의를 외우는 일은 여전히 필요하다. 다만 이제는 문제를 읽을 때 이름보다 질문을 앞에 둔다.

이전의 선택이 앞으로도 다른 결과를 만드는가. 아직 해결되지 않은 일은 어떤 순서로 닫혀야 하는가. 지금 하나를 확정해도 되는 이유는 있는가. 여러 과거를 하나로 합쳐도 되는 지점은 어디인가.

이 질문에 답하려 하면, 필요한 자료구조와 계산 순서는 뒤에서 따라온다. 반대로 답 없이 도구부터 고르면, 코드는 그럴듯해도 왜 맞는지 설명하기 어렵다.

남는 한계

물론 모든 문제를 이 한 문장으로 풀 수는 없다. 무엇을 남길지 아는 것과 그것을 효율적으로 구현하는 일은 다르다. 상태를 잘 골라도 시간과 메모리가 부족할 수 있고, 증명은 맞아도 경계 조건에서 구현이 틀릴 수 있다. 현실의 일은 알고리즘 문제보다 더 많은 모호함과 바뀌는 조건을 품고 있기도 하다.

그래도 이 관점은 출발점으로 유용하다. 복잡함을 줄이려 할 때, 무작정 단순화하지 않게 해 주기 때문이다.

지금의 작은 선택

다음 문제를 풀 때는 코드를 쓰기 전에 한 줄만 적어 보려 한다. 이 문제에서 미래를 바꾸는 최소한의 사실은 무엇인가?

그 한 줄이 명확해지면, 버릴 정보와 남길 정보의 경계도 조금씩 보이기 시작한다.