[5문제] 완전탐색 문제풀이 05
백준 1543번
해결 아이디어
파이썬의 replace()
를 사용했다. replace는 문자열 왼쪽부터 시작해서 바꾸고자 하는 문자가 나올 경우 대체해준다. 위 방법으로 중복되지 않게 최대로 구할 수 있었다.
내가 작성한 코드
doc = input()
search = input()
doc = doc.replace(search,'X'*len(search))
print(doc.count('X'*len(search)))
백준 1018번
해결 아이디어
시간도 오래 걸리고, 꽤나 애를 먹은 문제였다. 우선적으로 MxN 크기의 보드에서 8x8 크기의 체스판의 개수를 확인해준다. 그 체스판의 개수대로 검은색을 다시 칠하는 경우와 흰 색을 다시 칠하는 경우로 나뉘어 더 최소 개수로 칠하는 경우를 구해준다. 이때, 검은색을 다시 칠해주는 경우를 구했다면, 흰색은 정반대의 경우이기 때문에 총 64개의 정사각형 타일에서 검은색을 다시 칠해주는 경우를 빼주면 된다.
내가 작성한 코드
n, m = map(int,input().split())
board = [input() for _ in range(n)]
chess = []
for a in range(n-7):
for b in range(m-7):
check_w_condition = 0
check_b_condition = 0
for i in range(a, a+8):
for j in range(b, b+8):
if (i+j) % 2 == 0:
if board[i][j] != 'W':
check_w_condition += 1
else:
if board[i][j] != 'B':
check_w_condition +=1
chess.append(min(check_w_condition, 64 -(check_w_condition)))
print(min(chess))
백준 14501번
해결 아이디어
다이나믹 프로그래밍을 활용하는 문제였던 것 같다. 다이나믹 프로그래밍이 뭔지 몰라서 개념부터 공부하고 왔다. 문제의 적용해보기에는 아직 이해가 안되서 타인의 코드를 읽어보았다. 역시나 이해가 안됐다. 문제를 다시 풀어보고 이해가 될 때 코드를 올려놓으려고 한다.
백준 10974번
해결 아이디어
파이썬 itertools
모듈에는 순열을 계산해주는 permutations
이라는 메소드가 있다. 그 메소드는 튜플 형식으로 출력을 해주기 때문에 출력 내용에 맞게 변형을 해주면서 문제를 쉽게 해결할 수 있었다.
내가 작성한 코드
from itertools import permutations
num = int(input())
count = list(permutations(range(1,num+1),num))
for i in range(len(count)):
for j in range(num):
print(count[i][j], end=' ')
print()
백준 1057번
해결 아이디어
토너먼트의 규칙을 잘 이해하면 간단하게 해결 할 수 있는 문제였다. 다음 라운드에 올라가면 번호를 다시 매긴다. 그 번호는 자신이 배정받았던 번호에 2로 나눈 몫을 빼준 번호로 지정된다. 예를 들어서 7번 참가자가 다음 라운드에 올라가게 된다면, 다음 라운드 4번을 배정받고 그 다음 라운드는 2번, 마지막 라운드는 1번을 배정받게 되는 것이다. 그 과정을 반복하면서 두 수가 같아졌을 때, 대결이 성사가 된다.
이때 임한수와 김지민은 서로 대결하기 전까지 항상 이긴다고 가정했으므로, 서로 대결하지 않을 경우는 토너먼트 특성상 존재하지 않는다. 따라서 서로 대결하지 않을 때 -1을 출력하는 경우는 따로 구현하지 않았다.
내가 작성한 코드
n,kim,lim = map(int,input().split())
count = 0
while kim != lim:
kim-= kim//2
lim-= lim//2
count+=1
print(count)
Author And Source
이 문제에 관하여([5문제] 완전탐색 문제풀이 05), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@m1njae/5문제-완전탐색-문제풀이-05저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)