일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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
- Python
- onclick
- 우선순위큐
- BufferedReader
- 직무면접
- clean code
- 음수가 포함된 최단경로
- Java
- 다익스트라
- 기술면접
- 엔테크서비스
- 벨만 포드 알고리즘
- Controller
- 코딩테스트
- kmeans
- Django
- 플로이드 와샬
- top-down
- disjoint set
- 동적계획법
- spring boot
- Android Studio
- dto
- 유니온 파인드
- 최단경로
- compiler
- scikit-learn
- 거쳐가는 정점
- union-find
- bottom-up
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