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

완전 탐색이란?

 

가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법

'무식하게 푼다'라는 의미로 Brute-Force 라고 하기도 한다.

 

 

완전 탐색 기법

 

완전 탐색 방법을 이용하기 위해서 여러가지 알고리즘 기법이 이용된다.

 

-단순 Brute-Force

-비트마스크(Bitmask)

-재귀 함수

-순열 (permutation)

-BFS / DFS (너비 우선 탐색 / 깊이 우선 탐색)

 

 

1. 단순 Brute-Force

 

단순히 for문과 if문 등으로 모든 case들을 만들어 답을 구하는 방법

 

2. 비트마스크

 

2진수를 이용하는 컴퓨터의 연산을 이용하는 방식

 

3.재귀 함수

 

재귀 함수를 통해서 문제를 만족하는 경우들을 만들어가는 방식

 

4.순열

 

서로 다른 N개를 일렬로 나열하는 순열의 경우의 수는 N 이므로 

완전 탐색을 이용하기 위해서는 N이 한자리 수 정도는 되어야함

순열에 원소를 하나씩 채워가는 방식이며, 재귀 함수를 이용하거나 C++ 에서는 next_permutation이라는

유용한 함수를 제공한다.

 

5. BFS/DFS

 

대표적인 유형으로 길 찾기 문제가 있다.