본문 바로가기

알고리즘 이론32

벨만포드 알고리즘 (Bellman-Ford algorithm) 벨만 포드는 최단 경로 알고리즘입니다. 하나의 특정 도시에서 다른 도시들로 가는 최단 경로, 최소비용을 구하는데 사용됩니다. 벨만 포드 알고리즘과 다익스트라 알고리즘의 차이는 간선에 음수가 있을 때 사용할 수 있는가입니다. 다익스트라 알고리즘은 간선에 음수가 있을 때 사용할 수 없습니다. (참고) 벨만 포드 알고리즘은 "최단 경로는 최대 V-1 개의 간선을 지난다."를 이용한 방법으로 간선에 음수가 있을 때도 사용할 수 있습니다. (정점을 한 번씩 지났을 때가 최대로 많은 간선을 지니는 최단 경로) 그런데 만약 최단 경로에 음수 사이클(가중치의 합이 음수여서 해당 사이클을 돌 때마다 가중치 합이 줄어드는 구간)이 존재한다면 최단 거리는 끊임없이 작아질 것입니다. 그래서 벨만 포드에서 V-1 번 간선들을 .. 2019. 9. 26.
[알고리즘] 대회 TIP (for me) 코딩할 때 자주 헷갈리는거 모아둠. 우선순위큐 (priority_queue) priority_queue min_heap; // 최대 힙 priority_queue max_heap; // 최소 힙 참고 : https://github.com/fpdjsns/Algorithm/blob/master/tip/%EC%B5%9C%EC%86%8C%ED%9E%99_%EC%B5%9C%EB%8C%80%ED%9E%99.cpp vector 정렬 vector v; sort(v.begin(), v.end()); // 오름차순 bool compare(int a, int b){ return a > b; } sort(v.begin(), v.end(), compare); // 내림차순 sort(v.begin(), v.end(), [](co.. 2019. 9. 23.
다익스트라 알고리즘 (Dijkstra's algorithm) 다익스트라는 최단경로 알고리즘입니다. 하나의 특정 도시에서 다른 도시들로가는 최단경로, 최소비용을 구하는데 사용됩니다. 도시 i에서 j로 가는 비용이 arr[i][j]이고 도시들의 방문여부를 배열 check에 저장, 도시로 가는 최소비용을 배열 dist에 저장한다고 했을 때, 다익스트라 알고리즘은 다음과 같습니다. 1. 현재 도시(now)의 방문 여부를 체크합니다. [check[now] = true] 2. 현재 도시(now)를 거쳐 갈 수 있는 도시(next)들의 비용이 현재 저장되어 있는 비용(dist[next])보다 큰 경우 이를 갱신합니다. [ dist[next] > dist[now] + arr[now][next] => dist[next] = dist[now] + arr[now][next] ] 3... 2019. 9. 18.
외판원 순회(TSP: Traveling Salesperson Problem) 외판원 순회(TSP: Traveling Salesperson Problem)란 도시들이 있고 특정 도시에서 도시로 이동할 때 드는 비용이 주어졌을 때 불특정한 도시에서 출발해서 모든 도시를 돌고 다시 출발 도시로 돌아왔을 때 드는 최소 비용을 구하는 문제입니다. 외판원 순회는 NP문제로 이번에 소개할 알고리즘은 N이 16개 이하일 때 DP와 비트마스크를 이용하여 구하는 방법입니다. DP는 특정 도시들을 방문한 상태일 때 최소 비용을 저장해 놓고 이를 사용합니다. 비트마스크는 특정 도시를 방문한 상태를 저장할 때 사용합니다. 예를 들어서 1~3번 도시가 있다고 했을 때, 110(2)는 2,3번 도시를 방문한 상태입니다. 110(2)를 십진수로 바꿔보면 6(1x22 + 1x21 + 0x20)이 됩니다. 즉,.. 2019. 8. 31.
너비 우선 탐색(BFS: Breadth First Search) 그래프를 탐색하는 보편적인 방법은 깊이 우선 탐색(DFS)와 너비 우선 탐색(BFS)이 있습니다. 이번 시간에는 그 중 너비 우선 탐색에 대해 알아보겠습니다. 너비 우선 탐색은 그래프를 넓게 탐색하는 방법입니다. 예를 들어 보겠습니다. 너비 우선 탐색의 알고리즘은 1. 노드와 연결된 탐색하지 않은 모든 이웃 노드를 탐색한다. 2. 방금 탐색한 노드들에 1번 과정을 실행한다. 입니다. 즉, 1번 2번을 모든 노드가 탐색될 때까지 번갈아가며 실행합니다. 이해를 돕기위해 위의 예시 그래프를 너비 우선 탐색(BFS)으로 탐색해 보겠습니다. 시작 노드는 1번으로 하겠습니다. 일단 시작 노드인 1번 노드를 탐색합니다. 그리고 1번 노드의 이웃 노드 중 탐색하지 않았던 노드들을 우선 모두 탐색합니다. 즉, 2번 3번.. 2019. 8. 28.
버블 정렬(Bubble Sort) 버블 정렬은 단계별로 인접한 수를 비교하여 큰 수를 배열의 뒤로 보내서 정렬하는 것을 말합니다. 예를 들어서 설명해 보겠습니다. 정렬하고자 하는 배열은 "4 5 3 6 7 2 1" 이고 이를 오름차순 정렬해보겠습니다. 일단 앞에서부터 이웃한 두 수를 비교해서 인덱스 i 번째 수 보다 i + 1 번째 수가 작다면(array[i] > array[i+1]) 두 수를 바꿔줍니다. 위의 그림에서 이웃한 두 수 4, 5를 비교했을 때 i 번째 수(4)보다 i+1 번째 수(5)가 더 크므로 바꿔주지 않고 다음 인덱스로 넘어갑니다. 5, 3을 비교했을 때는 i 번째 수(5)보다 i+1 번째 수(3)가 더 작으므로 두 수를 바꿔줍니다. 이런 식으로 배열의 끝까지 진행하면 가장 큰 수가 배열의 맨 끝에 위치하게 됩니다. .. 2019. 6. 12.