[Algorithm] 브루트 포스 알고리즘
🌵 브루트포스 알고리즘(Brute Force Search)이란?
brute : 무식한 + force : 힘
brute force : 폭력
완전 탐색, 전체 탐색 알고리즘으로 불리며, 발생할 수 있는 모든 경우를 탐색한다.
쉽게 말해 4자리 비밀번호를 맞추기 위해 브루트포스 알고리즘을 사용하면,
0000부터 9999까지의 모든 숫자조합을 시도해 비밀번호를 찾는 것이다.
🌵 장점
- EASY
- 알고리즘을 설계, 구현하기가 매우 쉽다.
- 정답률 100%
- 해가 하나 이상 존재한다는 가정을 세우고 구현하므로, 100%의 확률로 정답을 찾을 수 있다.
🌵 단점
- 시간 초과 가능성
- 모든 경우를 탐색하므로 실행시간이 오래걸린다.
- 비효율적
- 메모리 효율측면에서 비효율적이다.
🌵 종류
브루트포스의 종류는 크게 두 가지로 분류된다.
1. 선형 구조 : 순차 탐색
2. 비선형 구조 : 백트레킹, 깊이 우선 탐색 (DFS, Depth First Search), 너비 우선 탐색 (BFS, Breadth First Search)
각각의 더 자세한 설명은 추후에 공부하고 추가하도록 하자!
- 순차탐색 (Sequential Search)
- 처음부터 끝까지 차례대로 비교하여 원하는 값을 찾아내는 알고리즘
- 단방향으로 탐색을 수행하기 때문에 선형 탐색(Linear Search)이라고도 불린다.
- 단순하지만, 비효율적
- 백트레킹 (Backtracking)
- 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법
- 즉, 모든 경우의 수들 중 특정 조건을 만족하는 경우만 살펴본다.
- 반복문의 횟수를 줄일 수 있다.
- 불필요한 부분을 쳐내고 최대한 올바른 쪽으로 간다는 의미로 가지치기라고도 불린다.
- 깊이 우선 탐색 (DFS, Depth First Search)
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색
- 말이 어려운데 이름 그대로 넓게 탐색하기 전에 깊게 탐색하는 것!
- 쉬운 예로 설명하면, 미로에서 길을 탐색할 때 한 방향으로 갈 수 있을 때까지 가다가 길이 막히면,
가장 가까운 갈림길로 돌아와 다른 방향의 길을 탐색하는 것이다.
- 너비 우선 탐색 (BFS, Breadth First Search)
- 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색
- 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나중에 방문하는 순회 방법
🌵 문제해결 방법
1. 주어진 문제를 선형 구조로 구조화
2. 구조화된 문제공간을 적절한 방법으로 해를 구성할 때까지 탐색
3. 구성된 해를 정리
브루트포스 알고리즘을 이욯한 문제들을 통해 이해하면 더 쉽게 이해할 수 있다.
🌵 관련 문제
[백준 알고리즘 2798번 : 블랙잭]
https://www.acmicpc.net/problem/2798
2798번: 블랙잭
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장
www.acmicpc.net
[SOLUTION]
https://gyurisinzorba.tistory.com/40
[Python] 백준 알고리즘 2798번 : 블랙잭
https://www.acmicpc.net/problem/2798 2798번: 블랙잭 첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지..
gyurisinzorba.tistory.com
[백준 알고리즘 2231번 : 분해합]
https://www.acmicpc.net/problem/2231
2231번: 분해합
어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이
www.acmicpc.net
[SOLUTION]
https://gyurisinzorba.tistory.com/41
[Python] 백준 알고리즘 2231번 : 분해합
https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한
gyurisinzorba.tistory.com
[백준 알고리즘 7568번 : 덩치]
https://www.acmicpc.net/problem/7568
7568번: 덩치
우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩
www.acmicpc.net
[SOLUTION]
https://gyurisinzorba.tistory.com/42
[Python] 백준 알고리즘 7568번 : 덩치
https://www.acmicpc.net/problem/7568 7568번: 덩치 우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치
gyurisinzorba.tistory.com
[백준 알고리즘 1436번 : 영화감독 숌]
https://www.acmicpc.net/problem/1436
1436번: 영화감독 숌
666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라는 시리즈 영화의 감독이다. 조지 루카스는 스타
www.acmicpc.net
[SOLUTION]
https://gyurisinzorba.tistory.com/43
[Python] 백준 알고리즘 1436번 : 영화감독 숌
https://www.acmicpc.net/problem/1436 1436번: 영화감독 숌 666은 종말을 나타내는 숫자라고 한다. 따라서, 많은 블록버스터 영화에서는 666이 들어간 제목을 많이 사용한다. 영화감독 숌은 세상의 종말 이라
gyurisinzorba.tistory.com
