개인적으로 굉장히 풀기 싫고, 제일 어려운 유형이라고 생각한다.
까딱 잘못하면 스스로 함정에 들어가버리게 되기 때문이다.
브루트 포스 관련 문제
17614번 - 369
1436번 - 영화감독 숌
1018번 - 체스판 다시 칠하기
28215번 - 대피소
2531번 - 회전 초밥
브루트 포스
브루트 포스는 모든 경우의 수를 다 따지며 해를 찾는 방식이다.
알고리즘이라기 보다는 DP와 같은 문제 풀이 방식이라 보면 된다.
한 블로그에 쓰인 글에 의하면 "문제를 풀다보면 무식하게 풀어볼까? 라는 생각이 들 때가 있습니다. 그런 경우 사용하는 방법이 바로 브루트 포스 입니다." 라고 한다.
또 브루트 포스 방식으로 문제를 풀 때 순열/조합으로 답을 구할때가 많은 듯하다.
그렇다고 반드시 순열, 조합을 사용해서 푸는 건 아니고 ① 무식 반복 ② 순열/조합 중 효율적인 방법을 따라가는 것 같다.
순열 조합 사용 방법은 이전에 블랙잭 문제를 풀며 정리한 적 있다!
[BOJ] 2798 - 블랙잭
문제 풀이
1. 369
n = int(input())
clapCnt = 0
clabable = ['3', '6', '9']
map(lambda x: x==j, clabable)
for i in range(1, n+1):
number = str(i)
clapCnt += number.count('3')
clapCnt += number.count('6')
clapCnt += number.count('9')
print(clapCnt)어쭙잖게 직접 구현하지 말고 내장 함수를 적극 활용하자.
그거 좋은거다.
2. 영화감독 숌
n = int(input())
num = 666
ans = num
while n - 1:
num += 1
if '666' in str(num):
ans = num
n -= 1
print(num)이 코드는 내가 푼건 아니고 구글링으로 찾은 풀이다.
참고 자료 링크에서 자세히 확인할 수 있다.
처음에 이 문제를 풀때는 번호를 찾는 규칙이 있다고 단정 지어버려서 큰 고난을 겪었다..
"어떻게하면 적은 반복 횟수로 효율적으로 풀 수 있을까?"가 문제를 풀 당시에 머리에 박혀 있었는데
전혀 그럴 필요가 없었다는게 아직도 충격적이다.
3. 체스판 다시 칠하기
n, m = map(int, input().split())
chess = [0]*n
rows = n - 8 + 1
cols = m - 8 + 1
locmin = 100000000
globalmin = 100000000
for i in range(n):
chess[i] = list(input())
for cnt in range(2):
change = [[0]*cols for _ in range(rows)]
bw=['B', 'W', 'B', 'W', 'B', 'W', 'B', 'W']
if cnt!=0:
bw=bw[::-1]
for row in range(rows):
cpyrow = chess[row: row+8]
for col in range(cols):
for i in range(8):
cpycol = cpyrow[i][col: col+8]
for j in range(8):
if cpycol[j]!=bw[j]:
change[row][col]+=1
bw=bw[::-1]
locmin = min(change[row])
if locmin<globalmin:
globalmin = locmin
print(globalmin)이거 푸느라 정신 나가는 줄 알았다.
그래도 스스로 풀어낸 나 자신 아주 칭찬해 ㅎㅎ
너무 무식하게 풀어서 풀고 나서도 과연 통과가 될까 싶었는데 오히려 시간이 얼마 안걸려서 당황스러웠다.
4. 대피소
해당 문제는 서브태스크가 있는 문제이다.
아래 코드는 40점 짜리 코드이다.
아무래도 for 문을 삼중으로 써서 100점은 못받은 듯 하다.
from itertools import combinations
from itertools import product
n, k = map(int, input().split())
locations = [0]*n
for i in range(n):
x, y = map(int, input().split())
locations[i] = (x, y)
shelters = list(combinations(locations, k)) # 모든 대피소 위치 경우의 수
globalMin = 10000000000 # 전체 거리 중 최소
for shelter in shelters: # 대피소 경우의 수 중 하나 선택
newlocations = list(set(locations) - set(shelters)) # 대피소 아닌 집의 위치
locMax = 0 # 집 사이의 거리 중 최대
for loc in newlocations: # 한 집에 대해서 연산
houseMin = 10000000000
for sh in shelter: # 대피소 중 하나 선택
distance = abs(loc[0] - sh[0]) + abs(loc[1] - sh[1])
if houseMin > distance: # 대피소 중 가까운 대피소 거리를 저장
houseMin = distance
if locMax < houseMin: # 여러 집의 집-대피소 거리 중 최대값 저장
locMax = houseMin
if globalMin > locMax: # 집-대피소 최대 거리중 작은 거리를 저장
globalMin = locMax
print(globalMin)
인줄 알았으나 아주 사소한 실수로 시간 초과 된거였다.
15번째 줄의 shelters를 shelter로 바꾸면 된다.
ㅋㅋ... ㅋㅋㅋㅋㅋㅋㅋㅋ
from itertools import combinations
from itertools import product
n, k = map(int, input().split())
locations = [0]*n
for i in range(n):
x, y = map(int, input().split())
locations[i] = (x, y)
shelters = list(combinations(locations, k)) # 모든 대피소 위치 경우의 수
globalMin = 10000000000 # 전체 거리 중 최소
for shelter in shelters: # 대피소 경우의 수 중 하나 선택
newlocations = list(set(locations) - set(shelter)) # 대피소 아닌 집의 위치
locMax = 0 # 집 사이의 거리 중 최대
for loc in newlocations: # 한 집에 대해서 연산
houseMin = 10000000000
for sh in shelter: # 대피소 중 하나 선택
distance = abs(loc[0] - sh[0]) + abs(loc[1] - sh[1])
if houseMin > distance: # 대피소 중 가까운 대피소 거리를 저장
houseMin = distance
if locMax < houseMin: # 여러 집의 집-대피소 거리 중 최대값 저장
locMax = houseMin
if globalMin > locMax: # 집-대피소 최대 거리중 작은 거리를 저장
globalMin = locMax
print(globalMin)내가 했던 멍청한 실수에 대해 조금 더 설명하자면
shelters는 대피소로 선택될 수 있는 모든 경우의 수를 저장하고 있고,
14번째 줄에서는 그런 경우의 수를 하나씩 shelter로 가져온다.
15번째 줄에서는 locations(전체 집의 좌표) - shelter(대피소의 좌표)를 하고 있는데, 이는 앞으로의 연산에서 중복되는 좌표가 없게끔 하기 위함이다. shelter: ((x1, y1), (x2, y2)) 구조
그런데 이전의 코드에서는 이를 shelters: 모든 경우, [((x1, y1), (x2, y2))] 구조로 해주었으니 중복되는 값을 제대로 빼주지 못해 시간 초과가 난 거였다.
멍청한 짓 하지 말자
5. 회전 초밥
import sys
n, d, k, c = map(int, input().split())
belt = [0]*n
for i in range(n):
belt[i] = int(sys.stdin.readline())
maxCount = 0
for i in range(n):
if i+k > n-1:
eats = belt[i:] + belt[:(i+k)-n]
else:
eats = belt[i:i+k]
eats = set(eats)
cnt = len(eats)
if c not in eats:
cnt += 1
if maxCount < cnt:
maxCount = cnt
print(maxCount)체스판 다시 칠하기 문제와 결이 비슷하다고 느꼈다.
벨트에 놓인 초밥 하나를 리스트 한 칸으로 생각하고 벨트 리스트를 채운다.
회전초밥이므로, 리스트의 끝과 처음이 이어져있어야 함을 명심하자.
느낀점
알고리즘 문제를 어느정도 풀게 되면서 언제부턴가 규칙을 찾아 빠르게 푸는게 무조건 좋은 방법이라고 은연중에 생각했던 것 같다.
그러나 문제를 풀다보면 문제 자체를 푸는것 자체가 힘든 경우가 있다. 위의 관련 문제들이 그렇다.
효율적인 방법을 생각하다 도저히 안되겠으면 무식하게 풀어버리는 것도 오히려 좋은 방법일 수 있다는 것을 느꼈다.
참고 자료
05. 브루트 포스
01. 영화감독 숌[백준 1436]
[백준] 1018번: 체스판 다시 칠하기 - 파이썬(Python)
[백준 1018][파이썬] 체스판 다시 칠하기
👍👍👍언니 완전 열심히 하넹