# Bellman Ford

19개의 포스트

백준 #11657 타임머신 (파이썬)

전형적인 벨만-포드 알고리즘 문제

약 12시간 전
·
0개의 댓글

[Algorithm] 다익스트라 vs 벨만포드 vs 플로이드와샬

그래프에서 하나의 노드에서 다른 모든 노드로 이동하는 최단 비용을 구하는 알고리즘시작 노드의 비용을 0 으로 초기화 (본인에게 이동하는 비용은 0)우선 순위 큐에 시작 노드를 삽입 (연결 리스트로 구현하는 등 다른 방법도 있는 듯 하다)큐가 비어있을 때 까지 아래의 동

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

[Algorithm] Shortest Path - 최단경로 알고리즘

최단 경로 알고리즘이란,최단 경로 알고리즘으로 주어진 노드와 간선들 중 가장 짧은 경로를 찾는 알고리즘최단 경로 문제의 종류하나의 정점에서 다른 하나의 정점까지 최단 경로를 구하는 문제하나의 정점에서 다른 모든 정점까지의 최단 경로를 구하는 문제각 모든 정점에서 다른

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

[알고리즘][파이썬] 벨만-포드 알고리즘

그래프를 사용하는 최단거리 알고리즘 중 하나이다. 알고리즘은 배워도 배워도 끝이 없다. 하나 배우면 앞에 배운거 까먹고 ㅎㅎ.. 그래서 이렇게 기록을 해놔야 한다. 다익스트라 알고리즘이라는 많이들 사용하는 알고리즘이 있는데 왜 벨만-포드 알고리즘을 써야하는 경우가 생기

2022년 4월 15일
·
0개의 댓글
post-thumbnail

[python] 백준 11657 : 타임머신

벨만-포드 알고리즘을 이용한 풀이

2022년 3월 4일
·
0개의 댓글

벨만포드(Bellman-Ford) 알고리즘이란 무엇인가?

벨만포드 알고리즘이란? 다익스트라 알고리즘과 마찬가지로 최단경로를 구하는 알고리즘입니다. 다익스트라는 음의 간선이 없을 경우에만 사용이 가능하지만, 벨만포드 알고리즘의 경우 음의 간선이 있을 때에도 최단거리를 구할 수 있습니다. 하지만 다익스트라 알고리즘보다 느립니다.

2022년 2월 24일
·
0개의 댓글

백준 1219번: 오민식의 고민

백준 1219번: 오민식의 고민기본 아이디어는 골목길 문제와 비슷하다.간선을 탈 때 빼주고, 노드에 도착했을 때 더해준다. 이 문제도 도착점까지 가는 경로에 사이클이 있는 경우에만 Gee를 출력해야 한다. 골목길 문제는 1부터 N까지 순서대로 V-1번 루프를 돌고 마지

2022년 1월 24일
·
0개의 댓글

백준 1738번: 골목길

백준 1738번: 골목길음의 간선을 포함한 최단거리 찾기. 이 때 단순히 사이클이 존재한다고 -1을 출력하는 것이 아니라, 1부터 N까지 가는 길에 사이클이 존재하여 N에 도착했을 때 금품을 무한히 가질 수 있는 경우에만 -1을 출력해야 한다. 예를 들어, N=5이고,

2022년 1월 24일
·
0개의 댓글

백준 11657번: 타임머신

백준 11657번: 타임머신음의 간선이 존재하기 때문에 다익스트라 알고리즘으로는 최단거리를 찾을 수 없다. 따라서 O(VE)로 모든 경우의 수를 탐색하는 벨만 포드 알고리즘이 적합. i가 1씩 커질때마다 싸이클을 한번씩 돈다고 하면, 500바퀴 돌렸을 때 INT_MIN

2022년 1월 24일
·
0개의 댓글
post-thumbnail

[백준] 1865번- 웜홀

[백준] 1865번- 웜홀

2021년 7월 14일
·
0개의 댓글

[C] 백준 11657 타임머신

https://www.acmicpc.net/problem/11657 문제 N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인 경우는 순간 이동...

2021년 7월 10일
·
0개의 댓글
post-thumbnail

[백준] 11657번-(Python 파이썬) - Bellman-Ford

문제링크 : https://www.acmicpc.net/problem/11657이번 문제는 가중치가 음수인 경우가 있어 다익스트라가 아니라 벨만포드 알고리즘으로 풀어야한다.벨만포드 알고리즘은 다익스트라에 비해 느리므로 가중치가 음수인경우에만 사용하는게 좋다.기

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

[백준]#1738 골목길

문제민승이는 놀러가기 위해 집을 나섰다. 민승이네 집에서 코레스코 콘도까지 가기 위해서는 복잡하게 얽혀있는 골목길들을 통과해야 한다.그런데, 어떤 길에는 깡패가 서식하고 있어, 그 길을 지나게 되면 깡패에게 일정한 양의 금품을 갈취당하게 된다. 그런가하면, 어떤 길에는

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

[백준]#1219 오민식의 고민

문제오민식은 세일즈맨이다. 오민식의 회사 사장님은 오민식에게 물건을 최대한 많이 팔아서 최대 이윤을 남기라고 했다.오민식은 고민에 빠졌다.어떻게 하면 최대 이윤을 낼 수 있을까?이 나라에는 N개의 도시가 있다. 도시는 0번부터 N-1번까지 번호 매겨져 있다. 오민식의

2020년 11월 13일
·
0개의 댓글
post-thumbnail

[백준]#11657 타임머신

문제N개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 버스가 M개 있다. 각 버스는 A, B, C로 나타낼 수 있는데, A는 시작도시, B는 도착도시, C는 버스를 타고 이동하는데 걸리는 시간이다. 시간 C가 양수가 아닌 경우가 있다. C = 0인

2020년 10월 22일
·
0개의 댓글
post-thumbnail

11657번: 타임머신

어렵다ㅋㅋㅋ 벨만포드 문제를 풀어보았다. 나중에 다시 보는 걸로..

2020년 10월 17일
·
0개의 댓글
post-thumbnail

[백준]#1865 웜홀

문제때는 2020년, 백준이는 월드나라의 한 국민이다. 월드나라에는 N개의 지점이 있고 N개의 지점 사이에는 M개의 도로와 W개의 웜홀이 있다. (단 도로는 방향이 없으며 웜홀은 방향이 있다.) 웜홀은 시작 위치에서 도착 위치로 가는 하나의 경로인데, 특이하게도 도착을

2020년 8월 28일
·
0개의 댓글
post-thumbnail

[알고리즘] Bellman-Ford in python3

Dijkstra 다음은 Bellman-Ford 알고리즘이죠. MIT 6006 강좌의 17번째 강의입니다. 개인적으로는 Dijkstra보다 원리가 훨씬 단순해서 더 이해하기 편했습니다. 구현의 경우에도 negative cycle을 체크하는 코드 정도가 추가되었을 뿐 Dijkstra의 경우보다 짧아졌습니다.

2018년 11월 15일
·
0개의 댓글