11월
알고리즘 재활치료
1) 이진탐색
백준 10815 : 숫자카드
import sys
N = int(sys.stdin.readline().strip())
lst = list(map(int,sys.stdin.readline().strip().split()))
lst.sort()
M = int(sys.stdin.readline().strip())
mlst = list(map(int,sys.stdin.readline().strip().split()))
for i in range(M): #M번의 이진탐색
start = 0
last = N-1
c = 0
while(start <= last):
c = int((start + last) / 2)
if mlst[i] < lst[c]:
last = c - 1
elif mlst[i] == lst[c]:
break
else:
start = c + 1
if mlst[i] == lst[c]: #찾은 수가 mlst 안에 있을 시
print("1", end=" ")
else:
print("0", end=" ")
이진탐색 알고리즘의 반복문의 조건이 while (start <= last) 라는 것을 잊지말자
2) 백트래킹
백준 15666: N과M (12)
#백트래킹
import sys
n,m = map(int,sys.stdin.readline().strip().split())
lst = set(map(int,sys.stdin.readline().strip().split()))
num = list(lst)
num.sort()
stack = []
def back():
l = len(stack)
if l == m:
print(" ".join(map(str,stack)))
return
else:
for i in range(len(num)):
if l == 0 or num[i] >= stack[-1]:
stack.append(num[i])
back()
stack.pop()
back()
스택 자료구조를 사용하면 좀 더 쉽게 구현가능하다
3) DFS,BFS
BFS - 백준 2206 : 벽 부수고 이동하기
# BFS
import sys,copy
from collections import deque
n,m = map(int,sys.stdin.readline().strip().split())
lst = [[0]*n for _ in range(2)]
maplst = [0]*n
for i in range(n):
maplst[i] = list(map(int,sys.stdin.readline().strip()))
lst[0][i] = copy.deepcopy(maplst[i])
lst[1][i] = copy.deepcopy(maplst[i])
dx = [1,-1,0,0]
dy = [0,0,1,-1]
dq = deque()
dq.append((0,0,0))
lst[0][0][0] = 1
lst[1][0][0] = 1
while dq:
x,y,c = dq.popleft()
for i in range(4):
nx,ny = x+dx[i],y+dy[i]
if nx < m and nx >= 0 and ny < n and ny >= 0:
if c == 0: # 한 번도 벽 부순적 없을 때
if maplst[ny][nx] == 0 and lst[0][ny][nx] == 0:
lst[0][ny][nx] = lst[0][y][x] + 1
dq.append((nx,ny,0))
#lst[1][ny][nx] = lst[0][y][x] + 1
elif lst[1][ny][nx] == 1:
lst[1][ny][nx] = lst[0][y][x] + 1
dq.append((nx,ny,1))
else: # 벽 이미 한 번 부순 후
if maplst[ny][nx] == 0 and lst[1][ny][nx] == 0:
lst[1][ny][nx] = lst[1][y][x] + 1
dq.append((nx,ny,1))
a = lst[0][n-1][m-1]
b = lst[1][n-1][m-1]
if a == 0 and b == 0:
print(-1)
elif a == 0 and b != 0:
print(b)
elif a != 0 and b == 0:
print(a)
else:
print(min(a,b))
BFS는 큐를 이용하면 구현이 편해진다
4) DP
백준 12865 : 평범한 배낭
# DP 이용 배낭문제 풀이
import sys
n,k = map(int,sys.stdin.readline().strip().split())
lst = []
for i in range(n):
lst.append(list(map(int,sys.stdin.readline().strip().split())))
lst.sort()
dp = [[0]*(k+1) for _ in range(n)]
for i in range(n):
w,v = lst[i][0],lst[i][1]
for j in range(1,k+1):
if j-w >= 0:
if i == 0:
dp[i][j] = v
else:
dp[i][j] = max(v,dp[i-1][j-w] + v,dp[i-1][j])
else:
if i > 0:
dp[i][j] = dp[i-1][j]
print(dp[-1][-1])
사실 어떻게 풀었는지 기억이 잘 안난다
5) 구현
백준 26006 : K-Queen
import sys
n,k = map(int,sys.stdin.readline().strip().split())
queen = []
check = [False]*9
king_y,king_x = map(int,sys.stdin.readline().strip().split())
king = [[0,0],[1,0],[-1,0],[0,1],[0,-1],[1,1],[1,-1],[-1,1],[-1,-1]]
for i in range(9):
king[i][0] += king_x
king[i][1] += king_y
for i in range(k):
y,x = map(int,sys.stdin.readline().strip().split())
queen.append([x,y])
for i in range(9):
king_x,king_y = king[i][0],king[i][1]
if king_x <= 0 or king_y <= 0 or king_x > n or king_y > n:
check[i] = True
else:
for j in range(len(queen)):
queen_x,queen_y = queen[j][0],queen[j][1]
if king_x == queen_x or king_y == queen_y:
check[i] = True
elif king_x - king_y == queen_x - queen_y or king_x + king_y == queen_x + queen_y:
check[i] = True
if check[0] == 1:
if 0 in check:
print('CHECK')
else:
print('CHECKMATE')
else:
if check.count(0) == 1:
print('STALEMATE')
else:
print('NONE')
홍익대학교 프로그래밍 경진대회 오픈 콘테스트 문제였다.
이걸 구현하는데 시간이 너무 오래 걸려서 다른 문제도 못 풀었다.
체스판을 탐색하는 알고리즘은 그냥 외워두는게 좋을 것 같다.
'백준 플레를 향해서' 카테고리의 다른 글
플레찍었으니 정리해보는 알고리즘 노트 2 - 중간에서 만나기, 투 포인터 (0) | 2023.02.06 |
---|---|
플레찍었으니 정리해보는 알고리즘 노트 1 - 이진탐색 (0) | 2023.02.05 |
백준 플레를 향해서 - 12월 넷,다섯째주(12.19~12.31) (1) | 2023.01.01 |
백준 플레를 향해서 - 12월 셋째주(12.12~12.18) (0) | 2022.12.18 |
백준 플레를 향해서 - 12월 둘째주(12.5~12.11) (2) | 2022.12.11 |