반응형 알고리즘/다익스트라10 백준 1753번 : 최단경로 java 이 문제는 다익스트라 알고리즘을 푸는 문제입니다. 이 문제를 풀 때 유의하셔야 하는 점은 메모리 제한이 256MB라는 점입니다. 저는 이 문제를 풀 때 처음에는 들어온 자료들을 2차원 배열에 입력하였습니다. 그러나 이 방식을 이용하면 정점의 개수가 최대인 20,000개일 때 20,000 * 20,000 * 4byte = 1,600,000,000byte 즉 이 2차원 배열을 int형으로 선언하는 데만도 1.6GB라는 어마어마한 메모리를 사용한다는 것을 알게 되었습니다. 따라서 이 문제를 다른 방식으로 풀 수 있나를 찾아보니 우선순위 큐를 이용하여 문제를 푸는 방법이 있어서 이 방법을 이용하여 다익스트라 알고리즘을 구현하였습니다. 문제를 푼 방법은 코드를 보면서 추가로 설명드리겠습니다. import java.. 2022. 5. 31. 백준 1916번 : 최소비용 구하기 java 이 문제는 다익스트라 알고리즘을 이용하는 문제입니다. 다익스트라 알고리즘에 대하여 설명드리겠습니다. 예제 1번을 예시로 다익스트라 알고리즘을 설명드리겠습니다. 예제 1번에서는 왼쪽 그림과 같이 도시가 존재합니다. 이제 주어진 입력값에 맞게 버스를 배치하겠습니다. 입력값들을 전부 입력하면 다음과 같은 그림이 됩니다. 다익스트라 알고리즘은 '한 점'에서 다른 모든 점까지 각각의 거리의 최솟값을 정하는 알고리즘입니다. 이 말에 대해서 이 문제를 풀어보면 더 자세히 알려드리도록 하겠습니다. 예제 1번에서는 1번에서 시작하여 5번까지 갈 때의 버스 비용의 최솟값을 찾으라고 하였습니다. 따라서 우리는 다익스트라 알고리즘이 시작하는 점을 1번으로 둘 수 있습니다. 이제 1번에서 시작하는 버스들을 제외하고는 잠시 지우.. 2022. 5. 29. 이전 1 2 다음 반응형
