[알고리즘] 완전탐색

완전탐색 개념

 

완전탐색은 컴퓨터의 빠른 계산 성능을 활용하여 가능한 모든 경우의 수를 탐색하는 방법
'무식하게 푼다'의 의미인 Brute Force 라고도 부름

모든 경우의 수를 탐색하기에 정확성은 100%, 효율성은 꽝
따라서 주어진 N의 크기가 작을 때 사용하는 것이 좋음

'알고리즘' 이라기보다는 문제를 푸는 방법!!

 

---

완전탐색 풀이 방법

1. 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산
2. 가능한 모든 방법을 다 고려
3. 실제 답을 구할 수 있는지 적용

 

위의 2에서 말한 "모든 방법" 5가지

1. 단순 Brute Force
2. 순열
3. 재귀 호출
4. 비트마스크
5. BFS, DFS

 

 

 

 

단순 Brute Force

반복문, 조건문을 활용하여 단순하게 모든 방법을 찾는 방법
ex) 자물쇠 암호를 찾는 경우 (0000 ~ 9999 모든 경우를 확인)

BFS, DFS 활용

그래프 자료구조에서 모든 정점을 탐색하기 위한 방법
ex) 단순히 길을 찾는 문제 => BFS, DFS // 장애물, 목적지 추가 등 추가적인 작업 필요한 문제 => 완전 탐색 + BFS, DFS

순열

임의의 수열이 있을 때, 그것을 다른 순서로 연산하는 방법인 순열을 활용하는 방법
서로 다른 N개를 일렬로 나열하는 순열의 경우의 수 = N! // N이 한 자릿수 정도..
완전탐색의 대표적인 유형
ex) n개의 숫자로 가능한 모든 순열을 만들어 경우의 수 확인

재귀 호출

재귀 함수를 통해 해결하는 방법
ex) 부분집합 문제, 만들고자 하는 부분 집합 S'일 때, S' = { }이며 각 원소에 대해 해당 원소가 포함되면 S'에 넣고 재귀 함수 호출, 포함되지 않으면 S'을 그대로 재귀 함수에 넣어주는 방식

비트마스크

비트(bit) 연산을 통해 부분 집합을 표현하는 방법
ex) 위의 재귀 호출과 마찬가지로 주로 각 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 사용