[알고리즘] 최단 경로 찾기

최단 경로를 찾는 데 자주 사용되는 알고리즘은 여러 가지가 있다. 1. One-To-One 한 지점에서 다른 특정 지점까지의 최단경로 구하기2. One-To-All 한 지점에서 다른 모든 지점까지의 최단경로 구하기3. All-To-All 모든 지점에서 모든 지점까지의 최단경로 구하기 문제의 조건마다 사용되는 알고리즘이 다르기때문에 적절히 선택해서 사용해야 한다.그러려면 어떤 알고리즘이 있는지 알아야 할 것! 1. 다익스트라(Dijkstra) 알고리즘 목적 단일 시작점에서 다른 모든 노드까지의 최단 경로를 구하는 것원하는 목적지가 나오면 종료할 수도 있음 그래프 유형 가중치가 있는 방향성 또는 무방향성 그래프 - 음수 가중치 허용 X 시간복잡도 O((V+E)⋅log⁡V) 구현방식1. 시작 노드의 거리를 0..

• format_list_bulleted 알고리즘
• · 2025. 1. 20.
• textsms

1. 알고리즘이란

알고리즘의 정의 컴퓨터가 계산이나 기타 문제 해결 작업을 수행할 때 따라야 하는 프로세스 또는 일련의 규칙문제 풀이에 필요한 계산 절차 또는 처리 과정의 순서를 뜻함 알고리즘 문제는 답을 찾는 것도 중요하지만 효율적인 방식으로 푸는 것도 중요하다.문제의 효율을 따질때는 보통 시간복잡도와 공간복잡도를 고려한다. 공간복잡도 공간 복잡도란 프로그램 실행과 완료에 얼마나 많은 공간(메모리)가 필요한지를 나타낸다.알고리즘을 실행시키기 위해 필요한 공간(space)는 두 가지로 나눌 수 있다.알고리즘과 무관한 공간, 즉 고정 공간코드가 저장되는 공간, 알고리즘 실행을 위해 시스템이 필요로 하는 공간 등알고리즘과 밀접한 공간, 즉 가변 공간문제를 해결하기 위해 알고리즘이 필요로 하는 공간.변수를 저장하는 공간, 순환..

• format_list_bulleted 알고리즘
• · 2024. 11. 24.
• textsms