[BAEKJOON] 완전탐색 뽀개기 | 파이썬 | 백준 Lv11. 브루트 포스 문제풀이

BAEKJOON 백준 코딩테스트 단계별로 풀어보기 > LEVEL 11 브루트 포스 https://www.acmicpc.net/step/22

브루트 포스 단계

 

완전 탐색(Brute-Force Search)이란

탐색 가능한 모든 경우의 수를 확인하여 답을 찾는 방법이다.

 

 

2798. 블랙잭

N과 M 두 자연수를 입력받는다. N은 카드의 개수이고 M은 카드의 합이 넘지 말아야할 최대의 수이다.

N장의 카드 중 3장을 골라 M에 최대한 가까운 수를 만들어 반환한다. 단 M을 넘어선 안된다.

 

내 코드) 메모리 42748mb / 시간 152ms

from itertools import combinations

answer = 0
n, m = map(int, input().split())
nums = list(map(int, input().split()))
orders = list(combinations(nums, 3)) # 나올 수 있는 모든 조합 저장

for order in orders[::-1]:
    s = sum(order)
    if s <= m: # 조건에 해당할 때
        answer = max(s, answer) # M보다 작은 수 중 가장 큰 수
        
print(answer)

문제의 주제가 완전탐색인 만큼 N장의 카드에서 3장 골랐을 때 나올 수 있는 조합의 모든 경우의 수를 구하여 조건에 맞는 답을 구하였다.

모든 조합의 수를 구할 때 파이썬의 itertools.combinations 라이브러리를 이용하였다.

 

* 순열과 조합의 차이는 순서 인정 여부에 있다.

예를 들어 숫자 (1, 1, 3)이 있을 때 순열의 경우, 처음 나온 1과 두번째의 1을 다른 1로 인식한다. 나올 수 있는 모든 경우의 수는 3x2x1로 6이다.

반면 조합은 앞의 1과 두 번째 1이 같은 1로 인식하고 나올 수 있는 경우의 수는 (3x2x1)/(2x1) 3이 된다. 

 

 

2231. 분해합

예를 들어 숫자 245가 있을  때 (245+2+4+5=)256은 245의 분해합이다. 245는 256의 생성자이다.

어떤 자연수 N이 주어졌을 때 N의 가장 작은 생성자를 반환한다. 생성자가 없을 경우 0을 반환한다.

 

내 코드1) 메모리 30864mb / 시간 1528ms

n = int(input())

for i in range(1, n+1):
    m, tmp = i, i
    while tmp != 0:
        m += (tmp%10)
        tmp //= 10
        
    if m == n:
        print(i)
        break
    if i == n:
        print(0)

N이 주어지면 1부터 N까지 N의 생성자인지 검사한다.

검사하는 숫자 tmp에 일의 자리 수를 계속 더하여 모든 자릿수를 더한다(분해합을 구한다). 분해합이 N이랑 같으면 반복을 멈추고 답을 반환한다.

 

더 간단한 코드로 수정) 메모리 30864mb / 시간 1248ms

n = int(input())

for i in range(1, n+1):
    m = i + sum(map(int, str(i)))
    if m == n:
        print(i)
        break
    if i == n:
        print(0)

앞서 값을 직접 10으로 나누면서 일의 자리를 더해갔는데 굳이 반복문을 돌지 않고 수를 문자열로 변환한 뒤 각 자리수를 정수형으로 변환하여 더해주었다. 아주 약간의 속도 향상이 있었다.

 

 

7568. 덩치

두 사람 A와 B가 있을 때 A의 키와 몸무게가 B의 키와 몸무게보다 클 때 A가 B보다 덩치가 크다고 할 수 있다.

N명의 집단에서 각 사람의 덩치 등수는 자신보다 더 큰 덩치의 사람의 수로 정해진다. 자신보다 덩치가 큰 사람이 k명이라면 그 사람의 덩치 등수는 k+1이 된다.

 

내 코드) 메모리 30864mb / 시간 68ms

n = int(input())
answer = [1 for i in range(n)]
info = []
for i in range(n):
    info.append(list(map(int, input().split())))

for i in range(n):
    for j in range(n):
        if (info[i][0] < info[j][0]) and (info[i][1] < info[j][1]):
            answer[i] += 1

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

