백준 단계별로 풀어보기!! - 브루트 포스

https://www.acmicpc.net/step/22

브루트 포스 단계

---

1. 브루트 포스(Brute Force)란?

 

 전체 대입이란 말과 동의어로 쓰이며, 모든 경우의 수를 대입해보는 것을 말한다. 요컨대, 노가다인 것이다...!! Brute: 짐승(같은 자) Force: 힘이라는 뜻으로, 이 알고리즘은 예외 없이 100%의 정답률이 장점이다.

하지만, 모든 수를 대입하다보니 자연스레 발생하는 브루트 포스의 문제점은 시간이다. 조금만 정답의 범위가 넓어지거나 정답을 찾는데 제약이 걸리면 정답을 도출하기까지의 시간이 큰 단위로 늘어나는 것이다.

 

2. 브루트 포스로 블랙잭 구현하기!

https://www.acmicpc.net/problem/2798

2798번: 블랙잭

 블랙잭이란, 카지노에서 행해지는 게임 중 하나이다. 카드의 도합이 21을 넘지 않는 선에서 카드의 합을 가장 21과 가깝게 만드는 사람이 승리하는 게임이다. 여기서 구현할 블랙잭은 조금 변형된 블랙잭으로, 양의 정수가 적혀있는 카드에서 딜러가 N장의 카드를 보이게 놓는다. 그 후 딜러가 특정 숫자(M)를 외치면, 플레이어는 놓인 카드들 중에서 3장을 뽑아 그 합이 M을 넘지 않는 가장 가까운 숫자를 만들면 되는 것이다. 

코드부터 확인하면 다음과 같다.

 

n, m = map(int, input().split())
card = list(map(int, input().split(' ')))
ans = 0

for a in range(0, n - 2):
    for b in range(a + 1, n - 1):
        for c in range(b + 1, n):
            if card[a] + card[b] + card[c] > m:
                continue
            else:
                ans = max(ans, card[a] + card[b] + card[c])
print(ans)

 

 첫 줄은 파이썬 내장 함수인 map으로 두 개의 숫자(n, m)을 입력받는다. 그 후 카드의 숫자들을 입력을 받고 card라는 변수에 리스트 형식으로 저장해준다. 삼중 for문을 만들어 카드 리스트의 숫자를 뽑아 더했을 때 m을 넘으면 넘어가고(continue) 아니면 최대치를 뽑아주는 if문을 작성해준다.

 

2. 브루트 포스로 분해합 구하기!

https://www.acmicpc.net/problem/2231

2231번: 분해합

 

 분해합이란, 어떤 자연수 n이 있을때, n의 분해합은 n과 n을 이루는 각 자릿수의 합을 의미한다. 이때 어떤 자연수 n을 생성자라고 한다. 예를 들어, 216의 분해합은 2+1+6+216 = 225인 것이다. 여기서 216은 225의 생성자인 것이다. 다음은 어떤 자연수가 주어졌을 때, 생성자를 구하는 코드이다.

 

n = int(input())
res = 0
for i in range(1, n+1):
    div = list(map(int, str(i)))
    sum_num = i + sum(div)
    if(sum_num == n):
        res = i
        break
print(res)

 

 첫 줄엔 자연수를 입력받는다(n). 그리고 생성자가 없는 경우에는 0을 출력해야하기에 res = 0으로 시작을 한다. 반복문을 통해 1부터 입력받은 숫자 n까지 돌린다. 이때 돌아가며 들어오는 숫자 i의 구성을 div라는 리스트에 저장해준다. 예컨대, 13이 i로 들어오면, 13을 문자열로 바꿔 1과 3으로 나눈 후 숫자형으로 재변환해 리스트에 저장해주는 것이다. 그 후, 들어온 숫자와(i) 그 구성의 합인 sum(div)이 n과 같으면 (n에 대한 생성자) res를 i로 바꿔준다. 그리고 res를 출력하면 된다.

 

3. 브루트 포스로 덩치 등수 나열하기!

https://www.acmicpc.net/problem/7568

7568번: 덩치

 

 A의 키와 몸무게가 모두 B보다 크면 A는 B보다 덩치가 크다고 할 수 있다. K명의 사람의 키와 몸무게가 주어질 경우, 자신보다 덩치가 큰 사람이 존재한다면 자신의 등수는 K+1이 된다. 이러한 정보를 바탕으로 키와 몸무게를 입력받아 순위를 매겨보자.

 

per_num = int(input())
dung = []
for i in range(per_num):
    w, h = map(int, input().split())
    dung.append((w, h))
