다익스트라알고리즘2 2022 국가 자료구조(나) 5 ~ 6번 해설 정답) 2 스택의 기본연산 push(i): 스택에 i 추가 pop(): 가장 마지막에 들어온 data 삭제 peek(): 스택 가장 윗 데이터 반환 여기서 pop()과 peek()의 차이점은 pop은 data가 삭제가 되지만, peek()는 삭제가 되지 않고 반환만 된다는 점이다. 이를 기억하고 문제를 풀어보자. 정답) 1 다익스트라 알고리즘은 한 정점에서 다른 정점까지의 최단거리를 구하는 알고리즘이다. 모든 정점을 탐색하며 최단 거리를 계속해서 갱신하는 것이 특징이다. 글로는 이해하기 어려우니 문제를 통해서 살펴보자. 우선, 정점 A로부터 다른 정점까지의 거리를 표로 나타내었다.연결되어있지 않은 정점들은 ∞로 표시하고, (A, B) = K 는 A에서 B까지의 거리가 K라는 의미로 사용하겠다. A B C.. 2023. 2. 1. 2022 서울시 자료구조(A) 해설 8번 정답) 3 이 문제는 다익스트라(Dijkstra) 알고리즘을 사용해서 구하면 쉽게 구할 수 있다. 다익스트라 알고리즘은 최단 경로를 찾은 후 그 경로를 경유하면 더 짧은 경로가 되는지 확인하고 값을 갱신해 나가는 알고리즘이다. 글로 적으면 어려우니 한 단계씩 알아가 보자. 의 표는 행은 출발지점, 열은 도착지점을 나타낸다. 이 문제는 출발지점이 서울인 경우만 살펴보면 되니 첫 번째 행을 가져오고, 이 행을 갱신하며 최단 경로를 찾도록 하자. 앞으로의 해설에서 (A, B)는 A가 출발점 B가 도착점을 의미한다. 서울 성남 평택 기흥 대구 서울 0 20 30 35 ∞ 이 표에서 최소 경로는 (서울, 성남)으로 20이다. 성남을 거쳐가는 경우를 모두 살펴보고 기존 경로보다 더 작은 경로가 나온다면 갱신해주도록.. 2022. 12. 15. 이전 1 다음
