반응형 Study/Algorithm38 [Algorithm] 유니온 파인드(Union-Find) 알고리즘 (python) 유니온 파인드 알고리즘 유니온 파인드 알고리즘은 이름 그대로 유니온 연산과 파인드 연산으로 구성되어 있는 알고리즘이다. 그래프에서 두 노드가 같은 그래프에 속해 있는지를 확인할 수 있다. 1. union 연산 두 노드가 속한 집합을 하나의 집합으로 합치는 연산이다. 2. find 연산 특정 노드가 속한 집합의 대표 노드를 반환하는 연산이다. 파이썬으로 유니온 파인드 알고리즘 구현하기 1. 1차원 리스트 사용 인덱스를 노드라고 생각하고 대표 노드 값을 리스트의 값으로 본다. 2. 2개의 노드의 집합을 하나로 합치는 union 연산 진행 두 노드를 합칠 때 두 노드의 리스트 값이 대표 노드가 아닌 경우가 있을 수 있다. 그럴 때 각 노드의 대표노드를 찾아서 대표 노드끼리 연결을 해야 한다. 3의 대표 노드가.. 2022. 12. 15. [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. 이전 1 2 3 4 5 6 ··· 10 다음 반응형