쉬운 문제였다. 프로그래머스에 익숙한 나에게 백준은 문제도 문제지만.. 입력 받는 부분 코드 짜는게 더 어렵다..

먼저 등 수를 모두 1로 초기화해놓고 문제 조건에서 주어진 '덩치가 더 크다'조건에 맞는 사람이 있으면 등수를 증가시킨다. 수행 속도를 위해 이중 for문 쓰는걸 최대한 지양하려고 하는데 이 문제는 이중 for문을 사용하여야만 풀 수 있었다ㅠ

 

 

1018. 체스판 다시 칠하기

NxM 크기의 체스판에 색이 어떻게 칠해져있는지 알려주는 보드의 색 정보가 입력된다. 여기서 우리는 8x8 크기만 잘라 체스판을 만들려 한다.

체스판은 검정색(B)과 흰색(W)이 번갈아가며 나와야한다. 주어진 보드에서 어느 부분을 잘라야 최소한으로 색을 변경해 체스판을 완성할 수 있을까?

 

* 보드가 시작되는 가장 왼쪽 위의 칸의 색을 검정색(B) 또는 흰색(W) 중 하나를 선택할 수 있다.

따라서 체스판으로 자를 부분을 골랐을 때 첫번째 칸의 색에 따라 경우의 수가 2개 나온다.

 

내 코드) 메모리 30872mb / 시간 120ms

n, m = map(int, input().split())
board = []
answer = 100

for i in range(n):
    board.append(list(input()))

for i in range(0, n-7):
    for j in range(0, m-7):
        cnt1, cnt2 = 0, 0
        color1 = 'B'
        color2 = 'W'
        for k in range(i, i+8):
            for l in range(j, j+8):
                if ((k-i)+(l-j)) % 2 == 0 :
                    if board[k][l] != color1:
                        cnt1 += 1
                    if board[k][l] != color2:
                        cnt2 += 1
                else:
                    if board[k][l] == color1:
                        cnt1 += 1
                    if board[k][l] == color2:
                        cnt2 += 1
        
        answer = min(answer, min(cnt1, cnt2))
        
print(answer)

이중 for문을 돌며 체스판의 첫 시작을 어디로할지 고르고 해당 체스판에서 색을 몇 번 바꿔야하는지 두 경우의 수를 구한다.

첫 시작이 검정색일때와 흰색일 때 두가지 경우로 나누고 해당 색을 기준이 되는 색으로 정한다. 색이 번걸아 나와야함으로 시작 칸의 인덱스와 현재 검사하는 칸의 인덱스를 이용해 기준 색과 같아야하는지 달라야하는지 비교, 검사한다.

 

 

1436. 영화감독 숌

666은 종말을 나타내는 숫자라고 한다. 숌 감독은 멋져보이기위해 자신의 영화에 숫자 '666'을 포함하여 제목을 짓는다.

첫 번째 영화는 '세상의 종말 666', 두 번째 영화 제목은 '세상의 종말 1666', '세상의 종말 2666', ...

이렇게 적어도 3개 이상의 6이 연속적으로 나타나는 종말의 수가 포함되도록 영화 제목을 지을 때 N번째 영화 제목을 구하여라.

 

내 코드 1) 메모리 30864mb / 시간 1160ms

n = int(input())

answer, cnt = 1, 0
while True:
    
    if str(answer).find('666') != -1: 
        cnt += 1
    if cnt == n:
        print(answer)
        break
        
    answer += 1

N번째 영화를 찾아야함으로 1부터 계속 증가해가며 종말의 숫자 666이 들어갔는지 찾는다.

종말의 숫자가 나올때마다 카운트를 하고 카운트가 N이 될때 정답을 반환한다.

 

내 코드에서 살짝 수정) 메모리 30864mb / 시간 816ms

n = int(input())

answer, cnt = 1, 0
while True:
    
    if '666' in str(answer):
        cnt += 1
    if cnt == n:
        print(answer)
        break
        
    answer += 1

수행 속도가 너무 안좋은 것 같아서 다른 코드를 살짝 참고해봤더니 find() 메서드 대신 in 메서드를 쓰는걸 보고 수정해보았다.

시간이 좀 더 빨라졌다..!

 

 

백준 완전탐색 문제들은 난이도가 괜찮은 편이였다. 이제 프로그래머스 정복하러..~