다익스트라 알고리즘3 [알고리즘] ep7++) 다익스트라 확장 알고리즘 다익스트라 확장 알고리즘은 기본 다익스트라 알고리즘을 수정하여 단일 출발점에서 목표 지점까지의 최단 경로뿐만 아니라 최단 경로의 수까지 계산할 수 있도록 한다. 이 문제에서 요구하는 것은 다익스트라 알고리즘을 사용하여 각 정점까지의 최단 거리를 계산하고, 동시에 각 정점에 도달하는 최단 경로의 수를 세는 기능을 추가한 것이다. 위 샘플그래프 G에 대해 아래 정점쌍 4개를 s(ource) 및 t(arget) 인자쌍으로 각각 사용하여 수행하라(즉, 프로그램을 4회 수행함). 각 수행 결과는 아래 예시처럼 인쇄할 것 [출력예시]source target 최단거리 최단경로 수C A 1 1 C F .. 2024. 8. 2. [알고리즘] ep7+) 다익스트라와 벨만-포드 알고리즘 구현 주의: 그래프 알고리즘 구현 시, 그래프의 인접 정보(즉, 부착 간선리스트 또는 인접행렬) 없이도 수행 가능한 문제라고 판단되면 간선리스트 구조로 그래프를 간편하게 구현할 것을 우선적으로 고려하라. 그렇지 않고, 인접 정보가 있어야 수행한다고 판단되면 인접리스트 구조 또는 인접행렬 구조 중에 해당 문제 해결에 효율성 면에서 유리하다고 판단되는 것을 선택하여 구현하라. 문제1) 무방향 양의 가중그래프 -> 다익스트라 알고리즘무방향 양의 가중그래프(undirected weighted graph) G와 출발정점이 주어지면, 출발정점에서 다른 모든 정점으로 가는 최단거리를 구하는 프로그램을 작성하라. 입력 그래프의 성질:◦ n(1 ≤ n ≤ 100)개의 정점과 m(1 ≤ m ≤ 1,000)개의 간선으로 구성.. 2024. 7. 27. [알고리즘] ep1-1) 우선순위 큐 ㅇ우선순위 큐(Priority Queue): 각 요소마다 우선순위를 부여하고 이 우선순위에 따라 요소를 처리하는 큐요소가 삽입될 때 우선순위가 함께 부여되며, 삭제 시에는 가장 높은 우선순위를 가진 요소가 먼저 삭제된다 활용 분야: CPU 작업 스케줄링, 네트워크 패킷 처리, 최단 경로 알고리즘(다익스트라 알고리즘 등) 등 [구현 방법 2가지]1. 리스트를 이용한 구현① 무순리스트로 구현: 리스트에 임의 순서로 저장e.g. 선택정렬 ② 순서리스트로 구현: 리스트에 키 정렬 순서로 저장e.g. 삽입정렬 2. 힙을 이용한 구현① 최대 힙 사용② 최소 힙 사용 일반적으로 우선순위 큐를 구현할 때는 힙을 사용하는 것이 가장 효율적이다(최대 힙 or 최소 힙) 출처 및 참고: 알고리즘-원리와.. 2024. 7. 3. 이전 1 다음
