탐색 공간을 영리하게 줄이기

때로는 완전 탐색이 아슬아슬하게 너무 느립니다. 이때는 정답을 잃지 않으면서 탐색 범위를 줄이는 것이 해결책입니다. 🙂

강력한 방법 중 하나는 변수 하나를 반복문으로 고정한 다음 나머지를 더 빠르게 해결하는 것입니다. 전체 탐색 하나를 여러 개의 작은 탐색으로 바꾸는 셈입니다.

첫 번째 원소를 고정한 다음 짝이 되는 원소를 이분 탐색하거나 해시로 찾습니다. 그러면 O(n 제곱) 탐색을 대략 O(n 로그 n)으로 바꿀 수 있습니다.

탐색하는 동안 현재까지의 최선의 정답을 이길 수 없는 경로는 즉시 중단합니다. 건너뛴 가지는 탐색하는 데 비용이 들지 않습니다.

먼저 정렬하면 반복문을 일찍 중단할 수 있는 경우가 많습니다. 값이 임계값을 넘으면 나머지 값으로는 도움이 될 수 없다는 것을 알 수 있습니다.

두 항목을 바꿔도 결과가 같다면 한 가지 순서만 탐색합니다. 각 경우를 한 번씩만 세면 작업량을 절반 이하로 줄일 수 있습니다.

항목을 두 절반으로 나누고 각각을 열거한 다음 결합합니다. 이렇게 하면 2^n 탐색을 대략 2^(n/2) 규모의 작업으로 줄일 수 있습니다.

같은 하위 문제가 다시 나타나면 결과를 저장해 재사용합니다. 메모이제이션을 사용하면 탐색에서 반복되는 가지 전체를 제거할 수 있습니다.

각 가지에 대해 낙관적인 상한을 계산합니다. 그 가지에서 최선의 경우에도 질 수 있다면 전체를 건너뛰어 시간을 절약합니다.

모든 가지치기는 안전해야 합니다. 실제로 이길 가능성이 없는 경로만 제거해야 합니다. 단순한 완전 탐색과 비교해 정답을 잃지 않았는지 확인합니다.

완전 탐색이 아깝게 제한 시간에 걸릴 때 이러한 방법을 사용합니다. 변수를 고정하거나, 가지치기하거나, 나누면 탐색이 제한 시간 안에 들어오는 경우가 많습니다.

2^n개의 부분집합을 모두 열거하면 너무 느리지만, 항목을 두 절반으로 나눌 수 있습니다.

변수를 고정하거나, 가능성이 없는 가지를 가지치기하거나, 대칭성을 활용하거나, 중간에서 만나는 방법으로 탐색 범위를 줄입니다. 모든 제거가 안전한지 확인해야 합니다. 🚀