6. 브루트포스(brute-force) part 2

6.7 최적화 문제(Optimization problem)

문제의 답이 하나가 아니라 여러 개이고, 그 중에서 어떤 기준에 따라 가장 '좋은' 답을 찾아 내는 문제

ex) n개의 사과 중에서 r개를 골라 무게의 합을 최대화 하는 문제

최적화 문제를 해결하는 방법 중 기초적인 것은 완전 탐색 이다.
가능한 답을 모두 생성해 보고 그중 가장 좋은 것을 찾아내면 되기 때문에,
가장 직관적인 방법이기도 하다.

다른 방법으로는 동적계획법(DP), 조합탐색, 결정문제 등으로 문제를 더욱 빠르게 풀 수 있다.

ex) 여행하는 외판원 문제 (Traveling Salesman Problem, TSP)

6.10 많이 등장하는 완전 탐색 유형

1. 모든 순열 만들기
   가능한 순열의 수 N!, N이 10을 넘어간다면 시간이 많이 걸리므로, 다른 알고리즘 필요.
   
   
2. 모든 조합 만들기
   이항계수 \( \begin{pmatrix} n \\ r \end{pmatrix} \)
   
   
3. 2ⁿ가지 경우의 수 만들기