[백준BOJ] 단계별로 문제풀기 - 브루트 포스 정답 및 후기(파이썬, python)

백준 알고리즘에서 제공되는 문제들 중 단계별로 문제 풀기 - 브루트 포스를 파이썬으로 풀어보았다. 코드는 5문제 통째로 깃허브에 올려놓았으며 각 문제마다 주석으로 표시해놨다.

 

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

브루트 포스 단계

원본 코드는 깃허브에!

github.com/tomy9729/Algorithm/blob/master/BaekJoon/Step-by-step%20troubleshooting(%EB%8B%A8%EA%B3%84%EB%B3%84%EB%A1%9C%20%EB%AC%B8%EC%A0%9C%ED%92%80%EA%B8%B0)/11.%20%EB%B8%8C%EB%A3%A8%ED%8A%B8%ED%8F%AC%EC%8A%A4

tomy9729/Algorithm

 

0. 전체 후기

브루트 포스란 무차별 대입이다. 모든 경우의 수를 확인해본다. 브루트 포스에서는 어느 한 경우도 빼놓지 않고 확인하는 것이 중요하다. 단 이러한 점이 문제를 풀면서 굉장히 비효율적이라고 느꼈다. 2중 반복문은 기본이고 4중 반복문까지 사용하였다. 비효율적인만큼 아이디어는 어렵지 않았다.

 

1. 2798번 블랙잭

3중 for문으로 풀었으며 한 숫자를 중복해서 더하면 안되는 점에 주의해야 한다.

#2798번 블랙잭
n,m = input().split()
n = int(n)
m = int(m)
nums = []
ans = 0

nums = input().split()

for i in range(n) : 
  nums[i] = int(nums[i])

for i in range(n) : 
  for j in range(i+1,n) : 
    for l in range(j+1,n) : 
      if nums[i]+nums[j]+nums[l] <= m and nums[i]+nums[j]+nums[l] > ans : 
        ans = nums[i]+nums[j]+nums[l]

print(ans)

 

2. 2231번 분해합

최솟값을 구하기 때문에 1부터 1씩 증가시키며 분해합을 구하여 입력받은 n과 분해합이 같을 때 반복문을 중단시키도록 했다. 분해합을 구하는 과정은 % 연산자와 //연산자를 통해 구했다. 반복문이 끝까지 돌면 생성자가 존재하지 않기 때문에 이 때는 0을 출력하도록 했다.

#2231번 분해합
n = int(input())

for i in range(n) : 
  temp = i
  ans = i
  while temp > 0 : 
    ans += temp%10
    temp = temp//10

  if ans == n : 
    break
  
if i == n-1 : 
  print(0)
else : 
  print(i)

 

3. 7568번 덩치

중복 등수가 허용돼서 더 쉬운 문제였다. 덩치가 더 큰 기준은 키와 몸무게가 더 클 때이다. 어떤 사람에 대해서 반복문을 돌며 그 사람보다 덩치가 큰 사람이 존재할 때마다 등수를 높였다. 

#7568번 덩치
n = int(input())
weight = [0]*n
height = [0]*n
rank = [1]*n

for i in range(n) :
  weight[i],height[i] = input().split()
  weight[i] = int(weight[i])
  height[i] = int(height[i])
  rank[i] = 1

for i in range(n) : 
  for j in range(n) : 
    if weight[i] < weight[j] and height[i] < height[j] : 
      rank[i] += 1

for i in range(n) : 
  print(rank[i],end=' ')

 

4. 1018번 체스판 다시 칠하기

무려 4중 for문이다. 이 코드를 짜고서 정답을 확인할 때 시간 초과가 나지 않은 것을 확인하고 '원래 이렇게 푸는 문제구나...' 생각했다. 처음에는 그나마 효율적으로 짜고 싶어서 체스판과 가장 유사한 8*8 부분만 떼 오고 싶었는데 좋은 아이디어가 떠오르지 않아 그냥 브루트 포스로 풀었다. 입력받은 보드에서 왼쪽 위부터 8*8씩 가져와서 체스판과 일일이 비교하였다. 

이 문제를 풀면서 zip이라는 것에 대해서 처음으로 알게 되었다. 앞으로 필요할 때마다 유용하게 사용할 수 있을 것 같다.

#1018번 체스판 다시 칠하기
import sys
n,m = input().split()
n = int(n)
m = int(m)
min = sys.maxsize

wb = [['W','B','W','B','W','B','W','B'],['B','W','B','W','B','W','B','W'],['W','B','W','B','W','B','W','B'],['B','W','B','W','B','W','B','W'],['W','B','W','B','W','B','W','B'],['B','W','B','W','B','W','B','W'],['W','B','W','B','W','B','W','B'],['B','W','B','W','B','W','B','W']]
bw = [['B','W','B','W','B','W','B','W'],['W','B','W','B','W','B','W','B'],['B','W','B','W','B','W','B','W'],['W','B','W','B','W','B','W','B'],['B','W','B','W','B','W','B','W'],['W','B','W','B','W','B','W','B'],['B','W','B','W','B','W','B','W'],['W','B','W','B','W','B','W','B']]

board = [[0]*m for i in range(n)]
temp = [[0]*8 for i in range(8)]

for i in range(n) : 
  board[i] = input() 

for i in range(n-7) : #체스판은 8*8이기 때문에 오버플로우 하지 않기 위함
  for j in range(m-7) : 
    count_wb = 0
    count_bw = 0
    for x,a in zip(range(i,i+8),range(8)) : 
      for y,b in zip(range(j,j+8),range(8)) : 
        temp[a][b] = board[x][y]
    for c in range(8) : 
      for d in range(8) : 
        if temp[c][d] != wb[c][d] : #체스판으로 존재 할 수 있는 두 가지 체스판과 전부 비교
          count_wb += 1
        if temp[c][d] != bw[c][d] : 
          count_bw += 1
    if min > count_wb : 
      min = count_wb
    if min > count_bw : 
      min = count_bw

print(min)

 

5. 1436번 영화감독 숌

처음에는 main함수만 작성하려고 했는데 is_end_num함수를 작성하는 게 훨씬 깔끔해 보여서 함수를 분리했다. is_end_num함수는 입력받은 숫자를 단위마다 나누어서 리스트로 저장한 뒤 6이 연속으로 세 번 있는지 확인하는 함수다. 그나마 효율적으로 작성하고 싶어서 반복문은 666부터 시작하도록 했다.

#1436번 영화감독 숌
def is_end_num(num) : #종말의 숫자인지 확인
  num_list = []
  while num : 
    num_list.append(num%10)
    num = num//10
  for i in range(len(num_list)-2) : 
    if num_list[i] == 6 and num_list[i+1] == 6 and num_list[i+2] == 6 : #숫자 세개가 연속으로 6이면 True 반환
      return True

n = int(input())
count = 0  
num = 666

while count < n : 
  if is_end_num(num) : 
    count += 1
  num+=1
print(num-1)