우선순위 큐4 [알고리즘] ep7+) 다익스트라와 벨만-포드 알고리즘 구현 주의: 그래프 알고리즘 구현 시, 그래프의 인접 정보(즉, 부착 간선리스트 또는 인접행렬) 없이도 수행 가능한 문제라고 판단되면 간선리스트 구조로 그래프를 간편하게 구현할 것을 우선적으로 고려하라. 그렇지 않고, 인접 정보가 있어야 수행한다고 판단되면 인접리스트 구조 또는 인접행렬 구조 중에 해당 문제 해결에 효율성 면에서 유리하다고 판단되는 것을 선택하여 구현하라. 문제1) 무방향 양의 가중그래프 -> 다익스트라 알고리즘무방향 양의 가중그래프(undirected weighted graph) G와 출발정점이 주어지면, 출발정점에서 다른 모든 정점으로 가는 최단거리를 구하는 프로그램을 작성하라. 입력 그래프의 성질:◦ n(1 ≤ n ≤ 100)개의 정점과 m(1 ≤ m ≤ 1,000)개의 간선으로 구성.. 2024. 7. 27. [알고리즘] ep6+) Prim-Jarnik과 Kruskal 알고리즘 구현 주의: 그래프 알고리즘 구현 시, 그래프의 인접 정보(즉, 부착 간선리스트 또는 인접행렬) 없이도 수행 가능한 문제라고 판단되면 간선리스트 구조로 그래프를 간편하게 구현할 것을 우선적으로 고려하라. 그렇지 않고, 인접 정보가 있어야 수행한다고 판단되면 인접리스트 구조 또는 인접행렬 구조 중에 해당 문제 해결에 효율성 면에서 유리하다고 판단되는 것을 선택하여 구현하라. 문제1) Prim-Jarnik 알고리즘 구현입력으로 주어지는 그래프를 Prim-Jarnik 알고리즘을 이용하여 최소신장트리(Minimum Spanning Tree, MST)를 생성하는 프로그램을 작성하고, 최소신장트리의 생성 과정과 총무게를 결과로 출력하시오. 입력 그래프의 성질: n (1 ≤ n ≤ 100) 개의 정점과 m (1 ≤ m .. 2024. 7. 26. [알고리즘] 정렬 알고리즘 선택 매뉴얼 ㅇ버블정렬 - 실무에서는 아예 사용하면 안된다"제자리 + stable" O(n^2) ㅇ선택정렬: 우선순위 큐 (무순 리스트로 구현)"제자리 + unstable" O(n^2): 느리다 - 소규모 입력에 적합 ㅇ삽입정렬: 우선순위 큐 (순서 리스트로 구현)"제자리 + stable" O(n^2): 느리다 - 소규모 입력에 적합 ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ ㅇ힙정렬: 우선순위 큐 (힙으로 구현)"제자리 + unstable" O(nlog(n)): 빠르다 - 대규모 입력에 적합 ㅇ병합정렬: 분할통치"제자리 X + stable" O(nlog(n)): 빠르다 - 초대규모 입력 + stable 결과에 적합 ㅇ퀵정렬: 분할통치"제자리 + unstable".. 2024. 7. 7. [알고리즘] ep1-1) 우선순위 큐 ㅇ우선순위 큐(Priority Queue): 각 요소마다 우선순위를 부여하고 이 우선순위에 따라 요소를 처리하는 큐요소가 삽입될 때 우선순위가 함께 부여되며, 삭제 시에는 가장 높은 우선순위를 가진 요소가 먼저 삭제된다 활용 분야: CPU 작업 스케줄링, 네트워크 패킷 처리, 최단 경로 알고리즘(다익스트라 알고리즘 등) 등 [구현 방법 2가지]1. 리스트를 이용한 구현① 무순리스트로 구현: 리스트에 임의 순서로 저장e.g. 선택정렬 ② 순서리스트로 구현: 리스트에 키 정렬 순서로 저장e.g. 삽입정렬 2. 힙을 이용한 구현① 최대 힙 사용② 최소 힙 사용 일반적으로 우선순위 큐를 구현할 때는 힙을 사용하는 것이 가장 효율적이다(최대 힙 or 최소 힙) 출처 및 참고: 알고리즘-원리와.. 2024. 7. 3. 이전 1 다음
