반응형 다익스트라8 [C/C++] 프로젝트 오일러 #83 Path sum: four ways(다익스트라) #83 문제는 난이도 25%로 설정되어 있습니다. 동적 계획법 등으로는 구현하기 어렵고, 다익스트라 알고리즘을 사용해야 합니다. 다익스트라 알고리즘 자체는 너비 우선 탐색, 프림 알고리즘과 비슷한 구현 방법으로 큐 자료구조와 우선순위 큐 자료구조의 이해가 필요합니다. https://projecteuler.net/problem=83 다익스트라 알고리즘 구현은 그래프에서 경로 찾기에서 자주 나옵니다. https://sdev.tistory.com/119 다익스트라 알고리즘 다익스트라 알고리즘은 시작점에서 다른 모든 경로로 가는 최단 거리에 대한 그래프(트리)를 만들어줍니다. 다익스트라 알고리즘을 사용하려면, 힙을 이용해서 최소의 엔티티를 찾는 것이 필요 sdev.tistory.com https://sdev.t.. 2023. 5. 6. [C/C++] 백준 #1939 중량제한(그래프) 이번 문제는 프림이나 다익스트라와 비슷하게 동작하지만, 경로에 걸쳐있는 간선중, 최소값의 간선값이 해당 경로값이 됩니다. 이 경로값이 가장 큰 것을 찾는 문제입니다. 그래서 프림 알고리즘이나 다익스트라 알고리즘을 곧이 곧대로 사용할 수가 없습니다. 제가 사용한 탐욕 방법은 이것입니다. 0) 모든 노드의 값을 0으로 초기화합니다. 1) 출발지점에서 가장 큰 노드값을 가지고 있는 노드를 선택합니다. 2) 이동할 수 있는 모든 간선들을 적용하여 도착할 곳의 노드값을 결정합니다. 도착할 노드값은 현재보다 큰 경우 노드값을 저장하고, 우선순위큐에 해당 값을 넣습니다. 3) 도착지점이 가장 큰 노드값인 경우 종료합니다. 이 상태에서 선택할 수 있는 다른 노드값은 도착지점보다 적은 값이므로 의미가 없습니다. 제가 작.. 2022. 11. 19. [C/C++] 백준 #1916 최소비용 구하기(다익스트라) 이번 문제는 다익스트라 알고리즘을 이용해서 최소 경로를 구하는 문제입니다. 다익스트라 알고리즘은 Edsger W. Dijkstra(독일 : 데이크스트라 또는 다이크스트라)가 개발한 알고리즘입니다. 프림 알고리즘과 비슷하지만, 누적 간선 가중치의 값을 노드의 값으로 한다는 점이 다릅니다. DFS, 프림, 다익스트라, A* 알고리즘은 모두 비슷한 형태로 구성이 되어서 이해하면 쉽게 구현이 가능합니다. 다익스트라를 구현하는 방법은 거의 일정합니다. 다익스트라 기본 알고리즘은 시작정이 주어지고, 나머지 모든 노드들까지의 최소 경로값을 구하는 것이지만, 여기서는 도착점이 주어지기 때문에, 도착점이 선택되면, 그 부분에서 멈추도록 합니다. 이 문제에서는 저는 인접행렬과 힙을 이용해서 구현해보았습니다. 일반적으로는 .. 2022. 11. 6. [C/C++] 백준 #1753 최단경로(다익스트라) 이번 문제는 문제 자체가 다익스트라 알고리즘으로 푸는 문제입니다. 유향 그래프(directed graph)가 주어졌을 때, 시작점에서 출발해서, 다른 모든 노드들까지의 최단 경로를 찾는 것입니다. 정확하게 다익스트라 알고리즘입니다. 저는 일단 해시맵(unordered map)을 이용해서 인접리스트를 구성했습니다. 그렇게 했던 가장 큰 이유는 두개의 정점사이에 두개 이상의 간선이 존재할 수 있다는 조건때문이었죠. 물론 벡터(vector)를 이용한다고 해서 문제가 되지는 않습니다. 최단거리이므로, 알아서 최소값을 찾아서 갈테니까요. 이것은 필수라기보다는 선택이라고 보입니다. 우선순위큐는 힙(heap) 자료구조를 이용해서 구현하였습니다. 우선순위큐를 바로 사용해도 괜찮은 선택입니다. 제 경우에는 힙을 직접 쓰.. 2022. 10. 10. [C/C++] 프로젝트 오일러 #82 path sum : three ways(다익스트라) 이번 문제는 앞에 #81 문제와 동일하게 경로의 합을 구하는데 있어서 최소의 경로값을 잦는 것입니다. 앞의 문제가 two ways였던 것에 비해서 이번 것은 three ways입니다. 프로젝트 오일러 문제들 초창기가 제가 알고리즘 문제들 풀기 시작한 초기였던 점을 생각했을 때, 지금 보면 유치하기 짝이 없네요. 일단 힙구조를 사용하지도 않고 짰고, 삽입정렬을 이용해서 짰네요. 뭐 삽입정렬을 한다고 한다면, \(O(N^2)\) 알고리즘이었다는 것이죠. 이것 작성할 때만 해도 STL 사용도 안 했을 때이니까요. 우선순위 큐를 사용하면 해결되었을텐데요. 행렬이 크기 않았기 때문에 풀 수 있던 것이죠. 동적 계획법으로 풀 수도 있습니다. 하지만 사이클이 있기때문에 반복을 많이 해야 안정된 값이 나오게 됩니다. .. 2022. 10. 10. #1504 특정한 최단 경로 특정한 최단 경로는 중간에 두군데의 지점을 반드시 통과하는 경로중 최단 경로를 찾아라하는 문제입니다. 중간에 두군데의 지점을 반드시 통과하기 위해서는 [시작]-[지점1]-[지점2]-[끝]을 가는 경로와 [시작]-[지점2]-[지점1]-[끝]을 가는 경로중 거리가 짧은 것을 선택하시면 됩니다. 기본적인 알고리즘은 다익스트라(Dijkstra)의 변형입니다. 다익스트라 변형은 도착지점이 큐에서 나오면, 더이상 계산하지 않도록 하는 것입니다. 무방향 그래프이므로 [지점1]-[지점2]와 [지점2]-[지점1]은 같은 값입니다. 제가 구현한 소스입니다. 소스는 참조용으로만 봐주세요. //--------------------------------------------------------------------------.. 2022. 8. 22. 이전 1 2 다음 728x90
