📌문제방문 판매원 A는 많은 회사가 모여 있는 공중 미래 도시에 있다. 공중 미래 도시에는 1번~N번까지의 회사가 있는데 특정 회사끼리는 서로 도로를 통해 연결되어 있다. 방문 판매원 A는 현재 1번 회사에 위치해 있으며, X번 회사에 방문해 물건을 판매하고자 한다.연결된 두개의 회사는 양방향으로 이동할 수 있고 특정 회사와 다른 회사가 도로로 연결되어 있다면 1만큼의 시간으로 이동할 수 있다.또한 방문 판매원 A는 기대하던 소개팅에도 참석하고자 한다. 소개팅 상대는 K번 회사에 존재한다. A는 X번 회사에 가서 물건을 판매하기 전에 먼저 소개팅 상대의 회사에 찾아가서 함께 커피를 마실 예정이다. 따라서 A는 1번 회사에서 출발하여 K번 회사를 방문한 뒤에 X번 회사로 가는 것이 목표이다. 방문 판매원..
📌플로이드 워셜 알고리즘모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용(다익스트라 알고리즘: 한 지점에서 다른 특정 지점까지의 최단 경로 구하는 경우 사용) 시간복잡도: O(N³) 다이나믹 프로그래밍노드의 개수 N번 만큼의 단계를 반복하며 점화식에 맞게 2차원 리스트를 갱신A에서 B로 가는 최소 비용과 A에서 K를 거쳐 B로 가는 비용을 비교하여 더 작은 값으로 갱신 📌플로이드 워셜 알고리즘 소스 코드INF = int(1e9) # 무한, 10억# 노드의 개수와 간선의 개수 입력받기n = int(input())m = int(input())# 2차원 리스트(그래프 표현)를 만들고, 모든 값을 무한으로 초기화graph = [[INF] * (n + 1) for _ in rang..
📌방법 2. 개선된 다익스트라 알고리즘 시간 복잡도: O(ElogV), V=노드의 개수, E=간선의 개수힙 자료구조 사용특정 노드까지의 최단 거리에 대한 정보를 힙에 담아서 처리하므로 출발 노드로부터 가장 거리가 짧은 노드를 더욱 빠르게 찾을 수 있음(로그 시간) 방법 1에서 최단 거리가 가장 짧은 노드를 선택하는 과정을 우선순위 큐를 이용하는 방식으로 대체 📌개선된 다익스트라 알고리즘 소스 코드import heapqimport sysinput = sys.stdin.readlineINF = int(1e9) # 무한, 10억# 노드의 개수, 간선의 개수 입력받기n, m = map(int, input().split())# 시작 노드 번호 입력받기start = int(input())# 각 노드에 연결되어..
📌최단 경로가장 짧은 경로길 찾기 문제라고도 불림보통 그래프를 이용해 표현 최단 거리 알고리즘 3가지: 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘 그리디 알고리즘과 다이나믹 프로그래밍 알고리즘이 최단 경로 알고리즘에 그대로 적용 📌다익스트라 최단 경로 알고리즘그래프에서 여러 노드가 있을 때, 특정한 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘매번 가장 비용이 적은 노드를 선택해서 다음 과정을 반복1. 출발 노드 설정2. 최단 거리 테이블 초기화3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드 선택4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신5. 3, 4번 반복 각 노드에 대한 현재까지의 최단 거리 정보..
📌문제N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다. 이때 각 화폐는 각 몇개라도 사용할 수 있으며, 사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 📌풀이적은 금액부터 큰 금액까지 확인하며 차례대로 만들 수 있는 최소한의 화폐 개수를 찾음 📌코드n, m = map(int, input().split())array = []for i in range(n): array.append(int(input()))# 한번 계산된 결과를 저장하기 위한 DP 테이블 초기화d = [10001] * (m + 1)# 다이나믹 프로그래밍(보텀업)d[0] = 0for i in range(n): for j in range(array..