# 다익스트라

104개의 포스트

[알고리즘] 백준 - 서강그라운드

백준 - 서강그라운드처음 문제를 제대로 읽지 않고 문제를 풀기 시작해서 다익스트라로 풀었다. 물론 각 노드에 대해 다익스트라를 반복해도되지만, 문제의 의도는 플로이드 와샬이었을 것이다.

4일 전
·
0개의 댓글

[알고리즘] 백준 - 도로포장

백준 - 도로포장처음에는 K개의 범위가 그리 크지 않아서 백트랙킹으로 완탐을 이용하여 각 경우에 대해 다익스트라를 쓰려고 했다. 하지만 메모리 초과가 났다.dp를 활용해서 풀었다.

4일 전
·
0개의 댓글
post-thumbnail

다익스트라 알고리즘

최단 경로(shortest path)문제는 정점 u와 정점 v를 연결하는 경로 중 간선들의 가중치 합이 최소가 되는 경로를 찾는 문제다. 간선의 가중치는 경우에 따라 비용, 거리, 시간 등으로 해석될 수 있다. 아래의 그래프를 살펴보자. 정점 0에서 정점 3으로 가는

6일 전
·
0개의 댓글
post-thumbnail

Bellman Ford's와 다익스트라(Dijkstra) 알고리즘 - 2

Bellman Ford's와 다익스트라(Dijkstra) 알고리즘 - 2 / 백준 1916번 / Python

2021년 5월 6일
·
0개의 댓글
post-thumbnail

Bellman Ford's와 다익스트라(Dijkstra) 알고리즘 - 1

Bellman Ford's 와 다익스트라(Dijkstra) 알고리즘 - 1 / 백준 1916번 문제 / Python

2021년 5월 6일
·
0개의 댓글

[알고리즘] 백준 - 최단경로

백준 - 최단경로전형적인 다익스트라 문제지만 자바로 구현했기에 다소 낯선 포인트들이 있었다.bfs/dfs와 달리 이제는 그래프에 다른쪽 노드와 distance까지 보관해야한다. 따라서 List<Integer>\[]가 아닌 List<int\[]>\[]로 그래프

2021년 5월 6일
·
0개의 댓글

다익스트라(Dijkstra) 알고리즘

하나의 정점에서 모든 정점까지의 최단 거리를 구하는 알고리즘다익스트라 알고리즘은 다음에 방문할 정점을 선택하는 방법에 따라 크게 두가지로 구현이 가능하다.출발지로부터 모든 정점까지의 거리를 담는 우선순위 큐를 구현해, 출발점으로부터 거리가 가장 작은것부터 꺼내오기시간

2021년 5월 5일
·
0개의 댓글

[BOJ] 1238 파티

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비

2021년 5월 5일
·
0개의 댓글

백준 1753 풀이

https://www.acmicpc.net/problem/1753 최단경로

2021년 5월 2일
·
0개의 댓글

FIRETRUCKS(소방차)

(출처) https://algospot.com/judge/problem/read/FIRETRUCKS

2021년 4월 29일
·
0개의 댓글

ROUTING(신호라우팅)

(출처) https://algospot.com/judge/problem/read/ROUTING

2021년 4월 29일
·
0개의 댓글
post-thumbnail

알고리즘 11일차 - 그래프, 최단 경로 알고리즘, 다익스트라

피곤하다.. 그래도 해야한다 그래프에 관한 알고리즘이 워낙에 많고 시험에도 자주 나오니 대략적으로 정리하면 다음과 같다. 그래프의 순회 DFS BFS 그래프의 최단 경로 다익스트라 벨만포드 플루이드 와샬 최소 비용 그래프 연결(MST) 프림 크루

2021년 4월 28일
·
0개의 댓글

[JS] 프로그래머스 경주로 건설

알고리즘, 2020 카카오 인턴십 4번, 다익스트라, 완전탐색

2021년 4월 27일
·
0개의 댓글
post-thumbnail

[Python] 프로그래머스(Lv2) - 배달

안녕하세요 ! https://programmers.co.kr/learn/courses/30/lessons/12978프로그래머스 배달 문제입니다.그래프를 보면, 가중치가 있는 최단경로를 구하는 문제로 볼 수 있습니다. 가중치가 있는 최단경로는 다익스트라 알고리즘

2021년 4월 23일
·
0개의 댓글
post-thumbnail

[알고리즘] 다익스트라 알고리즘 (Dijkstra Algorithm)

최단 경로 알고리즘은 말 그대로 가장 짧은 경로를 찾는 알고리즘이다. ('길 찾기 문제' 라고도 불린다.) 최단 경로 알고리즘 유형에는 다양한 종류가 있다. 대표적으로 다익스트라 최단 경로 알고리즘, 플로이드 워셜, 벨만 포드 알고리즘, 이렇게 3가지이다. 그중 다익스

2021년 4월 21일
·
0개의 댓글
post-thumbnail

다익스트라 최단 경로 알고리즘

다익스트라 최단 경로 알고리즘에 대해 알아보자.

2021년 4월 20일
·
0개의 댓글

프로그래머스 72413번 - 합승 택시 요금(★★★ / O / 1) : Python

풀이 시간 : 15~20분시간 제한 : 알수없음(2초까지는 가능한듯)메모리 제한 : 알수없음기출 : 2021 KAKAO BLIND RECRUITMENT링크 : https://programmers.co.kr/learn/courses/30/lessons/72413

2021년 4월 13일
·
0개의 댓글

최단경로 알고리즘 (다익스트라)

가장 작은 비용으로 목표에 도달하는 최단경로 알고리즘 : heapq를 활용한 다익스트라 알고리즘을 공부해보았다.

2021년 4월 13일
·
0개의 댓글