탐색

완전탐색/전체탐색(exhaustive search)

가능한 모든 경우의 수를 모두 탐색하면서 요구조건에 충족되는 결과만을 가져온다.

1. Brute Force : for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법

2. 비트마스크

3. 순열 : 순열의 시간 복잡도는 O(N!)

4. 백트래킹

5. BFS : 그래프 이용

6. 재귀

 

브루트포스(brute-force search) 

완전탐색 알고리즘. 

=> 예외 없이 100%의 확률로 정답만을 출력 가능

문제 : 백준 덩치, 블랙잭, 분해합

* 암호학의 브루트 포스(brute force attack, 무차별 대입 공격)은 특정한 암호를 풀기 위해 가능한 모든 값을 대입하는 것을 의미

 

선형 구조를 모두 탐색 - 순차 탐색

비선형 구조를 모두 탐색 - BFS(넓이 우선 탐색), DFS(깊이 우선 탐색)

 

순차탐색(Sequential Search)

순차적으로 비교해가면서 찾는 것. 선형 구조를 전체적으로 탐색

문제 : 백준 한수?

 

DFS(Depth-First Search, 깊이 우선 탐색)

다음 branch로 넘어가기 전 해당 branch를 완벽하게 탐색

즉, 넓게(wide) 탐색하기 전에 깊게(deep) 탐색

 

- 자기 자신을 호출하는 순환 알고리즘의 형태 => 재귀적

- 전위 순회(Pre-Oreder Traversals)를 포함한 다른 형태의 트리 순회는 모두 dfs의 한 종류

- 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사(무한루프에 빠질 위험이 있으므로)

 

BFS(Breath-First Search, 너비 우선 탐색)

시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문

즉, 깊게(deep) 탐색하기 전에 넓게(wide) 탐색

- 재귀적X

- 그래프 탐색의 경우 어떤 노드를 방문했었는지 여부를 반드시 검사(무한루프에 빠질 위험이 있으므로)

Queue를 이용 => FIFO

 

 

*검색 속도 DFS보다 BFS가 좀 더 빠름

 

 

백트래킹(Backtracking)

조건을 만족하는 모든 경우를 탐색

DFS + 가지치기(Pruning, 갈 필요 없는 루트는 고려하지 않음)

문제 : No-Queen, 스도쿠