본문 바로가기
728x90
반응형

다이나믹프로그래밍

Algorithm & Data Structure 2022. 11. 2. 백준 - 11404번(플로이드) https://www.acmicpc.net/problem/11404 import sys n = int(sys.stdin.readline()) m = int(sys.stdin.readline()) arr = [[float('INF') for _ in range(n)] for _ in range(n)] bus = [] for i in range(n): arr[i][i] = 0 for _ in range(m): a,b,c = map(int,sys.stdin.readline().split()) if arr[a-1][b-1] > c: arr[a-1][b-1] = c for k in range(n): for i in range(n): for j in range(n): if arr[i][j] > arr[i][k] +..
플로이드 워셜(Floyd Warshall) 알고리즘
Algorithm & Data Structure 2022. 11. 2. 플로이드 워셜(Floyd Warshall) 알고리즘 로봇공학을 공부하다가 알고리즘 파트가 나와서 공부해볼 겸 정리를 해본다. pdf에는 단순히 DP를 이용한 최단거리 탐색 이라고 적혀 있지만, 사실상 플로이드 워셜 알고리즘을 설명하고 있다. 최단 거리를 찾는 알고리즘의 일종이다. "거쳐가는 정점을 기준으로 최단거리를 구하는 것" DP를 이용한다. 이러한 그래프의 방문의 최적 비용을 2차원 테이블로 표현해 보자. 이는 현재까지 계산된 최소비용이다. 2열 3행은 2-> 3으로 가는 현재까지 계산된 최소비용이고, 이는 9이다. 무한으로 표시된 것은 한 번의 이동으로는 갈 수 없는 즉, 필연적으로 다른 노드를 거쳐야 하는 경우이다.(만약 연결된 노드가 없는 경우 못 갈 수도 있다.) 예를 들어 1->3으로 가는 경우는 1 -> 4 -> 3을 거쳐서 비용 11, ..
Algorithm & Data Structure 2022. 8. 14. 백준 - 12738(DP,LIS,이분탐색,bisect) https://www.acmicpc.net/problem/12738 12738번: 가장 긴 증가하는 부분 수열 3 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net from bisect import bisect_left import sys n = int(sys.stdin.readline()) arr = list(map(int, sys.stdin.readline().split())) dp = [] for i in arr: k = bisect_left(dp, i) if len(dp)
Algorithm & Data Structure 2022. 8. 6. 백준 - 9370번(다익스트라, DP) https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net import sys from collections import deque def dajik(st, ed): if st == ed: return 0 q = deque([]) q.append([0, st]) dist = [float('inf')] * (n + 1) while q: now_value, st = q.popleft() for i in arr[st]: if now_value + i[1]..
Algorithm & Data Structure 2022. 8. 6. 백준 - 1504번(다익스트라, DP) https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net import sys import heapq n,e = map(int,sys.stdin.readline().split()) arr = [[] for _ in range(n+1)] for _ in range(e): a,b,c = map(int,sys.stdin.readline().split()) arr[a].append([b,c]) arr[b].append..
Algorithm & Data Structure 2022. 5. 21. 백준 - 1446번(다익스트라, DP) https://www.acmicpc.net/problem/1446 1446번: 지름길 첫째 줄에 지름길의 개수 N과 고속도로의 길이 D가 주어진다. N은 12 이하인 양의 정수이고, D는 10,000보다 작거나 같은 자연수이다. 다음 N개의 줄에 지름길의 시작 위치, 도착 위치, 지름길의 길이 www.acmicpc.net import sys n,d = map(int,sys.stdin.readline().split()) arr = [] for i in range(n): arr.append(list(map(int,sys.stdin.readline().split()))) arr.sort(key= lambda x:(x[0],x[1],x[2])) ans = [i for i in range(d+1)] for i i..
728x90
반응형

티스토리툴바