반응형 DP3 파이썬(Python) 플로이드-워셜(Floyd-Warshall) 개념과 예제 (백준 11404) 플로이드-워셜 알고리즘 ● 다익스트라( O(ElogV) ) vs 벨만-포드 ( O(EV) ) vs 플로이드-워셜 ( O(V^3) ) 다익스트라는 양수엣지에서 가장 빠르게 최단거리를 구하는 알고리즘이고, 벨만-포드는 음수엣지에서 최단거리를 구하는 알고리즘이라면, 플로이드는 한 번 실행하여 모든 노드 간 최단 경로를 구할 수 있습니다. (플로이드-워셜 알고리즘은 음의 간선도 사용할 수 있습니다) 그러므로 한노드에서 출발하는 최단거리를 구하라고 하면 오래 걸리지만, 출발노드가 계속 달라지면서, 최단거리의 질의가 많아지면 빛을 발하는 알고리즘이라고 볼 수 있습니다. 동적계획법(DP)의 원리를 이용한 알고리즘으로 점화식은 아래와 같습니다. s에서 시작해서 e로 간다고 하겠습니다. s->k->e 방식으로 k를 경유.. 2022. 12. 31. [백준 9084] 냅색 알고리즘(DP) - 파이썬 Python 동전 성공 문제 우리나라 화폐단위, 특히 동전에는 1원, 5원, 10원, 50원, 100원, 500원이 있다. 이 동전들로는 정수의 금액을 만들 수 있으며 그 방법도 여러 가지가 있을 수 있다. 예를 들어, 30원을 만들기 위해서는 1원짜리 30개 또는 10원짜리 2개와 5원짜리 2개 등의 방법이 가능하다. 동전의 종류가 주어질 때에 주어진 금액을 만드는 모든 방법을 세는 프로그램을 작성하시오. 입력 입력의 첫 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 10)가 주어진다. 각 테스트 케이스의 첫 번째 줄에는 동전의 가지 수 N(1 ≤ N ≤ 20)이 주어지고 두 번째 줄에는 N가지 동전의 각 금액이 오름차순으로 정렬되어 주어진다. 각 금액은 정수로서 1원부터 10000원까지 있을 수 있으며 공백으로 .. 2022. 12. 30. [백준 12865] 냅색 알고리즘(DP) - 파이썬 Python 평범한 배낭 문제 이 문제는 아주 평범한 배낭에 관한 문제이다. 한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다. 준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자. 입력 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100.. 2022. 12. 18. 이전 1 다음
