완전탐색 - 순열, 조합, 부분집합

완전탐색

• 완전 탐색 방법은 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법
• Brute-force 혹은 generate-and-test기법이라고도 불린다.
• 모든 경우의 수를 ㅌ테스트 한 후, 최종 해법을 도출한다
• 상대적으로 빠른 시간에 문제해결(알고리즘 설계)를 할 수 있다.
• 일반적으로 경우의 수가 상대적으로 작을 때 유용하다.
• 모든 경우의 수를 생성하고 테스트하기 때문에 수행 속도는 느리지만, 해답을 찾아내지 못할 확률이 작다.
• 검정 등에서 주어진 문제를 풀 때 , 우선 완전 검색으로 접근하여 해답을 도출한 후, 성능 개선을 위해 다른 알고리즘을 사용하고 해답을 확인하는 것이 바람직하다.
• 많은 종류의 문제들이 특정 조건을 만족하는 경우나 요소를 찾는 것이다.
• 또한, 이들은 전형적으로 순열, 조합, 그리고 부분집합과 같은 조합적 문제들과 연관된다.
  

순열

• 서로 다른 것들 중 몇개를 뽑아서 한줄로 나열하는 것.
• 서로 다른 n개 중 r개를 택하는 순열은 아래와 같이 표현
• nPr = n!/(n-r)!
• nPr = n * (n-1) * (n-2) * … * (n-r+1)
• nPn = n!이라고 표기하며 Factorial이라 부른다.
• nPn = n * (n-1) * (n-2) * … * 2 * 1
• N개의 요소들에 대해서 n!개의 순열들이 존재한다
• 12! = 479001600
• n>12인 경우, 시간 복잡도 폭발적으로 올라간다. 다른 방법을 찾아야 한다.

순열을 생성하는 방법

1. 반복문
   • 예) {1,2,3}을 포함하는 모든 순열을 생ㅇ성
   • 3P3
2. 재귀를 통한 순열 생성
3. 비트마스킹을 통한 순열 생성