네발로 코딩하는 포메라니안

1. 문제 https://www.acmicpc.net/problem/4485 4485번: 녹색 옷 입은 애가 젤다지? 젤다의 전설 게임에서 화폐의 단위는 루피(rupee)다. 그런데 간혹 '도둑루피'라 불리는 검정색 루피도 존재하는데, 이걸 획득하면 오히려 소지한 루피가 감소하게 된다! 젤다의 전설 시리즈의 주 www.acmicpc.net 2. 풀이과정 BFS를 사용한 이유 처음엔, dfs로 풀고 시간 초과가 났다. 생각해보니 이 문제는 가다가 해당 노드에 더 작은 비용으로 갈 수 있는 경우, 굳이 더 갈 필요가 없어서 버리기 때문에 bfs가 유리하다. dfs를 사용할 경우, 초반에 전체 탐색을 하기 때문에 시간 초과가 나는 것 같다. Priority Queue를 사용한 이유 bfs임에도 priority..

1. 우선 순위 큐 - 큐에 넣을 데이터들이 우선 순위가 있다. - 우선 순위가 높은 것부터 꺼낼 수 있도록 한다. 2. 구현 방법 1. 배열 배열로 구현할 때, 우선순위가 높을수록 배열의 앞에 위치시키며 아래와 같은 단점이 있다. 1) 데이터를 삽입 및 삭제할 때, 데이터를 한 칸씩 밀고 당겨야 한다. => 연산 증가 2) 삽입 위치를 찾기 위해 처음부터 하나씩 비교를 해야 한다. 2. 연결 리스트 연결 리스트로 구현할 때, 배열과 마찬가지로 우선순위가 높을수록 리스트 앞쪽에 위치시킨다. 배열의 첫 번째 단점은 없지만, 두 번째 단점은 여전히 존재한다. 따라서 우선순위 큐는 힙을 사용하는 경우가 많다. 3. 힙 힙은 우선순위를 고려한 '완전 이진 트리'이다. *완전 이진 트리 : 자식 subtree가 ..