완전탐색 (Exhaustive search) - goorm-6th-Als/for_study_Algorithm GitHub Wiki
모든 경우의 수를 다 체크해서 정답을 찾는 방법이다.
- 무식하게 한다는 의미로 'Brute Force'라고도 부른다.
- 직관적이어서 이해하기 쉽고 문제의 정확한 결과값을 얻어낼 수 있는 가장 확실하며 기초적인 방법이다.
- 경우의 수에 따라 실행 시간이 비례하기 때문에 입력 값의 범위가 작은 경우 유용하다.
- 단순히 반복문과 조건문으로 모든 경우를 만들어 답을 구하는 방법이다.
- 비트(bit) 연산을 통해서 부분 집합을 표현하는 방법을 의미한다.
- 문제에서 나올 수 있는 모든 경우의 수에 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 유용하게 사용이 가능하다.
ex) 어떤 집합의 부분집합은 집합의 각 원소가 해당 부분집합에 포함되거나, 포함되지 않는 두 가지 경우만 존재한다.
따라서 5자리 이진수 (0 ~ 31)를 이용하여 각 원소의 포함 여부를 체크할 수 있다.
- 원소가 포함되면 해당 원소를 넣어 함수를 호출하고, 포함되지 않으면 그 상태에서 함수를 호출하는 방식이다.
- 비트마스크와 마찬가지로 주로 각 원소가 포함되거나, 포함되지 않는 두 가지 선택을 가질 때 이용된다.
- 완전탐색의 대표적인 유형이다. 임의의 수열이 있을 때, 그것을 다른 순서로 연산하는 방법을 의미한다.
- 서로 다른 N개를 일렬로 나열하는 순열의 경우의 수는 N!이므로 완전탐색을 이용하기 위해서는 N이 한자리 수 정도는 되어야 한다.
