CS 기초 · 심화
네트워크 플로우(Network Flow) 문제 해결을 위한 알고리즘 중 Dinic 알고리즘이 Edmonds-Karp나 Ford-Fulkerson 알고리즘에 비해 실제 환경에서 훨씬 효율적인 이유를 설명하고, Dinic 알고리즘의 핵심 단계인 레벨 그래프 구성과 블로킹 플로우(Blocking Flow)를 찾는 과정을 자세히 설명하시오.
힌트 · Dinic 알고리즘은 BFS로 레벨 그래프를 구성하여 최단 경로 상의 증강 경로들을 찾고, DFS로 블로킹 플로우를 탐색하여 한 번의 레벨 그래프 구성으로 여러 증강 경로를 효율적으로 처리함으로써 성능을 향상시킵니다.
레벨 그래프블로킹 플로우BFS잔여 네트워크시간 복잡도
모범답안
Dinic 알고리즘은 Edmonds-Karp나 Ford-Fulkerson보다 실제 환경에서 훨씬 효율적인 이유는, 한 번의 레벨 그래프 구성으로 여러 개의 증강 경로를 동시에 찾고 처리하기 때문입니다.
핵심 단계는 다음과 같습니다.
먼저 BFS를 이용해 소스에서 싱크까지의 최단 경로 길이를 기준으로 레벨 그래프를 구성합니다. 이 레벨 그래프는 각 노드의 소스로부터의 최단 거리를 나타냅니다.
이후 DFS를 이용해 레벨 그래프 상에서 블로킹 플로우를 찾습니다. 블로킹 플로우란, 더 이상 레벨 그래프 상에서 소스에서 싱크로 도달할 수 없을 때까지 모든 가능한 증강 경로를 통해 최대한의 유량을 흘려보내는 것을 의미합니다.
이러한 레벨 그래프 구성과 블로킹 플로우 탐색 과정을 반복하면, 각 단계마다 잔여 네트워크에서 최단 경로를 따라 유량을 증가시키므로 전체적인 수렴 속도가 빨라져 효율성이 높아집니다.
읽었다면, 이제 직접 답해볼 차례예요
패스잇 앱에서 이 질문에 말로 답하면 AI가 꼬리질문까지 이어가며 1:1 코칭합니다.
함께 보는 알고리즘 면접 질문
- 우선순위 큐(Priority Queue)를 구현할 때 힙(Heap) 자료구조를 사용하는 주된 이유와, 힙의 삽입 및 삭제 연산이 어떻게 동작하는지 설명해주세요.
- 두 개의 포인터(Two Pointers) 기법이 어떤 문제들을 효과적으로 해결할 수 있는지 두 가지 예시를 들고, 각 예시에서 이 기법이 어떻게 적용되는지 설명해주세요.
- 대규모 데이터셋에서 동적 계획법(Dynamic Programming)을 적용할 때, DP 테이블의 크기가 너무 커지거나 상태 전이 비용이 높아져 발생하는 성능 문제를 해결하기 위한 고급 최적화 기법(예: Convex Hull Trick, Divide and Conquer Optimization, Monotonic Queue Optimization)들을 설명하고, 각 기법이 어떤 형태의 점화식에 적용될 수 있는지 구체적인 예시를 들어 설명하시오.
- 대용량 텍스트 데이터에서 모든 반복되는 부분 문자열을 효율적으로 찾거나, 두 문자열의 최장 공통 부분 문자열(Longest Common Substring)을 찾는 문제에 Suffix Array와 Suffix Tree를 어떻게 적용할 수 있는지 설명하고, 두 자료구조의 구현 복잡도, 공간 효율성, 그리고 특정 문제 해결에 있어서의 장단점을 비교 분석하시오.
- 평면상의 수많은 선분들 중에서 교차하는 모든 쌍을 효율적으로 찾는 문제(Line Segment Intersection)를 해결하기 위한 Line Sweep 알고리즘의 원리를 설명하고, 이 알고리즘이 O((N+K) log N) (N은 선분 개수, K는 교차점 개수) 시간 복잡도를 가지는 이유를 자료구조(예: BST)의 역할과 함께 설명하시오.
- 일반적인 세그먼트 트리로는 처리하기 어려운 '구간 내 모든 값에 특정 연산 적용 후 특정 값으로 클램핑' 또는 '구간 내 최댓값을 특정 값으로 변경'과 같은 복잡한 구간 업데이트를 효율적으로 처리하기 위한 Segment Tree Beats(혹은 Advanced Lazy Propagation)의 동작 원리를 설명하고, 어떤 조건에서 이러한 최적화가 가능하며 실제 어떤 문제에 적용될 수 있는지 예시를 들어 설명하시오.