[Algorithm] 완전탐색

1. 완전탐색

1) 개념 : 말 그대로 가능한 모든 경우의 수를 다 탐색하는 것 

2) 방법 

ⓐ 브루트 포스(Brute-Force) : 영어를 번역하면 무차별 대입이라는 뜻이다.

ⓑ 비트마스크(BitMask) : 이진수를 사용하는 컴퓨터의 연산 방식을 이용하여, 정수의 이진수 표현을 자료 구조로 쓰는 기법

ⓒ 순열

ⓓ BFS(너비우선탐색)

ⓔ 백트래킹 : DFS에 가지치기를 통해 가도되지 않는 루트는 고려하지 않고 탐색하는 완전탐색 기법 

<출처 : 브랜든의 블로그 :: [알고리즘] 완전탐색 (tistory.com)>

 

2. 해결방법

1) 주어진 문제를 선형 구조로 구조화

2) 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색

3) 구성된 해를 정리

EX) 10의 약수구하기

- 10의 약수가 될 수있는 모든 자연수를 구조화 (1,2,3,4,5,6,7,8,9,10}

- 탐색을 이용하여 첫번째 원소부터 마지막 원소까지 탐색 (1,2,5,10)

- 해 정리 {1,2,5,10}