Jinnie devlog Jinnie devlog

1697(숨바꼭질), 5014(스타트링크) 두 문제 모두 큐를 활용한 BFS 방식의 문제다. 이동할 수 있는 거리만큼의 for문을 돌며, 큐에 삽입하고 이동거리를 +1씩 해주며 최종 목적지의 이동거리를 구하였다. 똑같은 위치를 반복해서 방문하게 되면, 필요없는 작업을 하게되어 visited 배열을 통해 한번만 방문하도록 하였다. 백준 1697 숨바꼭질 from collections import deque def bfs(s): q = deque([s]) visited[s]=1 while q: cur = q.popleft() if cur == K: return count[K] for i in (cur-1, cur+1, cur*2): if 0

배낭 문제 배낭에 담을 수 있는 무게의 최댓값이 정해져 있고, 일정 가치와 무게가 있는 짐들을 배낭에 넣을 때 가치의 합이 최대가 되도록 짐을 고르는 방법을 찾는 문제이다. 배낭문제는 짐을 쪼갤 수 있는 경우(무게가 소수일 수 있는 경우)와 짐을 쪼갤 수 없는 경우(이 경우 짐의 무게는 0 이상의 정수만 가능) 두 가지로 나눌 수 있는데, 짐을 쪼갤 수 있는 경우의 배낭문제를 분할가능 배낭문제(Fractional Knapsack Problem), 짐을 쪼갤 수 없는 경우의 배낭문제를 0-1 배낭문제(0-1 Knapsack Problem)라 부른다. https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C 배낭 문제 - 위키백과, 우리 모두의..