한국어
메뉴

자료 구조와 알고리즘

다익스트라 알고리즘으로 올바른 최단 경로를 구하기 위한, 그래프에 관한 조건으로 올바른 것은?

  1. A그래프에 사이클(같은 정점으로 돌아오는 경로)이 없을 것
  2. B간선에 방향이 없을 것
  3. C간선의 가중치가 모두 0 이상일 것
정답과 해설 보기

정답: C. 간선의 가중치가 모두 0 이상일 것

다익스트라 알고리즘은 미확정 정점 중 거리가 가장 작은 것을 확정합니다. 이는 다른 정점을 거치면 거리가 늘어나는 일은 있어도 줄어드는 일은 없다는 전제에 기반합니다. 음의 가중치를 가진 간선이 있으면 나중에 다른 경로로 거리가 짧아지는 경우가 있으며, 예를 들어 S→A가 2, S→B가 3, B→A가 −2인 방향 그래프에서는 A를 2로 확정한 뒤에 S→B→A의 1이 발견됩니다. 음의 가중치가 있을 때는 벨먼-포드 알고리즘 등을 사용합니다. 사이클이 있어도, 간선에 방향이 있어도, 가중치가 0 이상이면 다익스트라 알고리즘을 사용할 수 있습니다.

이 분야 연습하기 분야로 돌아가기

자료 구조와 알고리즘의 다른 문제

  1. 작업 A~E에 'A는 C보다 앞', 'B는 C보다 앞', 'C는 D보다 앞', 'B는 E보다 앞', 'E는 D보다 앞'이라는 순서 제약이 있다. 모든 제약을 만족하는 작업의 순서(위상 정렬의 결과)는?
  2. 함수 f(x, y)를 'y가 0이면 x를 반환하고, 그렇지 않으면 f(y, x mod y)를 반환한다'로 정의한다. f(84, 36)을 호출했을 때의 반환값과, f가 호출되는 횟수(첫 호출 포함)의 조합은?
  3. 피보나치 수를 구하는 함수 fib(n)을 'n이 1 이하이면 n을 반환하고, 그렇지 않으면 fib(n−1) + fib(n−2)를 반환한다'로 재귀적으로 정의했다. fib(5)를 호출했을 때 fib가 호출되는 횟수는 첫 호출을 포함하여 몇 회인가?
  4. 1엔, 4엔, 6엔의 3종류 동전으로 8엔을 지불한다. 큰 동전부터 쓸 수 있는 만큼 쓰는 탐욕 알고리즘으로 정했을 때의 개수와 최소 개수의 관계로 올바른 것은?
  5. 용량 8인 배낭에 (무게, 가치)가 (2, 3), (3, 4), (4, 5), (5, 6)인 4개의 물건 중에서 골라 넣는다. 각 물건은 하나씩밖에 없고 나눌 수 없다. 무게의 합계가 8 이하일 때 가치 합계의 최댓값은 얼마인가?