'📒 코테연습장/📝 최단경로' 카테고리의 글 목록

[Beakjoon] 백준 28354_링크 컷 토마토 (Java)

2023.09.04

28354번: 링크 컷 토마토 첫째 줄에 토마토의 개수 $N$, $0$일에 연결되어 있는 토마토 쌍의 수 $M$, $0$일에 익은 토마토의 수 $K$, 연결 상태가 변하는 횟수 $Q$가 공백으로 구분되어 주어진다. $(1 \leq K \leq N \leq 200\,000;$ $0 \leq www.acmicpc.net 문제 풀이 내 첫 플래티넘 문제였다. 알고리즘은 제대로 구성해서 작성한 것 같은데, 계속 시간 초과가 나서 애먹었던 기억이 있다. 시간을 단축시키고자 BFS 방문 시 필요 없는 방문이 발생하지 않도록 조건도 체크했는데 시간 초과가 나서 며칠 동안 붙잡고 있었다. 결론적으로 탐색이 더 효율적인 자료구조로 변경하니 통과되었다. 처음엔 그래프를 ArrayList로 구현했었는데, 그래프 안에 특정 ..

📒 코테연습장/📝 최단경로

[알고리즘] 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

2023.07.05

벨만 포드 알고리즘 벨만-포드 알고리즘은 다익스트라 알고리즘과 마찬가지로 한 정점을 기준으로 다른 모든 정점까지의 최단경로를 구하여 결과적으로 원하는 도착지까지의 최단경로를 도출해 내는 알고리즘이다. 하지만 다익스트라 알고리즘과 다르게 그래프에 음의 가중치가 있어도 최단 경로를 구할 수 있다. [알고리즘] 다익스트라(Dijkstra) 다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍(DP)과 그리디 알고리즘을 활용한 최단경로 탐색 알고리즘이다. 다익스트라 알고리즘은 하나의 특정 정점에서 다른 모든 정점 dana-study-log.tistory.com 다익스트라와 음의 가중치 다익스트라 알고리즘 과정 1. 시작정점 선택 2. 거리 배열 초기화 (시작정점은 0으로 다른 노드는 무한대로) 3. 지금..

📒 코테연습장/📝 최단경로

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

2023.05.08

다익스트라 알고리즘 다익스트라 알고리즘은 다이나믹 프로그래밍(DP)과 그리디 알고리즘을 활용한 최단경로 탐색 알고리즘이다. 다익스트라 알고리즘은 하나의 특정 정점에서 다른 모든 정점으로 가는 최단 경로를 알 수 있으며, 간선의 가중치가 양수일 때 사용가능하다. 다익스트라 알고리즘이 DP라고 할 수 있는 이유는 특정 최단 거리는 여러 개의 최단거리로 이루어져 있기 때문이며, 하나의 최단 거리를 구할 때 특정 정점까지의 최단거리 정보를 그대로 가져와 사용하기 때문이다. 또한 그리디 알고리즘이라고 말할 수 있는 이유는 특정 최단 거리에 최단 거리를 더해가며 최종적인 최단거리를 계산하는 방식이기 때문이다. (다익스트라 알고리즘을 공부한 뒤 다시 읽으면 쉽게 이해가능) 한 정점에서 다른 모든 정점까지의 최단거리를..

[Beakjoon] 백준 28354_링크 컷 토마토 (Java)

[알고리즘] 벨만-포드 알고리즘 (Bellman-Ford Algorithm)

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

티스토리툴바