브루트포스 알고리즘?

브루트(Brute): 무식한
포스(Force): 힘
"무식하게 탐색한다"

일일히 모든 경우의 수를 대입해보는 노가다
전체 탐색 알고리즘이라고도 불린다

브루트포스의 치명적인 단점
▶ 문제의 복잡도에 매우 민감하다
▶ 탐색하고자 하는 값의 범위가 넓을 경우, 알고리즘 실행시간이 오래 걸린다.

백준 2798 블랙잭

백준 2798 링크

문제 요약

• 양의 정수가 쓰여있는 N장(3 <= N <= 100)의 카드가 있다.
• N장의 카드 중 3장을 뽑고, 뽑은 3장의 카드의 합을 출력해라.
• 이때 3장의 카드의 합은 M을 넘지 않으면서 M과 최대한 가까운 값이어야 한다.
• 단, 10 <= M <= 300,000

문제 접근

두가지 방법으로 접근해보았다.

M을 넘지 않은 카드 합(sum)들 중, 최대값을 출력

1. total이라는 빈 리스트를 만들고, 뽑은 3장의 카드를 합한 값이 M을 넘지 않을 경우 그 합을 total 리스트에 append 한다.
2. total에 append된 모든 값들 중, 최대값을 출력한다.

카드 합이, M을 넘지 않고 이전에 나온 카드 합보다 큰 경우에만 갱신해줌으로써 최종 카드 합을 출력한다.

1. total이라는 변수를 만든다. 해당 변수에는 조건에 만족하는 최종 카드 합이 계속 갱신되어 넣어진다.
2. 카드 합이 갱신되는 조건: 현재 sum(카드 합)이 M을 넘지 않으면서 이전에 나온 카드 합(total)보다 큰 경우 total = sum을 해줌으로써 total을 갱신한다.
3. 모든 경우를 탐색 후, 가장 마지막으로 total변수에 저장된 값이 최종 답

파이썬 코드

1번

N, M = map(int, input().split())
cards = list(map(int, input().split()))
total = []
for i in range(N):  # 첫번째 카드 뽑기
    for j in range(i+1, N):  # 두번째 카드 뽑기 (i카드 이후부터 뽑기)
        for k in range(j+1, N):  # 세번쨰 카드 뽑기 (j카드 이후부터 뽑기)
            sum = cards[i] + cards[j] + cards[k]
            if sum <= M:
                total.append(sum)
print(max(total))

2번

N, M = map(int, input().split())
cards = list(map(int, input().split()))
total = 0
for i in range(N):
    for j in range(i+1, N):
        for k in range(j+1, N):
            sum = cards[i] + cards[j] + cards[k]
            if (sum <= M) & (sum > total):
                total = sum
print(total)

1번은 시간이 108ms 나왔고,
2번은 시간이 80ms 나왔다.

결론: 2번 코드가 더 효율적이다.

백준 2231 분해합

백준 2231 링크

문제 요약

• N(1 <= N <= 1000000)이 주어졌을 때, N의 가장 작은 생성자 M을 구해라
• 예를 들어 N = 216일 때 216(=198+1+9+8)이므로 N의 가장 작은 생성자는 198

문제 접근

"어떤 자연수의 경우에는 생성자가 없을 수도 있고, 생성자가 여러 개일 수도 있다"라는 말이 처음에는 이해가 안갔다.
예시로,

• 어떤 자연수의 경우에는 생성자가 여러 개일 수 있다 : 101은 생성자가 2개(91과 100)
• 어떤 자연수의 경우에는 생성자가 없을 수 있다 : 1,3,5,7,9,20,31...은 생성자가 없다

1. N을 각 자릿수로 분리하고, 각 자릿수의 합을 생성자와 더해 num_sum에 저장한다
2. num_sum이 N과 같을 경우, 해당 생성자를 출력하고 탐색을 종료한다
3. 탐색이 끝난 후에도 num_sum == N에 해당하는 생성자 값을 못찾으면 0을 출력한다

파이썬 코드

N = int(input())  

for i in range(1, N+1):   # i = N의 모든 생성자 (i = 198일 때)
    num = sum((map(int, str(i))))  # i의 각 자릿수를 더함 (num = 1+9+8 = 18)
    # print(map(int, str(i))) = [1,9,8]
    num_sum = i + num  # 분해합 = 생성자 + 각 자릿수의 합  (num_sum = 198 + 18 = 216)
    # 처음으로 분해합과 입력값이 같을때가 가장 작은 생성자
    if num_sum == N:  # if 216 == 126
        print(i)
        break
else:  # for반복문이 다 돈 후에도 num_sum == N에 해당하는 i값을 못찾으면
    print(0)

백준 19532 수학은 비대면 강의입니다.

백준 19532 링크

문제요약

• a,b,c,d,e값이 주어질 때, 알맞은 x와 y값을 구하는 문제

문제접근

처음에는 크래머 공식으로 간단하게 풀려고 했으나 해당 문제는 브루트포스 알고리즘을 기반으로 풀라고 출제한 문제였기에..(왜냐하면 범위도 ~999~1000으로 좁게 나와서) for문으로 x와 y룰 -999 ~ 1000까지 모두 대입해보는 코드를 구현했다.

파이썬 코드

a,b,c,d,e,f = list(map(int,input().split()))
values = []

# 대입 노가다 (x와 y를 -999부터 1000까지 모두 대입)
for x in range(-999, 1000):
    for y in range(-999, 1000):
        if a*x + b*y == c:
            values.append([x,y])

# 1행에서 얻은 x,y 묶음을 2행의 방정식에 대입해보면서 최종 해 찾기
for xy in values:
    if d*xy[0] + e*xy[1] == f:
        print(xy[0], xy[1])
        break