완전탐색

• 완전탐색은 모든 케이스에 대해서 일일히 다 해봐서 답을 구하는 방법, Bruteforce 기법중 하나라고 할수있다.

• 완전탐색은 주어진 문제에 따라서 다음과 같이 생각해 볼 수 있다.

• N의 크기에 따라 루프로 풀지 재귀로 풀지 결정해야 한다.

  • 루프로 푸는 방법 : 비트연산, next permutation, 큐, 이분탐색(상한과 하한을 정해서 계속 반으로 쪼개서 탐색)
  • 재귀로 푸는 방법 : 호출되는 최대 depth 를 고려해서 충분히 가능한지 고려해야한다. 스택의 크기를 고려해야 하므로 가능하면 1000번 이상 호출되지 않도록 고려한다.

• 중복 호출이 된다면 DP 를 적용하도록 한다.

• 관련문제

• 개똥벌레 - 구간합+완전탐색

• 랜선 자르기 - 이분탐색