본문 바로가기
반응형

전체보기119

[Python] 최단 경로 - 다익스트라 알고리즘(Dijkstra's algorithm) 다익스트라 알고리즘 다익스트라 알고리즘은 그래프의 한 노드에서 다른 노드로 가는 최단 경로를 구하는 알고리즘이다. 그래프의 노드를 잇는 간선에는 거리 정보가 주어진다. 다익스트라 알고리즘은 이 거리가 양수여야 한다. 다익스트라 알고리즘 구현 1. 주어진 그래프 구현 2. 최단 거리 리스트를 생성 3. 최단 거리 리스트에서 가장 작은 값을 가지는 노드 선택 4. 최단 거리 리스트 업데이트 - 선택한 노드의 최단거리 + 도착 노드까지의 거리와 도착 노드의 최단거리를 비교해서 작은 값으로 도착 노드의 최단 거리를 업데이트 한다. 이 과정을 반복해서 최단거리 리스트를 업데이트한다. 효율적인 다익스트라 알고리즘을 구현하기 위해 우선순위 큐를 사용해서 구현한다. 파이썬의 heapq 모듈을 통해 우선순위 큐를 사용할.. 2022. 3. 28.
[LeetCode] #743. Network Delay Time (python) 문제 https://leetcode.com/problems/network-delay-time/ Network Delay Time - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com n개의 노드가 있는 네트워크가 있다. (출발지, 목적지, 소요 시간)이 주어진다. 주어진 노드 k에서 신호를 보낼 때 모든 n개의 노드에 신호를 보낼 때 걸리는 시간을 반환해야한다. 만약 모든 노드로 신호를 보내는 것이 불가능하면 -1을 반환하면 된다. 예시 입출력 Input: time.. 2022. 3. 23.
[LeetCode] #207. Course Schedule (python) 문제 https://leetcode.com/problems/course-schedule/ Course Schedule - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com [a, b] 형식으로 구성된 a를 끝내려면 b를 먼저 끝내야 된다는 코스 리스트가 있다. 코스 개수 n도 함께 입력 받는다. 주어진 모든 코스를 완료 가능하다면 True를 반환하고 그렇지 않으면 False를 반환해야 한다. 예시 입출력 Input: numCourses = 2, prerequisit.. 2022. 3. 17.
[LeetCode] #78. Subsets (python) 문제 https://leetcode.com/problems/subsets/ Subsets - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 모든 부분집합을 반환해야 한다. 예시 입출력 Input: nums = [1,2,3] Output: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]] 풀이 내 풀이 class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: outpu.. 2022. 3. 17.
반응형

티스토리툴바