일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 엔테크서비스
- spring boot
- BufferedReader
- kmeans
- 동적계획법
- bottom-up
- Python
- Controller
- 코딩테스트
- Java
- top-down
- 기술면접
- onclick
- disjoint set
- 최단경로
- Django
- 우선순위큐
- union-find
- Android Studio
- compiler
- 다익스트라
- dto
- 직무면접
- 음수가 포함된 최단경로
- 플로이드 와샬
- 벨만 포드 알고리즘
- 거쳐가는 정점
- scikit-learn
- clean code
- 유니온 파인드
Archives
- Today
- Total
목록다익스트라 (1)
춤추는 개발자
[그래프] 다익스트라 알고리즘
다익스트라 - '최단 경로는 여러 개의 최단경로로 이루어졌다.' - 다이나믹 프로그래밍을 활용한 대표적인 최단 경로 탐색 알고리즘, 하나의 정점(Node)에서부터 다른 정점까지로 가는 최단 경로를 알 수 있습니다. (대신, 가중치가 음수인 경우 적용할 수 없습니다.) - 기본적으로 하나의 최단 경로를 구할 때, 이전까지 구한 최단 경로 정보를 그대로 활용한다는 특징이 있습니다. 다익스트라의 작동과정 1. 출발노드 선정 2. 출발노드를 기준으로 연결된 노드마다 최소 비용 저장 3. 방문하지 않은 노드 중 최소 비용의 노드 선택 4. 다른 노드로 이동할 경우, 최소 비용을 갱신하며 이동 5. 3~4번 반복 www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 ..
Developer's_til/자료구조 & 알고리즘
2021. 3. 29. 17:33