한국어
메뉴

자료 구조와 알고리즘

작업 A~E에 'A는 C보다 앞', 'B는 C보다 앞', 'C는 D보다 앞', 'B는 E보다 앞', 'E는 D보다 앞'이라는 순서 제약이 있다. 모든 제약을 만족하는 작업의 순서(위상 정렬의 결과)는?

  1. AA, C, B, E, D
  2. BB, A, E, C, D
  3. CB, E, D, A, C
정답과 해설 보기

정답: B. B, A, E, C, D

B, A, E, C, D에서는 A와 B가 C보다 앞, C와 E가 D보다 앞, B가 E보다 앞으로, 5개의 제약을 모두 만족합니다. A, C, B, E, D는 B보다 먼저 C를 하고 있으므로 'B는 C보다 앞'에 어긋나고, B, E, D, A, C는 C보다 먼저 D를 하고 있으므로 'C는 D보다 앞'에 어긋납니다. 위상 정렬은 방향이 있고 사이클이 없는 그래프(DAG)에서 모든 간선이 앞에서 뒤로 향하도록 정점을 나열하는 조작으로, 들어오는 간선이 없는 정점부터 차례로 꺼내는 방법(칸 알고리즘)이나 깊이 우선 탐색으로 구할 수 있습니다. 답이 하나라고는 할 수 없으며, 이 예에서는 제약을 만족하는 순서가 5가지 있습니다.

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

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

  1. 함수 f(x, y)를 'y가 0이면 x를 반환하고, 그렇지 않으면 f(y, x mod y)를 반환한다'로 정의한다. f(84, 36)을 호출했을 때의 반환값과, f가 호출되는 횟수(첫 호출 포함)의 조합은?
  2. 피보나치 수를 구하는 함수 fib(n)을 'n이 1 이하이면 n을 반환하고, 그렇지 않으면 fib(n−1) + fib(n−2)를 반환한다'로 재귀적으로 정의했다. fib(5)를 호출했을 때 fib가 호출되는 횟수는 첫 호출을 포함하여 몇 회인가?
  3. 1엔, 4엔, 6엔의 3종류 동전으로 8엔을 지불한다. 큰 동전부터 쓸 수 있는 만큼 쓰는 탐욕 알고리즘으로 정했을 때의 개수와 최소 개수의 관계로 올바른 것은?
  4. 용량 8인 배낭에 (무게, 가치)가 (2, 3), (3, 4), (4, 5), (5, 6)인 4개의 물건 중에서 골라 넣는다. 각 물건은 하나씩밖에 없고 나눌 수 없다. 무게의 합계가 8 이하일 때 가치 합계의 최댓값은 얼마인가?
  5. 문자열 안에서 패턴을 찾는 BM법(보이어-무어 알고리즘)의 특징으로 올바른 것은?