self.winter.(09). 완전탐색 preview. [브루트포스, 백트래킹, BFS/DFS, 비트마스크]

🧐 완전 탐색 (Exhaustive Search)

🤫 완전 탐색이란?

이름에서도 알 수 있듯 하나부터 열까지 모든 경우를 다 탐색하는 알고리즘이다.
모든 경우를 탐색하니 당.연.히 정답을 찾을 수 있다.

장점: 모든 경우를 고려해서 정답을 확실히 찾을 수 있으며 복잡하지 않고 빠르게 구현이 가능
단점: 당연하게도 모든 경우를 다 찾기에 효율적이지 않고 실행시간이 오래걸린다.

🤫  완전탐색의 종류 

🤔브루트포스(https://www.acmicpc.net/step/22)
- 조건문/반복문을 이용해 모든 경우의 수를 찾는 방법
- https://chan4im.tistory.com/119

브루트 포스 단계

 

🤔백트래킹(https://www.acmicpc.net/step/34)
- 현재 상태에서 가능한 후보군으로 가지를 치며 탐색하는 방법

백트래킹 단계

 

🤔BFS,DFS(https://www.acmicpc.net/workbook/view/1833)

- BFS(너비 우선 탐색): 정점과 같은 레벨에 있는 형제노드를 탐색

- DFS(깊이 우선 탐색): 정점의 자식노드들을 탐색

아래 문제집에서는 완전탐색의 유명한 예시인 순열도 포함되어 있다.
순열과 조합 : (https://buyandpray.tistory.com/52)

문제집: DFS, BFS 추천문제 (c3171700)

 

🤔비트마스크(https://www.acmicpc.net/workbook/view/804)
- 2진수인 컴퓨터의 연산을 이용하는 방법

문제집: 비트마스크 (cokcjswo)