1. 브루트 포스

• 브루트 포스는 모든 경우의 수를 다 해보는 것이다
• e.g. 비밀번호가 4자리이고, 숫자로만 이루어져 있다고 한다면
  • 0000부터 9999까지 다 입력해보면 된다.
  • 경우의 수가 10,000가지 이다
  • 사람이 직접 비밀번호를 입력하는데 1초가 걸린다면 10,000초 = 2.7시간 정도 걸린다
• e.g. 비밀번호가 12자리이고, 숫자로만 이루어져 있다고 한다면
  • 000000000000부터 999999999999까지 다 입력해보면 된다.
  • 경우의 수가 1,000,000,000,000가지 이다.
  • 사람이 직접 비밀번호를 입력하는데 1초가 걸린다면 1,000,000,000,000초 = 약 31688년이 걸린다

이 때, 경우의 수를 다 해보는데 걸리는 시간이 문제의 시간 제한을 넘지 않아야 한다

브루트 포스로 문제를 풀기 위해서는 다음과 같은 3가지 단계를 생각해볼 수 있다.

1. 문제의 가능한 경우의 수를 계산해본다.
   • 직접 계산을 통해서 구한다. 대부분 손으로 계산해볼 수 있다
2. 가능한 모든 방법을 다 만들어본다.
   • 하나도 빠짐 없이 만들어야 한다.
   • 대표적으로 그냥 다 해보는 방법, for문 사용, 순열 사용, 재귀 호출 사용, 비트마스크 사용이 있다
3. 각각의 방법을 이용해 답을 구해본다.
   • 이 단계는 보통은 어렵지 않다. 문제에 나와있는 대로 답을 계산해본다

브루트 포스 문제의 시간 복잡도는 대부분 O(경우의 수 * 방법 1개를 시도해보는데 걸리는 시간 복잡도)가 걸린다

1. 일곱 난쟁이 - 2309

• 일곱 난쟁이 📚 https://www.acmicpc.net/problem/2309

python

1
import sys
2

3
# 입력받은 숫자의 개수
4
n = 9
5

6
# 입력받은 숫자 리스트
7
a = [int(input()) for _ in range(n)]
8

9
# 숫자 리스트 정렬
10
a.sort()
11

12
# 숫자 리스트의 합
13
total = sum(a)
14

15
# 두 개의 숫자를 선택하여 합이 100이 되는 경우를 찾는 반복문
16
for i in range(0, n):
17
    for j in range(i + 1, n):
18
        # 합이 100인 경우
19
        if total - a[i] - a[j] == 100:
20
            # 두 개의 숫자를 제외한 나머지 숫자를 출력하는 반복문
21
            for k in range(0, n):
22
                # 이미 출력한 숫자이거나 선택한 두 개의 숫자일 경우 continue
23
                if i == k or j == k:
24
                    continue
25
                # 출력
26
                print(a[k])
27
            # 종료
28
            sys.exit(0)