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

✅완전탐색이란?

완전 탐색이란 문제 해결을 위해 모든 경우의 수를 다 시도하는 방법이다. 

Brute Force는 Brute(단순히, 순전히)와 Force(힘)이란 단어의 조합으로 직역하면 단순히 힘만 가지고 밀어 붙인다는 의미이다. 

이는 컴퓨터로 해킹을 할 때, 개인의 정보에서 유추된 것 없이 모든 가짓수를 다 시도하여 해킹하는 방법에서 유래되었다고 한다. 

 

흔히 자물쇠를 풀 때 0000~9999까지 모든 방법을 다 동원하는 방식으로 설명된다. 

 

✅완전탐색 구현 방식

1. For, while 문

: 반복문을 사용하여 처음부터 끝까지 모든 가짓 수를 시도한다. 

 

2. 재귀함수

: 재귀함수를 활용하여 반복문의 사용을 줄이고, 효율적으로 완전탐색을 시도할 수 있다. 

재귀함수(자기 자신을 호출하는 함수)를 활용하면 같은 명령을 내리는 하위 반복문을 피하고, 효율적으로 완전 탐색을 수행할 수 있다.

재귀함수를 만들 때에는 탈출할 방법을 만드는 것이 중요함.

 

3. 순열(Permutaion)

: 주어진 수 중 일부(또는 전체)를 사용하여 만들 수 있는 조합의 수 

조합(Combination)에서는 만들어진 각 조합의 구성 요소가 같으면 한 가지 조합으로 취급하지만 순열을 조합하는 순서에 따라 다른 조합으로 취급함. 

 

4. 비트마스크 

: 비트 리스트를 만들어 문제를 해결하는 방법

비트리스트란 각 원소에 해당하는 상태를 0과 1로 표현한 리스트를 의미한다. 

예를 들어, [1,3,4,2,5] 라는 숫자가 주어졌을 때, 각각의 원소가 [1,3,5] 라는 리스트에 포함되는 여부를 가진 리스트로 표현한다. 

[1,3,4,2,5]의 비트리스트는 [1,1,0,0,1] 이 될 것이다. 

이런 비트리스트를 연산에 활용하는 방법이다. 

 

5. 백트래킹

현재 상태에서 가능한 모든 후보군을 탐색하다가 가능성이 없는 해라고 판단되면 그 해를 버리는 것. 

--> 깊이 우선 탐색(DFS)에 대한 이해가 먼저 필요하므로 다음에 설명하기로!

 

✅ 완전탐색 대표 문제 : 프로그래머스 소수찾기 python 풀이

 

문제설명

문제 풀이 포인트

1. 주어진 숫자로 조합하여 만든 모든 조합을 만든다 (완전탐색)

2. 만들어진 숫자가 소수인지 아닌지 파악한ㄷ. 

 

문제 해결 방식 

1. 순열을 이용하여 모든 조합을 생성한다.

- itertools의 permutation활용

2. 재귀함수를 이용하여 모든 조합이 만들어지도록 한다. 

 

*풀이 영상:  https://www.youtube.com/watch?v=m3kCKV8oc1g

 

*Reference

알고리즘 - 완전탐색(Exhaustive Search) https://hongjw1938.tistory.com/78

[알고리즘]완전탐색 https://brenden.tistory.com/10

3분이면 브로트 포스 완전이해 https://www.youtube.com/watch?v=ZNa9-86uVEA