같은 부분 문제를 다시 풀어야 하는가

서로 다른 탐색 경로가 같은 부분 문제에 도달한다면, 가능한 선택을 빠짐없이 살피겠다는 원칙이 같은 계산의 반복까지 요구하지는 않는다. 완전 탐색에서는 경로가 다르다는 이유로 이후 계산도 각각 수행할 수 있다. 하지만 도달한 뒤의 선택과 결과가 같다면, 두 번째 계산에서 새로 알아내는 것은 없다.

새 정보가 없는 반복이라면, 무엇을 재사용할 수 있는지 따져야 한다. 나는 완전 탐색에서 동적 계획법으로 넘어가는 지점을 여기서 이해한다. 한 번 구한 부분 문제의 답을 저장하고 다시 사용하는 것이다. 가능한 선택을 검토한다는 요구는 유지한다. 그 선택의 결과를 매번 처음부터 계산해야 한다는 요구를 줄인다. 탐색 경로의 수와 실제로 풀어야 할 부분 문제의 수가 달라질 수 있다.

다만 계산을 합치려면, 두 부분 문제가 같다는 조건부터 성립해야 한다. 현재 위치만 같아도 이전에 고른 것에 따라 앞으로 허용되는 선택이 달라진다면, 위치만으로 저장한 답을 재사용할 수 없다. 서로 다른 문제를 하나로 취급하게 되기 때문이다. 앞의 중복 계산을 없애려던 판단이 유효하려면, 상태에는 이후의 선택과 답을 결정하는 데 필요한 정보가 들어 있어야 한다.

이 조건 때문에 나는 저장할 공간부터 정하기보다, 무엇을 같은 상태로 볼지 먼저 묻겠다. 필요한 정보를 충분히 담았더니 상태 수가 커질 수도 있다. 그러면 재사용이 정확하다는 설명과 계산량을 감당할 수 있다는 설명은 따로 남는다. 완전 탐색의 반복을 줄일 수 있는 범위는, 같은 상태가 같은 부분 문제를 나타내고 그 상태들이 실제로 반복되는 구간까지다.