for per in dung:
    rank = 1
    for per2 in dung:
        if per[0] < per2[0] and per[1] < per2[1]:
            rank += 1
    print(rank, end=' ')
    

 

 사람 수를 첫 줄에 per_num으로 입력을 받고 키와 몸무게 목록인 dung을 빈 리스트로 만든다. 그 후 줄 별로 키와 몸무게를 입력받기 위해 반복문을 사용한다. 그 후 이중 반복문을 통해 몸무게를 비교한다. 매 비교 시마다 나(per)보다 다음 사람(per2)이 덩치가 크면 rank에 +1을 해준다. 그리고 print의 end=' '를 이용해 \n별로 출력하는 게 아니라 띄어쓰기 별로 출력한다.

 

4. 브루트 포스로 체스판 칠하기!

https://www.acmicpc.net/problem/1018

1018번: 체스판 다시 칠하기

 

 체스판은 8 x 8 칸으로 검은색과 흰색이 위, 아래, 좌, 우가 번갈아가면서 칠해져 있다. 입력으로 검은색과 흰색이 랜덤 하게 칠해져 있는 n x m 개의 보드가 주어졌을 때, 최소 몇 개를 칠해야 체스판을 만들 수 있는지 구하는 문제이다. 정답 코드는 다음과 같다. 

 

n, m = map(int, input().split())
chess_list = []
for row in range(n):
    chess_list.append(input())
cnt_min = 64

for i in range(n - 7):
    for j in range(m - 7):
        cntW = 0
        for k in range(i, i + 8):
            for s in range(j, j + 8):
                if k % 2 == 0 and s % 2 == 0:
                    if chess_list[k][s] == 'B':
                        cntW += 1
                elif k % 2 == 1 and s % 2 == 1:
                    if chess_list[k][s] == 'B':
                        cntW += 1
                elif k % 2 == 0 and s % 2 == 1:
                    if chess_list[k][s] == 'W':
                        cntW += 1
                elif k % 2 == 1 and s % 2 == 0:
                    if chess_list[k][s] == 'W':
                        cntW += 1
        cntB = 0
        for k in range(i, i + 8):
            for s in range(j, j + 8):
                if k % 2 == 0 and s % 2 == 0:
                    if chess_list[k][s] == 'W':
                        cntB += 1
                elif k % 2 == 1 and s % 2 == 1:
                    if chess_list[k][s] == 'W':
                        cntB += 1
                elif k % 2 == 0 and s % 2 == 1:
                    if chess_list[k][s] == 'B':
                        cntB += 1
                elif k % 2 == 1 and s % 2 == 0:
                    if chess_list[k][s] == 'B':
                        cntB += 1
        cnt_min = min(cnt_min, cntW, cntB)
print(cnt_min)

 첫 파트에는 보드를 구성하는 것(가로 - 세로 크기, 흰색, 검은색이 칠해진 상태)들로 인풋을 받는다. 그 후 보드의 시작점을 이중 for문으로 구성한다. 그다음엔 맨 처음이 W(흰색)인 경우와 B(검은색)인 경우 둘로 나누어 이중 for문을 작성한다. 이중 for문 안에는 각 칸의 x축과 y축의 index를 짝, 홀 총 4가지 경우로 나누어 (짝, 짝), (홀, 홀)이 처음과 다르거나 (짝, 홀), (홀, 짝)이 처음과 같으면 바꾸는 횟수를 1씩 늘려주는 방식으로 작성하였다. 그러고 나서 W로 시작한 경우, B으로 시작한 경우, 전체 다 바꿀 때 최대 횟수(cnt_min = 64) 중 가장 작은 수를 출력해준다.

5. 브루트 포스로 악마의 숫자 순서 구하기!

https://www.acmicpc.net/problem/1436

1436번: 영화감독 숌

 

 흔히 666은 악마의 숫자로 불리는 수이다. 이 문제는 악마의 숫자가 포함된 수들에서 n번째 수를 찾는 문제이다. 예를 들어 1번째 악마의 수는 666이 포함된 제일 작은 수인 666이고, 2번째는 1666, 3번째는 2666,..., 7번째는 6660, 8번째는 6661 이런 식으로 나아가는 것이다. 이 역시 브루트 포스로 구현이 가능하다.

 

n = int(input())
order = 0
last_num = 666
while True:
    if '666' in str(last_num):
        order += 1
    if order == n:
        print(last_num)
        break
    last_num += 1

 

 666부터 1씩 올려가며 숫자를 센다. 다만, 숫자 안에 666이 포함되면 order(순서)를 1 올리고, order와 입력받은 n이 같으면 1씩 올려가며 세던 수를 출력하는 구조이다.