Algorithm15 [백준]1516. 게임개발 (python) 문제 게임개발 https://www.acmicpc.net/problem/1516 문제 유형 topology sort + dp dp 미리 건설해야 하는 건물들(진입 차수)이 여러 개라면 각각에 소요되는 시간의 비교를 수행해야 함 # 게임개발 # https://www.acmicpc.net/problem/1516 import sys, collections N = int(input()) graph = collections.defaultdict(list) # pre_table = collections.defaultdict(list) indegree = [0] * (N + 1) time = [0] * (N + 1) for idx in range(1, N + 1): temp = list(map(int, input().. 2023. 7. 9. 위상정렬(topology sort) 위상 정렬 이란? 정렬 알고리즘의 일종으로 방향 그래프의 모든 노드들을 간선의 방향을 거스르지 않으며, 순서대로 나열하는 것을 말한다. 이 때, 우리에게 주어지는 방향 그래프는 사이클을 형성하지 않는 단방향 비순환 그래프(DAG, Directed Acyclic Graph) 일 것이다. 위상 정렬 구현 위상 정렬을 구현하기 위해서 모든 노드의 진입 차수를 나타내는 배열과 큐 자료구조를 활용한다. 참고로 스택을 활용할 수도 있다고 한다. 구현 로직을 살펴보면 bfs 형태인 것 같다. 진입 차수 레벨에 따라서 큐에 다음 방문 노드를 저장해둔다. 반복문을 통해서 큐에 존재하는 노드를 하나씩 꺼내어 결과 배열에 삽입한다. 그래프 탐색을 통해 방문한 노드로부터 다음에 방문하게 될 노드들을 찾아, 이들의 진입 차수를.. 2023. 7. 8. 743. Network Delay Time 743. Network Delay Time class Solution { private int[][] graph; private int[] visited; public int networkDelayTime(int[][] times, int n, int k) { this.makeGraph(times, n); this.visited = new int[n+1]; int answer = -1; Queue pq = new PriorityQueue(Comparator.comparingInt(p -> p[0])); pq.offer(new int[]{0, k}); while(!pq.isEmpty()) { var next = pq.poll(); if (visited[next[1]] != 0) continue; else .. 2023. 5. 15. [해시] 베스트앨범 해시 | 베스트앨범 두어 달 전에 풀었던 코드 굉장히 조잡한 절차적 코드...! import java.util.*; import static java.util.stream.Collectors.*; import java.util.LinkedList; class Solution { public int[] solution(String[] genres, int[] plays) { int[] answer = {}; Map map = new HashMap(); int len = genres.length; for (int i = 0; i < len; i++) { ArrayList tmp = map.getOrDefault(genres[i], new ArrayList()); // tmp.add(i); map.put(ge.. 2021. 12. 16. 이전 1 2 3 4 다음