배포 작업의 의존 순서를 위상 정렬했는데 일부 작업이 남습니다. 순환과 여러 유효 순서는 어떻게 다루나요?
잠깐, 답변을 보기 전에
먼저 내 말로 설명해 볼까요?
답변과 점검 포인트 펼치기답변 접기
구두 답변
정의를 외우기보다, 원리와 조건을 연결해 설명해 보세요.
위상 정렬은 방향 비순환 그래프의 의존 순서를 구합니다. Kahn 방식에서 진입 차수 0인 노드를 모두 처리한 뒤 노드가 남으면 순환에 연관된 의존이 있을 수 있습니다.
동작 원리와 전제
여러 진입 차수 0 노드 중 무엇을 먼저 고르는지에 따라 유효 순서가 여러 개일 수 있습니다. 재현 가능한 출력이 필요하면 안정적인 ID·우선순위로 선택합니다. 남은 노드 모두가 cycle 자체에 속하는 것은 아니고 cycle에 의존해 막힌 노드도 포함될 수 있습니다.
선택과 실패 처리
정확한 cycle 경로가 필요하면 DFS 색 상태나 strongly connected component를 이용해 진단합니다. 실행 가능한 독립 작업을 병렬화하되 선행 작업의 실제 성공을 확인한 뒤 후속을 시작해야 합니다. 정렬 결과만으로 실행 실패 처리가 해결되지 않습니다.
구체적인 사례와 검증
A가 B를, B가 A를 기다리고 C가 B에 의존하면 Kahn 방식에서 A·B·C가 모두 남을 수 있지만 실제 cycle은 A·B입니다. C를 cycle 원인으로 잘못 표시하면 진단이 어려워집니다. SCC나 DFS의 방문 상태로 실제 순환 경로를 찾아 사용자에게 보여 줍니다. 동시에 준비된 두 노드를 ID순으로 고르면 결과를 재현하기 쉽지만 실행 비용이 다른 경우 scheduling 정책은 별도입니다. 정렬된 순서에서 앞 작업이 실패하면 뒤 작업을 실행할지 중단할지 상태 머신으로 관리해야 합니다. 그래프의 유효성과 작업의 실제 성공은 다른 검증 단계입니다.
자기 의존·중복 간선·여러 성분·cycle 뒤 의존·동점 순서를 시험합니다. 설정 오류를 임의 순서로 무시하고 실행하지 않습니다. 의존 그래프의 구조와 런타임 작업 상태는 별도 계약입니다.
득점 포인트
이해가 드러나는 지점을 확인해 보세요.
- 핵심 구분: 위상 정렬은 방향 비순환 그래프의 의존 순서를 구합니다.
- 선택 조건: 정확한 cycle 경로가 필요하면 DFS 색 상태나 strongly connected component를 이용해 진단합니다.
- 검증 기준: 자기 의존·중복 간선·여러 성분·cycle 뒤 의존·동점 순서를 시험합니다.
감점 포인트
놓치기 쉬운 조건과 오해를 짚어 보세요.
- 위상 정렬 뒤 남은 모든 노드가 반드시 cycle 자체에 속한다고 한다.
더 파고들 거리
하나 더 질문하며 이해의 범위를 넓혀 보세요.
- 방향·중복·역간선과 실제 순회·갱신 요구에 맞춰 그래프를 어떻게 저장하나요?
- 선행 작업 성공 뒤 후속 배포를 시작하려면 순서 정의 외에 어떤 실패 정책이 필요한가요?
- 여러 하위 작업 중 하나가 실패하면 필수·선택 결과와 남은 자원 수명을 어떻게 나누나요?
득점·감점 포인트는 학습용 자기 점검 기준이며, 특정 회사의 실제 채점표가 아닙니다.
원리부터 공부하고 싶다면
답변을 보충하는 개념·예제·슈도코드를 읽어 보세요.