기록하지 않았다면 잃어버릴 시간들

새로운 것을 배우는게 즐거운 개발자입니다.

알고리즘/이론

안녕하세요. 최근 PS 관련 풀이를 하던도중 다익스트라 알고리즘에 대해 접하게 되었는데요. 사실 학부시절때 이론은 수업을 들어서 알고 있었지만 깊게 공부해보지 않아서 코드로 적용하기가 힘들더라구요... 그래서 이번 기회에 조금 깊게 공부해본 내용을 설명 하게 되었습니다. ●다익스트라 알고리즘 요약 1956년에 에즈허르 데이크스트라가 고안 다익스트라 알고리즘은 두 꼭지점 사이의 최단 경로 거리를 구하는 알고리즘 방향성 그래프와 무방향성 그래프 모두에 적용가능 가중치가 음수이면 사용 불가능 현제 길찾기 알고리즘의 기초가 되는 알고리즘 최초의 다익스트라는 출발노드를 기준으로 최소비용 그래프를 저장하여 방문하지 않은 노드 중 가장 가까운 거리에 있는 노드를 먼저 방문을 한 후 또 다른 노드를 방문하게 될 때 기..

2021. 8. 8.

알고리즘/백준

https://www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 백준 온라인저지 1753번 문제입니다. 다익스트라 #include #include #include #define MAX 20001 #define INF 987654321 #define endl "\n" using namespace std; int node[MAX]; vector connect[MAX]; int V, E, K; void init(int a) { for (i..

2021. 8. 4.

알고리즘/백준

https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 백준 1916번 문제입니다. 다익스트라 알고리즘을 이용해서 문제를 풀었습니다. #include #include #include #define MAX 1001 #define INF 987654321 using namespace std; int N,M, s,d,v; vectorconnect[MAX]; int val[MAX]; int node[MAX]; void Ini..

2021. 8. 4.