[알고리즘] 완전탐색(Brute-Force Search)

완전탐색(Brute-Force Search) 이란? 🤔

모든 경우의 수를 시도하는 방법으로 경우의 수에 따라 실행 시간이 비례하기 때문에 입력 값의 범위가 작은 경우 효과적임.

1. 단순 Brute Force : 단수히 반복/조건문을 활용해 모든 경우를 만들어 답을 구하는 방법
2. 순열 : N개의 원소를 중복없이 나열하는 방법
3. 비트마스크 : 2진수 표현 기법을 활용해 나올 수 있는 모든 경우의 수가 각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우 유용하게 사용
4. 재귀 함수
5. DFS/BFS

 

1. 역추적(back tracking) : 불필요한 탐색 그만두기

더 이상 진행해도 조건에 맞는 해를 찾을 수 없는 경우(유망성이 없는 경우)에 대해서 더 진행하지 않고(가지치기) 부모 노드로 되돌아가서 다른 해를 찾는 기법으로 DFS가 불필요한 경우까지 모두 탐색하는 것을 제한할 수 있게해준다.  조건문 등의 장치를 통해 답이 될 수 없는 상황을 정의하고 DFS 중에 그에 해당하면 탐색을 중지시킨 뒤 이전 분기로 돌아간다.

 

2. DFS(depth-first search) : 깊이우선탐색

DFS 알고리즘은 backtracking 개념을 사용하는 재귀 알고리즘으로 주로 모든 노드를 방문해야 할 때 이 방법을 선택하며, 너비 우선 탐색(BFS)보다 간단하나 검색 속도는 느릴 수 있다.

👉 Comment
 방문한 노드에 표시해두면, 동일한 노드를 두 번 이상 방문하는 것을 방지할 수 있다.

 

🔽  DFS 동작과정

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

3. BFS(breadth-first search) : 너비우선탐색

큐를 사용해서 가까운 노드부터 탐색하는 알고리즘으로 depth(깊이)를 계산해야되는 문제 (ex 최단경로 구하기) 혹은 가중치가 있는 그래프에서 최단거리 찾는데 효과적임

 

🔽  BFS 동작과정

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복한다