그래프 알고리즘(2) - 벨만포드, 존슨, 코사리주 알고리즘
1. 최단 경로 문제 다시 살펴보기 다익스트라 알고리즘은 성능 면에서 우수하나, 모든 그래프에 적용 불가능 그래프에 음수 가중치가 있을 경우 최적의 경로를 찾지 못하는 경우 발생 2. 벨만-포드 알고리즘 그래프의 모든 엣지에 대해 다익스트라의 그리디 선택 방법을 반복하여 점진적인 최단 거리 탐색 1) 연습 문제 32: 벨만-포드 알고리즘 구현하기 #include #include #include using namespace std; struct Edge { int src; int dst; int weight; }; const int UNKNOWN = INT_MAX; vector BellmanFord(vector edges, int V, int start) { vector distance(V, UNKNOWN..
- Computer Science/Data Structure & Algorithm
- · 2023. 7. 4.
그래프 알고리즘 (1) - BFS, DFS, 다익스트라 알고리즘
0. 들어가며 그래프는 정점의 집합과 정점들을 서로 잇는 에지의 집합으로 구성 그래프는 매우 유연한 자료구조 객체와 객체 사이의 관계를 표현 두 정점 사이에 여러 엣지를 가지기도 하고 하나의 엣지에 여러 가중치 부여하기도 하며 자신을 가르키는 셀프 엣지도 존재 주로 다루는 것은 방향 가중 그래프 1. 그래프 순회 문제 그래프의 특정 정점에서 시작하여 나머지 모든 정점을 방문하는 문제 그래프 탐색 문제로도 불림 1) 너비 우선 탐색 (BFS, Breadth-First Search) 시작 정점을 경계에 추가하는 것으로 시작 경계는 이전에 방문했던 정점들에 의해 구성 현재 경계에 인접한 정점을 반복적으로 탐색 2) 연습 문제 28: BFS 구현하기 #include #include #include #includ..
- Computer Science/Data Structure & Algorithm
- · 2023. 7. 3.
그리디 알고리즘
0. 들어가며 매 단계에서 ‘가장 좋아 보이는’ 해답을 선택하는 알고리즘 지역적인 최적의 해결 방법 → 전역적인 최적의 해결 방법 1. 기본적인 그리디 알고리즘 1) 최단 작업 우선 스케줄링 평균 대기 시간을 줄이기 위해 일 처리가 가장 빠른 사람을 맨 앞으로 가장 빠른 사람을 선택→그리디 알고리즘 2) 연습 문제 24: 최단 작업 우선 스케줄링 #include #include #include #include template auto compute_waiting_times(std::vector& service_times) { std::vector W(service_times.size()); W[0] = 0; for(auto i=1; i
- Computer Science/Data Structure & Algorithm
- · 2023. 7. 2.