[코드트리 조별과제] 5주차 학습

최근에 다시 알고리즘 공부를 하기 시작했습니다.

 

친구과 함께 하루에 백준에서 골드2문제를 랜덤으로 뽑아서 진행을 하고, 남은 시간에는 코드트리의 커리큘럼에 따라서 문제를 풀이하고 정리하려고 합니다. 

 

---

[코드트리] Intermediate Low / BFS / BFS탐색

 

문제는 단순하게 n * m 이차원 영역이 주어지고, 해당 영역에는 뱀이 서식합니다.

이 뱀들은 움직이지 않으며, 저희는 (0, 0) 지역에서 (n-1, m-1) 지역까지 이동할 수 있는지 판단내리면 됩니다.

 

[입력 범위]

2 <= n, m <= 100

[예제 입력 1]

5 5
1 0 1 1 1
1 0 1 0 1
1 0 1 1 1
1 0 1 0 1
1 1 1 0 1

[출력 1]

1

 

[정답 코드]

from collections import deque

n,m = map(int,input().split())

board =[[*map(int,input().split())]for _ in range(n)]

visited=[[0]* m for _ in range(n)]

visited[0][0] = 1
q = deque([[0,0]])
while q:
    x,y = q.popleft()
    for dx,dy in (0,1),(0,-1),(1,0),(-1,0):
        nx,ny = x + dx, y+dy
        if nx < 0 or nx >=n or ny < 0 or ny >=m:continue
        if not board[nx][ny] or visited[nx][ny]:continue
        visited[nx][ny] = 1
        q.append((nx,ny))
print(visited[n-1][m-1])

visited 배열을 0으로 초기화하고 bfs 돌린 후 배열을 출력하기만 하면 됩니다.

 

[코드트리] Intermediate Low / DP / 아이템을 적절히 고르는 문제

 

M원을 거슬러 줘야 할 때 N개 종류의 동전들로만 M원을 만드시오.

 

이 때 동전의 개수는 최소가 되도록 만드는 문제.

 

[입력 범위]

1 <= N <= 100, 1<= M <= 10, 000 

 

[예제 입력 1]

3 8
1 4 5

[출력 1]

2

 

[정답 코드]

n , m = map(int,input().split())
li = [*map(int,input().split())]

li.sort()

dp = [10001] * (m+1)
dp[0] = 0

for num in li:
    for i in range(num,m+1):
        dp[i] = min(dp[i], dp[i-num]+1)
result = dp[m]
print([result, -1][result == 10001])

 

마지막에 M값을 받아서 저런식으로 출력하는 것은 자주 사용되는 테크닉이다.

 

저렇게 하는 이유는 값이 값을 채울 수 없다면 -1을 출력해야 되는 문제이기에 저런식으로

 

dp의 값이 초기화되지 않은 점을 이용하는 풀이이다.