2565번 "교차 최소화를 위한 선 제거 알고리즘"을 해결하며 동적 계획법(DP)과 최장 증가 부분수열(LIS)의 연관성을 깊이 이해하는 시간을 가졌습니다. 처음에는 직관적인 탐욕적 접근으로 시작했지만, 문제의 본질을 파고들수록 DP와 LIS가 정답으로 향하는 길임을 깨닫게 되었습니다.

교차 최소화를 위한 선 제거 알고리즘: LIS로 해결하기

알고리즘 문제 2565번 "교차 최소화를 위한 선 제거 알고리즘"을 해결하며 동적 계획법(DP)과 최장 증가 부분수열(LIS)의 연관성을 깊이 이해하는 시간을 가졌습니다. 처음에는 직관적인 탐욕적 접근으로 시작했지만, 문제의 본질을 파고들수록 DP와 LIS가 정답으로 향하는 길임을 깨닫게 되었습니다.

학습 주제

공부 주제: 알고리즘 문제 풀이 (2565번: 교차 최소화를 위한 선 제거 알고리즘)
대화 제목: 교차 최소화를 위한 선 제거 알고리즘
학습 날짜: 2026년 2월 13일

질문과 탐구

처음에는 각 줄을 제거했을 때 교차가 얼마나 줄어드는지 계산하여 가장 효과적인 줄을 제거하는, 일종의 탐욕적(greedy) 접근을 시도했습니다. 하지만 AI와의 대화를 통해 이러한 탐욕적 방식이 항상 최적해를 보장하지 않는다는 점을 알게 되었습니다. 특정 줄을 제거했을 때 이후 상태에서 다른 줄들의 교차 감소 효율이 달라질 수 있기 때문입니다.

이후 DP 문제임을 인지하고, DP 상태를 어떻게 정의해야 할지에 대한 탐구가 시작되었습니다. "최소/최대를 구하라"는 문제의 성격과 "현재 선택이 이후 상태에 영향을 미친다"는 점, 그리고 "상태를 정의하고 중복 계산이 발생한다"는 DP의 특징을 파악하며, "현재 남은 줄들의 집합"을 상태로 정의하고 점화식을 세우는 방향으로 나아갔습니다.

하지만 "남은 줄들에서 교차를 0으로 만드는 최소 제거 줄 개수"라는 DP 상태 정의는 완전 탐색으로 이어져 2^N의 시간 복잡도를 가지는 비효율적인 방법임을 깨달았습니다. N이 100 이하인 문제 특성상 이는 불가능한 접근이었습니다.

핵심 학습 내용

문제의 제약 조건과 교차 정의를 면밀히 분석하는 과정에서 결정적인 전환점을 맞았습니다.

교차 정의: 두 선분 a→b와 a'→b'가 교차하는 조건은 (a' > a AND b' < b) OR (a' < a AND b' > b) 입니다.
교차하지 않는 조건: 이 교차 조건을 부정하면, (a' <= a OR b' >= b) AND (a' >= a OR b' <= b) 가 됩니다.
분배 법칙 적용: 위 식에 분배 법칙을 적용하고, 문제 조건 상 같은 위치에 줄이 연결될 수 없다는 점(a' ≠ a, b' ≠ b)을 고려하면, 교차하지 않는 조건은 (a' < a AND b' < b) OR (a' > a AND b' > b) 로 간결해집니다.

이것이 의미하는 바는 다음과 같습니다. 두 전봇대 A와 B 사이에 연결된 줄들이 있을 때, A 전봇대의 연결 위치 순서대로 줄들을 정렬했을 때, B 전봇대의 연결 위치도 동일하게 증가 순서를 유지해야만 줄들이 서로 교차하지 않는다는 것입니다.

이는 곧 "A 전봇대 연결 위치로 정렬했을 때, B 전봇대 연결 위치들의 최장 증가 부분수열(LIS)을 찾는 문제"와 같다는 결론에 도달했습니다. 따라서, 전체 줄의 개수에서 LIS의 길이를 빼면 최소한으로 제거해야 하는 줄의 개수를 구할 수 있습니다.

LIS 계산: N ≤ 100 이므로 O(N²) DP 또는 O(N log N) 이진 탐색 기반 LIS 알고리즘을 사용할 수 있습니다. 여기서는 O(N²) DP를 사용하여 구현했습니다.
최종 해법:
1. 입력받은 줄들을 A 전봇대 연결 위치 기준으로 정렬합니다.
2. 정렬된 줄들의 B 전봇대 연결 위치들로 이루어진 수열에서 LIS의 길이를 구합니다.
3. 전체 줄 개수 - LIS 길이 = 최소 제거 줄 개수

이해한 내용

처음에는 직관적인 탐욕 알고리즘으로 접근했으나, 문제의 구조를 깊이 파고들수록 DP와 LIS로 이어지는 과정이 흥미로웠습니다. 특히, 교차 조건을 논리적으로 분석하여 LIS를 도출하는 과정은 문제 해결의 핵심 아이디어였습니다.

DP와 LIS의 연결: "최소 제거"라는 문제를 "최대 유지" 문제로 바꾸어 LIS를 활용할 수 있다는 점이 인상 깊었습니다.
논리적 분석의 중요성: 수학적 정의를 기반으로 논리 연산을 통해 문제의 숨겨진 구조(LIS)를 발견하는 과정은 문제 해결 능력을 향상시키는 데 큰 도움이 되었습니다.

실전 적용

이 문제는 프로그래밍 경진대회 등에서 자주 출제되는 유형으로, 주어진 제약 조건과 문제 상황을 정확히 이해하고 적절한 알고리즘으로 모델링하는 능력을 기르는 데 매우 유용합니다.

추가 학습 계획

LIS 알고리즘의 O(N log N) 구현 방법을 더 깊이 이해하고 비교 분석할 계획입니다.
"DP 감지 포인트"를 익히고, 다양한 DP 문제에 적용하는 연습을 통해 문제 해결 역량을 강화하고자 합니다.
다음 학습 주제로는 그래프 탐색 알고리즘 또는 문자열 관련 DP 문제들을 고려하고 있습니다.

참고 자료

문제: 백준 2565번 - 전깃줄 (https://www.acmicpc.net/problem/2565)
알고리즘: 최장 증가 부분수열 (LIS) 알고리즘