[알고리즘 기본] 완전 탐색 (브루트 포스 Brute Force)

 

 

완전 탐색, 브루트 포스(Brute Force)

---

 

 

Brute Force 직역하면 짐승같은 힘, 무식한 힘이라는 뜻이다.

완전 탐색이라는 이름에서도 알 수 있듯이 하나부터 열까지 모든 경우를 다 탐색하는 알고리즘이다.

 

모든 경우를 탐색하니 당연히 정답을 찾을 수 있다.

 

 

완전탐색 예시

 

 

 

3자리로 구성된 자물쇠의 비밀번호를 찾기 위해

000 ~ 999까지 모든 경우의 수를 입력해보는 것을 생각하면 이해하기 쉽다.

999까지 입력할 것을 생각하면 벌써부터 몸살이 난다.

왜냐? 더럽게 오래 걸리기 때문이다. (This is 경험담)

 

여기서 완전탐색 알고리즘의 장점과 단점을 알 수 있다.

 

 

 

완전탐색 장점 & 단점

 

장점

• 모든 경우를 다 고려하기 때문에 확실한 정답을 찾을 수 있다.
• 복잡한 알고리즘 없이 빠르게 구현이 가능하다.

 

단점

• 모든 경우를 다 고려하기 때문에 효율적이지 못하다.
• 알고리즘 실행시간이 오래 걸린다.

 

 

그리디 알고리즘으로 풀 수 있는 최소 동전 개수 구하기 문제를 생각해보자.

그리디 알고리즘은 값의 가치가 가장 큰 동전부터 채워서 주면 된다.

(최소 동전개수 채우기는 그리디 알고리즘을 사용할 수 있는 조건을 만족한다)

 

완전탐색은 거스름돈을 거슬러주기 위한 동전의 경우의 수를 모두 구할 것이다.

그러면 시간이 배로 배로 걸린다.

 

일머리가 있느냐 없느냐의 차이로 생각하면 알고리즘의 이해도가 더 올라간다.

하여튼 나보단 빠르지만 다른 알고리즘들보단 느리다.

상황에 맞는 알고리즘이 있는 것이다.

 

 

 

 

완전탐색 종류

---

 

 

1. 브루트 포스(Brute Force)

조건문을 이용해 모든 경우의 수를 찾는 방법이다.

 

2. 비트마스크 (Bit Mask)

2진수인 컴퓨터의 연산을 이용하는 방법이다.

 

3. 순열

완전 탐색의 대표적인 유형이다.

순열은 서로 다른 N개에서 r개를 뽑아 한 줄로 세우는 경우의 수를 말한다.

 

4. 백트래킹

현재 상태에서 가능한 후보군으로 가지를 치며 탐색하는 방법이다.

 

5. DFS/BFS

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

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

 

 

 

1번 이외의 것들은 아직 공부를 하지 않았다.

차차 정리해 나갈 예정이다! 🏆

 

 

 

 

 

완저탐색 예시코드 (브루트 포스)

---

 

예시로 위에 1번인 브루트 포스(Brute Force)에 대한 백준 문제이다.

백준 2798번 : 블랙잭

2798번: 블랙잭

 

 

풀이 코드

const fs = require('fs');
const input = fs.readFileSync('dev/stdin').toString().trim().split('\n');

let num = input.shift().split(' ').map(Number);
let n = num[0];
let m = num[1];
let nums = input[0].split(' ').map(Number);

function blackJack(n, m) {
    let result = 0;
    for (let i = 0; i < n - 2; i++) {
        for (let j = i + 1; j < n - 1; j++) {
            for (let k = j + 1; k < n; k++) {
                let sum = nums[i] + nums[j] + nums[k];
                if (sum > result && sum <= m) {
                    result = sum;
                }
            }
        }
    }
    return result;
}

console.log(blackJack(n, m))

 

HOW? (풀이방법)

 

브루트 포스답게 모든 경우의 수를 구해야 한다.

반복문을 돌려서 나올 수 있는 경우의 수를 모두 계산한다.

카드 3개의 조합을 구하기 때문에 for문 중첩을 3번 돌린다.

 

for중첩을 2번까지는 써봤는데 3번이나 쓰려니까 처음에는 이게 뭐요 싶었다.

하지만 실행되는 것들을 출력해보니 이해가 갔다.

 

 

예를 들어 5종류의 카드 5,6,7,8,9와 3장을 뽑아 더한 최대합이 21이라고 했을 때

위의 for문을 돌리면 아래와 같이 모든 경우의 수를 확인할 수 있다.

 

 

 

[0] 5 + [1] 6 + [2] 7 = 18

[0] 5 + [1] 6 + [3] 8 = 19

[0] 5 + [1] 6 + [4] 9 = 20

[0] 5 + [2] 7 + [3] 8 = 20

[0] 5 + [2] 7 + [4] 9 = 21

[0] 5 + [3] 8 + [4] 9 = 22

[1] 6 + [2] 7 + [3] 8 = 21

[1] 6 + [2] 7 + [4] 9 = 22

[1] 6 + [3] 8 + [4] 9 = 23

[2] 7 + [3] 8 + [4] 9 = 24

 

 

 

 

 

 

 

Reference(참조)

 

https://intrepidgeeks.com/tutorial/algorithm-complete-navigation-technology

https://hongjw1938.tistory.com/78

https://velog.io/@sangbooom/JS-BFS-DFS

https://saegeullee.github.io/algorithm/bfs-dfs