![]()
문제 - n*n 그래프 / h : 사람 수 / m : 비를 피할 수 있는 칸 수- 0 : 이동 가능한 칸 / 1 : 이동 불가능한 칸 (벽) / 2 : 사람 서있는 칸 / 3 : 비를 피할 수 있는 칸- 출력값 : 각 칸마다 사람이 없었던 칸이면 0, 사람이 있었던 칸이면 제일 가까운 비를 피할 수 있는 칸까지의 거리 출력 풀이 방식 def bfs(x, y): que = deque([(x, y, 0)]) visited = [[False] * n for _ in range(n)] visited[x][y] = True while que: x, y, dist = que.popleft() if graph[x][y] == 3: return dis..
![]()
문제 바람이 불어오는 방향과 행의 숫자가 주어지고만약 인접한 행의 같은 열에 같은 숫자가 있다면 반대 방향에서 바람을 불어오게 하면 된다.(바람이 분다 = 한 칸씩 밀어낸다)주어진 바람의 정보 수만큼 반복해서 진행한다. 풀이 방식def rotate(row, direction): if direction == 'L': tmp = graph[row][-1] for i in range(m-1, 0, -1): graph[row][i] = graph[row][i-1] graph[row][0] = tmp elif direction == 'R': tmp = graph[row][0] for i in range(m-1): ..
![]()
0/1 Knapsack Problem이란? 용량이 W인 배낭, N개의 물건(각 물건은 무게(w)와 가치(v)가 주어짐) 1. 배낭에 담을 물건의 무게의 합이 W를 초과하지 않으면서 2. 담을 수 있는 최대 가치를 찾는다. 물건을 쪼갤 수 있다면 > Fraction Knapsack Problem 물건을 쪼갤 수 없다면 > 0/1 Knapsack Problem 접근법 DP 중에서도 작은 문제의 해로 큰 문제의 해를 찾는 상향식 접근법을 사용한다. 그렇다면 점화식을 구해야 한다. 부분 문제를 정의해 보면, 물건을 담을 수 있는 경우와 담을 수 없는 경우로 나눌 수 있고 담을 수 있는 경우에는 물건을 넣기로 결정하거나 물건을 안 넣기로 결정하는 경우로 또 나눌 수 있다. 정리하면, 1. 물..
