WIL - 다익스트라, 플로이드
1. 다익스트라 공부
https://jeojeo.tistory.com/144
다익스트라(Dijkstra) 최단경로 _이코테, 프로그래머스(가장 먼 노드)
하이구... 플로이드 와샬이 수월했다고 다익스트라도 괜찮을 줄 알았는데, 생각보다 어려웠다..😂 다익스트라.. 앞으로 이 친구도 많이 만나면서 친해져야겠다..ㅎㅎ 나동빈 저자의 <이것이 코
jeojeo.tistory.com
https://jeojeo.tistory.com/161
다익스트라 연습 - K경유지내 가장 저렴한 항공권
문제: https://leetcode.com/problems/cheapest-flights-within-k-stops/ 다익스트라 자체도 낯설고 어려운데, 이 문제는 적절히 가지를 쳐서 시간효율을 챙기지 않으면 리트코드에서 거절당하는 문제였다. 몇 번..
jeojeo.tistory.com
https://jeojeo.tistory.com/162
다익스트라 연습 - 화성탐사(이코테 39번)
1. 문제 2. 코드 import heapq import sys # n X n 의 탐사 지형(?) 정보 받아와서 2차원 배열로 그리기 n = int(sys.stdin.readline().rstrip()) graph = [[] for _ in range(n)] for i in range(n): row = list..
jeojeo.tistory.com
https://jeojeo.tistory.com/163
다익스트라 연습 - 숨바꼭질(이코테 40번)
import heapq import sys n, m = map(int, sys.stdin.readline().split()) con_info = [[] for _ in range(n+1)] for _ in range(m): s, e = map(int, sys.stdin.readline().split()) con_info[s].append(e) con_..
jeojeo.tistory.com
https://jeojeo.tistory.com/164
다익스트라 연습 - 네트워크 딜레이 타임
- 문제: https://leetcode.com/problems/network-delay-time/ - 코드 class Solution(object): def networkDelayTime(self, times, n, k): # 초기화에 사용할 큰 수 INF = int(1e8) # 각 노드 간 간선과 간선에..
jeojeo.tistory.com
https://jeojeo.tistory.com/165
다익스트라 연습 - 최단경로(백준 1753)
문제: https://www.acmicpc.net/problem/1753 다익스트라의 전형같은 문제! 코드 import heapq import sys n, m = map(int, sys.stdin.readline().split()) s = int(sys.stdin.readline().rstrip()) # 연결 정보..
jeojeo.tistory.com
2. 플로이드 워셜
https://jeojeo.tistory.com/141
플로이드-와샬 _ 그래프 최단거리
📝 플로이드 와샬(Floyd-Warshall) 알고리즘 경유지로 고려하는 대상(정점/도시)을 하나씩 늘려가면서! 그때마다의 최소거리(비용)를 갱신해가는 동적 프로그래밍 방식이다. 앞으로 다른 문제에서
jeojeo.tistory.com
https://jeojeo.tistory.com/142
플로이드 와샬 - 회장 뽑기 문제
import sys n = int(sys.stdin.readline().rstrip()) dy = [["M"]*n for _ in range(n)] # 자신과의 거리는 0 for i in range(n): dy[i][i] = 0 # 입력 라인이 -1 -1로 종료를 알릴 때까지 연결 정보를 받아온다...
jeojeo.tistory.com
https://jeojeo.tistory.com/166
플로이드-워셜 연습 - 정확한 순위(이코테 38)
이코테 38번 문제 학생 N명에 대한 성적을 분실했는데, 다만 두 명씩 성적을 비교한 결과 M 개가 있다. 예를 들어 1~6번 학생이 있는데, 1 < 5, 3 < 4, ... 이런 식으로 정보가 주어진다. 이 정보들만으
jeojeo.tistory.com
https://jeojeo.tistory.com/167
플로이드 워셜 연습 - 운동(백준 1956)
문제: https://www.acmicpc.net/problem/1956 이 문제에서 찾아야 하는 최단경로는, 출발지로 돌아와야 하는 순환경로라는 점이 다른 최단거리 구하는 점과 다르다. 처음에는 뭔가 복잡하게 접근할 뻔했는
jeojeo.tistory.com