평면상의 수많은 선분들 중에서 교차하는 모든 쌍을 효율적으로 찾는 문제(Line Segment Intersection)를 해결하기 위한 Line Sweep 알고리즘의 원리를 설명하고, 이 알고리즘이 O((N+K) log N) (N은 선분 개수, K는 교차점 개수) 시간 복잡도를 가지는 이유를 자료구조(예: BST)의 역할과 함께 설명하시오.
힌트 · Line Sweep 알고리즘은 가상의 스위프 라인을 이동시키며 이벤트 포인트(선분 시작/끝, 교차점)에서 자료구조(예: 균형 이진 탐색 트리)를 업데이트하여 교차 여부를 판단합니다. 이 자료구조의 삽입/삭제/탐색 비용이 log N이고, 총 이벤트 수가 N+K이기 때문에 해당 복잡도를 가집니다.
모범답안
Line Sweep 알고리즘은 평면 상의 선분 교차 문제를 효율적으로 해결하는 방법입니다. 핵심 아이디어는 가상의 수직선(sweep line)을 왼쪽에서 오른쪽으로 쓸면서 지나가면서, 이 선에 걸리는 선분들을 관리하는 것입니다.
선분이 시작되거나 끝나는 점, 또는 교차점이 발생할 가능성이 있는 점들을 이벤트 포인트로 관리하고, 이 이벤트들을 x좌표 기준으로 정렬합니다. Sweep line이 이벤트 포인트를 지날 때마다, 해당 위치에서 활성화되는 선분들을 균형 이진 탐색 트리(BST)에 삽입하거나 삭제합니다.
BST는 sweep line과 교차하는 선분들을 y좌표 순서대로 정렬된 상태로 유지합니다. 새로운 선분이 삽입될 때, BST에서 인접한 선분들과 교차하는지 확인하여 교차점을 찾습니다.
시간 복잡도는 이벤트 포인트를 정렬하는 데 O(N log N), 각 이벤트 포인트에서 BST 삽입/삭제/탐색에 O(log N)이 소요됩니다. 총 이벤트 수는 선분 시작/끝 점 N개와 교차점 K개, 즉 N+K개이므로, 전체 시간 복잡도는 O((N+K) log N)이 됩니다. BST를 사용하여 활성 선분들을 효율적으로 관리함으로써 불필요한 비교를 줄이는 것이 핵심입니다.
읽었다면, 이제 직접 답해볼 차례예요
패스잇 앱에서 이 질문에 말로 답하면 AI가 꼬리질문까지 이어가며 1:1 코칭합니다.
함께 보는 알고리즘 면접 질문
- 대규모 데이터셋에서 동적 계획법(Dynamic Programming)을 적용할 때, DP 테이블의 크기가 너무 커지거나 상태 전이 비용이 높아져 발생하는 성능 문제를 해결하기 위한 고급 최적화 기법(예: Convex Hull Trick, Divide and Conquer Optimization, Monotonic Queue Optimization)들을 설명하고, 각 기법이 어떤 형태의 점화식에 적용될 수 있는지 구체적인 예시를 들어 설명하시오.
- 네트워크 플로우(Network Flow) 문제 해결을 위한 알고리즘 중 Dinic 알고리즘이 Edmonds-Karp나 Ford-Fulkerson 알고리즘에 비해 실제 환경에서 훨씬 효율적인 이유를 설명하고, Dinic 알고리즘의 핵심 단계인 레벨 그래프 구성과 블로킹 플로우(Blocking Flow)를 찾는 과정을 자세히 설명하시오.
- 대용량 텍스트 데이터에서 모든 반복되는 부분 문자열을 효율적으로 찾거나, 두 문자열의 최장 공통 부분 문자열(Longest Common Substring)을 찾는 문제에 Suffix Array와 Suffix Tree를 어떻게 적용할 수 있는지 설명하고, 두 자료구조의 구현 복잡도, 공간 효율성, 그리고 특정 문제 해결에 있어서의 장단점을 비교 분석하시오.
- 일반적인 세그먼트 트리로는 처리하기 어려운 '구간 내 모든 값에 특정 연산 적용 후 특정 값으로 클램핑' 또는 '구간 내 최댓값을 특정 값으로 변경'과 같은 복잡한 구간 업데이트를 효율적으로 처리하기 위한 Segment Tree Beats(혹은 Advanced Lazy Propagation)의 동작 원리를 설명하고, 어떤 조건에서 이러한 최적화가 가능하며 실제 어떤 문제에 적용될 수 있는지 예시를 들어 설명하시오.
- 대규모 데이터셋에서 정확한 해를 찾기 어렵거나 시간이 너무 오래 걸릴 때, 확률적 알고리즘(Probabilistic Algorithms)이 대안이 될 수 있습니다. Monte Carlo 알고리즘과 Las Vegas 알고리즘의 차이점을 명확히 설명하고, 각각 어떤 종류의 문제에 적합하며 실제 시스템(예: 스트리밍 데이터 처리, 암호화)에서 어떻게 활용될 수 있는지 구체적인 사례를 들어 설명하시오.
- NP-hard 문제의 경우 다항 시간 내에 최적해를 찾는 것이 불가능합니다. 이럴 때 근사 알고리즘(Approximation Algorithms)을 사용하는데, TSP(Traveling Salesperson Problem)나 Vertex Cover와 같은 문제에서 근사 알고리즘이 어떻게 설계될 수 있는지 설명하고, 근사 비율(Approximation Ratio)의 의미와 중요성, 그리고 이를 증명하는 방법에 대해 논하시오.