브루트 포스
브루트 포스는 가능한 모든 경우의 수를 다 시도해보면서 문제를 푸는 방식이다. 이때, 경우의 수를 모두 해보는데 걸리는 시간이 문제의 제한시간을 넘기지 않아야 한다.
예시) 숫자로만 이루어진 n자리 비밀번호 알아내기
| 비밀번호의 자리수 | 가능한 범위 | 경우의 수 | 입력 하나에 1초로 따진 소요시간 |
| 4자리 | 0000 ~ 9999 | 10000가지 | 10000초 = 약 2.7시간 |
| 5자리 | 00000 ~ 99999 | 100000가지 | 100000초 = 약 1일 3시간 |
| 6자리 | 000000 ~ 999999 | 1000000가지 | 1000000초 = 약 11일 12시간 |
| 12자리 | 000000000000 ~ 999999999999 | 1000000000000가지 | 1000000000000초 = 약 31688년 |
브루트 포스로 문제를 풀기 위한 방법
1. 문제의 가능한 경우의 수를 계산해본다.
- 직접 손으로 계산해본다.
2. 가능한 모든 방법을 다 만들어본다.
- 하나도 빠짐 없이 만들어야 한다.
- 대표적인 방법으로 for문 사용, 순열 사용, 재귀 호출 사용, 비트마스크 사용이 있다.
3. 각각의 방법을 이용해 답을 구해본다.
- 브루트 포스 문제의 시간 복잡도는 O(경우의 수 * 방법 1개를 시도해보는 걸리는 시간복잡도)가 걸린다.
브루트 포스 문제
https://www.acmicpc.net/problem/2309
2309번: 일곱 난쟁이
아홉 개의 줄에 걸쳐 난쟁이들의 키가 주어진다. 주어지는 키는 100을 넘지 않는 자연수이며, 아홉 난쟁이의 키는 모두 다르며, 가능한 정답이 여러 가지인 경우에는 아무거나 출력한다.
www.acmicpc.net
https://www.acmicpc.net/problem/3085
3085번: 사탕 게임
예제 3의 경우 4번 행의 Y와 C를 바꾸면 사탕 네 개를 먹을 수 있다.
www.acmicpc.net
https://www.acmicpc.net/problem/1476
1476번: 날짜 계산
준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타
www.acmicpc.net
https://www.acmicpc.net/problem/1107
1107번: 리모컨
첫째 줄에 수빈이가 이동하려고 하는 채널 N (0 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 고장난 버튼의 개수 M (0 ≤ M ≤ 10)이 주어진다. 고장난 버튼이 있는 경우에는 셋째 줄에는 고장난 버튼
www.acmicpc.net
https://www.acmicpc.net/problem/14500
14500번: 테트로미노
폴리오미노란 크기가 1×1인 정사각형을 여러 개 이어서 붙인 도형이며, 다음과 같은 조건을 만족해야 한다. 정사각형은 서로 겹치면 안 된다. 도형은 모두 연결되어 있어야 한다. 정사각형의 변
www.acmicpc.net
'🧑💻코딩 테스트 > 알고리즘' 카테고리의 다른 글
| [코딩테스트/알고리즘] 그래프(Graph) - 그래프의 표현 (0) | 2022.12.09 |
|---|---|
| [코딩테스트/알고리즘] 그래프(Graph) - 그래프 종류, 그래프 용어 (0) | 2022.10.27 |
| [코딩테스트/알고리즘] 다이나믹 프로그래밍(Dynamic Programming) (0) | 2022.08.29 |
| [코딩 테스트/알고리즘] 알고리즘 공부 시작 (0) | 2022.06.29 |
댓글