코딩테스트에서 입력 크기와 제한 시간을 확인하면, 사용할 알고리즘을 어디까지 결정할 수 있을까? 나는 먼저 두 조건이 후보를 제외하는 근거인지, 특정 풀이를 선택하는 근거인지 구분하고 싶다. 감당하기 어려운 계산량을 찾았다고 해서, 남은 방법 가운데 정답이 바로 정해지는 것은 아니기 때문이다.

후보를 제외하려면 우선 어떤 입력에서 계산량이 가장 커지는지 물어야 한다. 각 원소를 처리할 때마다 전체 입력을 다시 훑는 접근이라면, 최악의 경우 작업량은 입력 크기의 제곱에 비례할 수 있다. 작은 예제에서 반복이 짧게 끝났다는 관찰만으로, 최대 입력도 처리할 수 있다고 보기는 어렵다. 여기서 확인할 것은 반복문이 눈에 몇 개 보이는지가 아니라, 그 반복이 총 몇 번 수행되는가다.

총수행 횟수를 추정한 다음에는, 그 계산량을 제한 시간과 연결할 수 있는지 살펴야 한다. Big-O는 입력 증가에 따른 연산량의 증가율을 표현하므로, 그 표기만으로 실행 시간을 초 단위로 확정할 수는 없다. 대략적인 연산량 기준은 후보를 거르는 데 쓸 수 있지만 통과를 보장하지는 않는다. 나는 이 단계의 판단을 ‘가능성이 남아 있다’는 정도로 두려 한다.

가능성이 남은 후보를 고르려면, 시간 조건 외에 무엇을 더 확인해야 할까? 같은 입력을 거듭 훑는 앞의 접근에서는, 매번 전체를 읽어야만 얻을 수 있는 정보가 무엇인지부터 좁혀 볼 수 있다. 그 정보가 실제로 필요한지 알아야, 반복을 줄여도 답이 유지되는지 따질 수 있다. 다음에는 반복해서 계산하는 값 가운데 앞선 계산에서 유지할 수 있는 값이 있는지 확인하고 싶다.