AOE(Activity On Edge) 네트워크에서 해당 작업의 가장 … | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 08년 1회차
AOE(Activity On Edge) 네트워크에서 해당 작업의 가장 이른 시간(earliest time)과 가장 늦은 시간(latest time)을 각각 나타내는 early(i)와 late(i)를 구하고자 한다. 가장 이른 사건 발생 시간(earliest event occurrence time)을 earliest라고 하고, 가장 늦은 사건 발생 시간(latest event occurrence time)을 latest라고 할 때, 작업 ai가 간선 <k, l>로 표현된다면, 다음 식으로부터 early(i)와 late(i)를 구할 수 있다.
early(i) = earliest[k]
late(i) = latest[l] - 작업 ai의 작업 시간(duration)
다음과 같은 AOE 네트워크에서 early(i)와 late(i)를 구한 결과 중 옳지 않은 것은?
문제 이미지
1
early(3) = 6, late(3) = 10
2
early(5) = 10, late(5) = 10
3
early(7) = 7, late(7) = 12
4
early(9) = 14, late(9) = 14
해설

작업 a3은 early(3) = 6이지만 late(3) = 11이므로, late(3)을 10으로 제시한 결과가 옳지 않다.

전진 계산으로 earliest를 구하면 V1 = 6, V3 = 10, V4 = 7, V6 = 14, V7 = 11, V8 = 19이다. 후진 계산으로 latest를 구하면 V6 = 14, V7 = 16, V4 = min(14 − 2, 16 − 4) = 12이다.

a3은 간선 <1, 4>, 작업 시간 1이므로 late(3) = latest[4] − 1 = 11이다.

  • early(5) = 10, late(5) = 10: a5는 <3, 6>, 시간 4로 earliest[3] = 10, latest[6] − 4 = 10이다.
  • early(7) = 7, late(7) = 12: a7은 <4, 7>, 시간 4로 earliest[4] = 7, latest[7] − 4 = 12이다.
  • early(9) = 14, late(9) = 14: a9는 <6, 8>, 시간 5로 earliest[6] = 14, latest[8] − 5 = 14이다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 국가직 자료구조론] 08년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기