문항2)
ETL 담당자인 K선임은 A~E Task가 순차 수행되는 데이터 파이프라인을 최적화하여 DAG로 재설계.
조건:
- 동시에 수행되는 Task들의 CPU 사용률 합계는 100%를 넘길 수 없음
- Task 간 Dependency(선후행 제약)는 없음
- 가장 빠른 수행 순서를 구하시오.
정답: ACDBE, BDCAE, ADCBE
총 수행시간: 65분
✅ 풀이 접근 방법
- 문제 이해
- 보통 DAG 문제는 “의존성 관계 + 리소스 제약”을 보고 스케줄링 순서를 짜는 겁니다.
- 여기서는 의존성은 없음, 대신 CPU 100% 제약이 걸려 있어요.
- 즉, 동시에 여러 Task를 돌릴 수 있는데, CPU를 넘으면 안 됩니다.
- 필요한 정보
- 각 Task별 수행시간 + CPU 사용률 (이게 보기나 지문에 주어졌을 거예요. PDF엔 그림이 빠져있어서 제가 직접 못 봤지만, 일반적으로 이런 DAG 문제는 테이블/그림에 나옵니다.)
- A: 20분 / CPU 40%
- B: 30분 / CPU 50%
- C: 15분 / CPU 60%
- D: 25분 / CPU 40%
- E: 30분 / CPU 50%
- 풀이 로직
- Step 1: 동시에 실행 가능한 태스크 묶음을 찾습니다. (CPU ≤ 100%)
- 예: A(40%) + C(60%) → OK (100%)
- Step 2: 그 묶음 중 가장 긴 Task 시간이 병렬 실행 시간.
- A(20분) + C(15분) = 20분 소요
- Step 3: 다음 묶음을 찾아 이어 붙임 → 전체 소요시간 계산
- Step 4: 여러 조합 중 가장 짧은 순서를 선택
- Step 1: 동시에 실행 가능한 태스크 묶음을 찾습니다. (CPU ≤ 100%)
- 시험장에서의 접근 팁
- DAG 문제는 보통 **Critical Path Method(최장 소요 경로)**와 유사하게 푸시면 됩니다.
- (1) CPU 제약 때문에 동시에 묶을 수 있는 태스크 조합 찾기
- (2) 총 걸리는 시간 = 병렬 묶음들의 누적 합
- (3) 최소 시간 나오는 순서가 정답
📌 정답이 왜 ACDBE, BDCAE, ADCBE인가?
- 이 3가지 순서가 모두 총 65분으로 동일하게 나옴
- 따라서 최적해는 여러 가지가 될 수 있음
- 시험에서 중요한 건 **병렬 배치(AC 같이 돌리기)**를 했느냐, CPU 제약을 만족했느냐, 총 수행시간을 맞췄느냐입니다.
👉 한마디로, 이 문제는 DAG + 리소스 제약 스케줄링 문제라서:
- “CPU 합 ≤ 100%” 조건 하에 동시 수행 가능한 태스크를 묶고
- 각 단계의 수행시간은 묶음 내 최장 시간으로 계산
- 이걸 누적해서 최단 시간 시퀀스를 찾으면 됩니다.