백준 플레를 향해서 - 11월~12월 첫째주(~12.4)

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')

홍익대학교 프로그래밍 경진대회 오픈 콘테스트 문제였다.

이걸 구현하는데 시간이 너무 오래 걸려서 다른 문제도 못 풀었다.

체스판을 탐색하는 알고리즘은 그냥 외워두는게 좋을 것 같다.