Goal
1. 브루트포스 알고리즘이 무엇인지에 대하여 정확히 이해한다.
2. 브루트포스 알고리즘이 쓰이는 문제의 종류에 대하여 정리한다.
브루트포스(brute force) 알고리즘이란?
브루트포스 알고리즘이란, 완전 탐색 알고리즘을 말한다.
즉, 가능한 모든 경우의 수를 탐색하면서 조건문을 통해서 요구조건이 충족되는 결과를 도출해 낸다.
모든 경우의 수를 탐색한다 -> 예외 없이 100%확률로 답을 가져올 수 있다.
- 알고리즘 설계의 가장 근본적인 방법은 해가 있을 곳을 예상해서 탐색하는 것이다.
- 브루트포스 알고리즘은 전체 구역을 탐색한다.
- 전체 구역을 탐색하는 방법은 선형구조를 전체 탐색하는 순차 탐색 (반복문을 통한 전체 순차 탐색), 비선형 구조를 전체 탐색하는 DFS(깊이 우선 탐색), BFS(너비 우선 탐색)의 방법이 있다.
보통 DFS는 백트래킹 기법 (브루트포스와 유사하지만, 백트래킹 기법은 가지치기 즉, 해당 부분에 해가 없을 것으로 판단되면 그 부분에 대한 탐색을 멈추는 기법을 말한다.)
BFS는 브루트포스에 많이 쓰인다.
이후 DFS와 BFS를 다룰 때 더 자세히 쓰도록 하겠다.
문제 해결 방법
문제의 데이터를 해를 적절히 찾을 때까지 전부 탐색한다.
예시 및 추천 문제
백준 - BOJ 단계별 문제 브루트포스
https://www.acmicpc.net/problem/2798
2798번: 블랙잭
첫째 줄에 카드의 개수 N(3 ≤ N ≤ 100)과 M(10 ≤ M ≤ 300,000)이 주어진다. 둘째 줄에는 카드에 쓰여 있는 수가 주어지며, 이 값은 100,000을 넘지 않는 양의 정수이다. 합이 M을 넘지 않는 카드 3장
www.acmicpc.net
https://www.acmicpc.net/problem/7568
7568번: 덩치
우리는 사람의 덩치를 키와 몸무게, 이 두 개의 값으로 표현하여 그 등수를 매겨보려고 한다. 어떤 사람의 몸무게가 x kg이고 키가 y cm라면 이 사람의 덩치는 (x, y)로 표시된다. 두 사람 A 와 B의 덩
www.acmicpc.net
문제 해결 과정은 업로드 예정!
위 문제들은 간단히 반복문만 돌려도 충분히 풀 수 있는 문제들이니 충분히 생각해보고 풀어봤으면 한다.
이 외에 브루트포스 문제 중 시간 제한 상 DFS,재귀를 써야하는 문제들은
백준
https://www.acmicpc.net/problem/16943
16943번: 숫자 재배치
두 정수 A와 B가 있을 때, A에 포함된 숫자의 순서를 섞어서 새로운 수 C를 만들려고 한다. 즉, C는 A의 순열 중 하나가 되어야 한다. 가능한 C 중에서 B보다 작으면서, 가장 큰 값을 구해보자. C는 0
www.acmicpc.net
https://www.acmicpc.net/problem/1527
1527번: 금민수의 개수
첫째 줄에 A와 B가 주어진다. A는 1보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다. B는 A보다 크거나 같고, 1,000,000,000보다 작거나 같은 자연수이다.
www.acmicpc.net
등이 있다.
'알고리즘' 카테고리의 다른 글
| [알고리즘] 다익스트라 알고리즘 (0) | 2022.08.02 |
|---|---|
| [알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS) 의 개념과 차이 (0) | 2022.06.27 |
| 정렬 알고리즘 정리 (0) | 2021.10.31 |
