Category/Algorithm8 다익스트라 알고리즘(Dijkstra's Algorithm) 다익스트라 알고리즘 (Dijkstra's Algorithm)은 그래프에서 단일 시작 정점에서 모든 다른 정점까지의 최단 경로를 찾는 알고리즘입니다. 가중치가 있는 그래프에서 음수 가중치가 없는 경우에 사용됩니다.알고리즘 동작 원리시작 정점에서의 거리 초기화:시작 정점의 거리를 0으로 설정하고, 나머지 모든 정점의 거리를 무한대로 설정합니다.최단 거리 확정:현재 확인한 정점 중 최단 거리인 정점을 선택하고 해당 정점의 거리를 확정합니다.이웃 정점 거리 업데이트:선택된 정점과 연결된 정점들의 거리를 업데이트합니다.반복:모든 정점의 거리가 확정될 때까지 위 과정을 반복합니다.필요한 자료 구조우선순위 큐(Priority Queue):최단 거리를 가진 정점을 효율적으로 찾기 위해 사용합니다.Python에서는 he.. 2024. 11. 22. 백트래킹(Backtracking) 백트래킹(Backtracking)은 탐색 알고리즘의 하나로, 모든 가능한 경우의 수를 탐색하면서도 불필요한 탐색을 줄이는 방법입니다. 이를 통해 효율적으로 정답을 찾아낼 수 있습니다.백트래킹의 핵심 아이디어모든 경우의 수를 탐색: 가능한 모든 해를 탐색하는 과정을 포함합니다.가지치기(Pruning): 탐색 도중 현재 경로가 유망하지 않다고 판단되면, 해당 경로를 더 이상 탐색하지 않고 되돌아가는 방식입니다.백트래킹의 특징완전 탐색 기반:백트래킹은 기본적으로 모든 경우를 탐색하지만, 불필요한 탐색을 피할 수 있습니다.재귀를 활용:대부분 재귀적으로 구현되며, 상태를 저장하고 탐색이 종료되면 이전 상태로 돌아갑니다.유망성 판단:탐색 도중 "이 경로는 정답이 될 가능성이 없다"고 판단되면 해당 경로를 탐색하지 .. 2024. 11. 21. 이전 1 2 다음