본문 바로가기

알고리즘3

[이코테] 전보(2) - 코딩테스트 - 다른풀이 안녕하세요. 이번에는 이전에 풀었던 전보 - 다익스트라 알고리즘 풀이를 다른 방식으로 풀어보려고합니다. 다익스트라 풀이법은 아래의 링크로 들어가시면 보실 수 있습니다. https://sonlife97.tistory.com/entry/%EC%9D%B4%EC%BD%94%ED%85%8C-%EC%A0%84%EB%B3%B4-%EC%BD%94%EB%94%A9%ED%85%8C%EC%8A%A4%ED%8A%B8-%EA%B5%AC%EC%B2%B4%EC%A0%81%EC%9D%B8%ED%92%80%EC%9D%B4 [이코테] 전보 - 코딩테스트 - 구체적인풀이 문제 어떤 나라에는 N개의 도시가 있다. 그리고 각 도시는 보내고자 하는 메시지가 있는 경우, 다른 도시로 전보를 보내서 다른 도시로 해당 메시지를 전송할 수 있다. 하.. 2024. 1. 18.
최단경로 - 플로이드 워셜 알고리즘 플로이드 워셜 알고리즘이란? 다익스트라 알고리즘은 '한 지점에서 다른 특정 지점까지의 최단 경로를 구해야 하는 경우'에 사용할 수 있는 최단 경로 알고리즘입니다. 이번에 설명하는 플로이드 워셜 알고리즘은 '모든 지점에서 다른 모든 지점까지 최단 경로를 모두 구해야 하는 경우'에 사용할 수 있는 알고리즘입니다. 다이나믹 프로그래밍을 기반으로 하며, 특히 밀집 그래프(dense graph)에서 효과적입니다. 플로이드 워셜 알고리즘의 개념 초기화 먼저, 최단 거리를 저장할 테이블(2차원 배열)을 초기화합니다. 이 테이블의 각 항목 dist[i][j]는 정점 i에서 j로 가는 최단 거리를 나타냅니다. 자기 자신으로의 거리는 0으로, 직접 연결된 정점 사이의 거리는 해당 가중치로, 그렇지 않은 경우에는 무한대(또.. 2024. 1. 17.
최단경로 - 다익스트라 알고리즘 구체적인 설명(2) - 우선순위큐 활용 이전의 간단한 다이스트라 알고리즘 https://sonlife97.tistory.com/entry/%EC%B5%9C%EB%8B%A8%EA%B2%BD%EB%A1%9C-%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B5%AC%EC%B2%B4%EC%A0%81%EC%9D%B8-%EC%84%A4%EB%AA%85 최단경로 - 다익스트라 알고리즘 구체적인 설명 다익스트라 알고리즘은 하나의 출발 노드로부터 모든 노드까지의 최단 경로를 찾는 알고리즘입니다. 알고리즘의 원리를 간략히 설명하면 다음과 같습니다. 1. 출발 노드를 설정한다. 2. 최단 거 sonlife97.tistory.com 해당 알고리즘의 시간 복.. 2024. 1. 16.

티스토리툴바