정렬 후 스캔은 애드혹 문제에서 의외로 자주 통하는 출발점입니다. 정렬은 데이터를 예쁘게 나열하는 습관이 아니라, 순서를 바꿔서 흩어진 규칙을 눈앞으로 끌어오는 작업입니다.
정렬이 통하는 문제는, 정렬한 뒤에는 멀리 있는 후보를 다 보지 않아도 되고 가까운 것만 봐도 되는 구조가 생깁니다. 이번 글은 인접 비교, 구간 정렬, 쌍 맞추기, 한 번에 스캔하는 감각을 쉬운 예시부터 단계적으로 정리합니다.
정렬 후 스캔
정렬 후 스캔은 먼저 데이터를 어떤 기준으로 정렬하고, 그다음 앞에서부터 한 번 또는 양끝에서 한 번 훑는 방식입니다. 여기서 중요한 것은 정렬 그 자체가 아니라 정렬을 하고 나면 비교 대상이 줄어드는가입니다.
원래는 모든 쌍을 다 봐야 할 것 같던 문제가 정렬 뒤에는 이웃만 보면 되는 문제로 바뀌기도 하고, 복잡하게 섞인 구간들이 현재 끝점 하나만 기억하면 되는 문제로 바뀌기도 합니다. 즉, 정렬 후 스캔은 문제를 더 쉽게 읽히는 순서로 다시 배열하는 작업입니다.
왜 정렬이 규칙을 드러낼까
정렬의 가장 큰 장점은 가까운 것끼리 붙고, 왼쪽과 오른쪽의 의미가 생긴다는 점입니다. 정렬 전에는 3과 4가 멀리 떨어져 있을 수도 있지만, 정렬 후에는 작은 값은 왼쪽, 큰 값은 오른쪽이라는 질서가 생깁니다.
- 가장 비슷한 둘은 누구인가
- 지금 구간과 다음 구간은 겹치는가
- 작은 것부터 처리하면 놓치는 것이 없는가
- 현재 값이 너무 크면 어느 쪽을 버려야 하는가
애드혹 문제에서 정렬이 강한 이유는, 복잡한 상황을 한 축 위의 순서 문제로 바꿔주기 때문입니다. 이 순간부터는 모든 후보를 다시 계산하기보다 현재 상태를 갱신하는 쪽으로 풀이가 단순해집니다.
인접 비교
차이가 가장 작은 두 수를 찾는 문제를 떠올려보겠습니다. 처음에는 모든 쌍을 비교하고 싶어지지만, 정렬하고 나면 생각이 달라집니다. 정렬된 수열에서는 멀리 떨어진 둘 사이에 다른 값이 끼어 있을 수 있기 때문에, 최소 차이는 인접 원소 사이에서 나올 가능성이 가장 강합니다.
예를 들어 8, 1, 13, 4, 7을 정렬하면 1, 4, 7, 8, 13이 됩니다. 이제 1-4, 4-7, 7-8, 8-13만 보면 됩니다. 정렬 전에는 보이지 않던 가까움이 정렬 후에는 실제로 이웃 관계로 드러나기 때문입니다.
def min_adjacent_difference(nums):
nums.sort()
answer = float("inf")
for i in range(1, len(nums)):
answer = min(answer, nums[i] - nums[i - 1])
return answer이 코드는 정렬 뒤에 비교 범위를 과감하게 줄였다는 점이 핵심입니다. 브루트포스처럼 모든 쌍을 만들지 않아도 되는 이유를 먼저 이해하면 코드도 자연스럽게 따라옵니다.
구간 정렬
구간 문제도 정렬 후 스캔이 아주 자주 통합니다. 예를 들어 회의 시간대가 여러 개 있을 때 겹치는 구간을 합치라고 하면, 정렬 전에는 누가 누구와 겹치는지 바로 판단하기 어렵습니다.
하지만 시작 시간 기준으로 정렬하면 흐름이 생깁니다. (5, 7), (1, 3), (2, 6), (8, 10)을 정렬하면 (1, 3), (2, 6), (5, 7), (8, 10)이 되고, 이제 앞에서부터 보면서 현재 끝점만 관리하면 됩니다.
구간 병합에서 중요한 기억 값은 과거의 모든 구간이 아니라, 현재까지 합쳐진 구간의 끝점 하나입니다. 이 점 때문에 정렬 뒤 선형 스캔이 가능해집니다.
def merge_intervals(intervals):
intervals.sort(key=lambda x: x[0])
merged = []
for start, end in intervals:
if not merged or merged[-1][1] < start:
merged.append([start, end])
else:
merged[-1][1] = max(merged[-1][1], end)
return merged구간 정렬이 통하는 이유는 시작점 순서가 생기면서 미래에 볼 구간들이 어떤 위치에 있는지 예측 가능해지기 때문입니다. 그래서 현재 구간과 다음 구간만 비교하면서도 안전하게 진행할 수 있습니다.
쌍 맞추기
두 집합을 가능한 한 잘 연결해야 하는 문제에서도 정렬은 강합니다. 예를 들어 아이들 키가 [130, 150, 160], 좌석 높이가 [128, 155, 162]라면 두 배열을 정렬한 뒤 앞에서부터 맞추는 방식이 자연스럽습니다.
- 130 ↔ 128
- 150 ↔ 155
- 160 ↔ 162
작은 값을 뒤쪽의 큰 값과 무리하게 연결하면 중간에 있던 더 가까운 후보를 오히려 놓치기 쉽습니다. 그래서 학생과 장비, 사람과 방, 작업과 시간대처럼 비슷한 순서끼리 붙는 문제에서는 두 집합을 각각 정렬한 뒤 같은 인덱스나 두 포인터로 맞추는 전략이 자주 나옵니다.
물론 모든 매칭 문제가 정렬로 끝나는 것은 아닙니다. 하지만 “작은 것부터 처리해도 전체를 망치지 않는가”라는 질문에 예라고 답할 수 있다면, 정렬 후 스캔을 먼저 의심해볼 가치가 있습니다.
한 번에 스캔
정렬 후 스캔의 네 번째 대표 장면은 이벤트를 시간순으로 훑는 방식입니다. 예를 들어 행사 시작 시간과 종료 시간이 있을 때 어떤 순간에 사람이 가장 많이 겹치는지 구하는 문제를 생각해볼 수 있습니다.
이때는 각 구간을 직접 서로 비교하기보다, 시작은 +1, 종료는 -1 같은 이벤트로 바꾸고 시간순으로 정렬합니다. 그다음 앞에서부터 지나가며 현재 인원 수만 갱신하면 됩니다.
이 방식의 본질은 과거 전체를 다시 보는 것이 아니라 정렬된 흐름 속에서 현재 상태 하나만 업데이트하는 것입니다. 구간 병합, 스위프 라인, 일부 투 포인터 문제들이 모두 이 감각과 연결됩니다.
대표 학습 자료인 USACO Guide의 two pointers 정리도 정렬된 배열에서는 순서 정보 덕분에 모든 쌍을 다 보지 않아도 된다고 설명합니다. 핵심은 정렬이 후보를 버릴 근거를 만든다는 점입니다.
언제 안 통할까
정렬은 강하지만 만능은 아닙니다. 가장 흔한 실패는 원래 순서가 의미인 문제를 정렬해 버리는 경우입니다. 원소의 등장 순서, 원래 위치, 앞뒤 관계 자체가 정답의 일부라면 정렬이 오히려 중요한 정보를 지워 버릴 수 있습니다.
또 하나는 정렬을 해도 버릴 수 있는 후보가 생기지 않는 경우입니다. 현재 원소 하나만 보고 다음 행동을 정할 수 없다면, 정렬 후 스캔만으로는 부족할 수 있습니다. 그럴 때는 해시, 우선순위 큐, 세그먼트 트리, 동적 계획법 같은 다른 도구가 필요합니다.
Python 공식 정렬 문서도 정렬 기준을 key로 명확히 정해야 한다고 설명합니다. 알고리즘 문제에서도 마찬가지입니다. 무엇을 기준으로 정렬할지 애매하면, 아직 구조를 제대로 본 것이 아닐 수 있습니다.
실전 체크리스트
- 정렬해도 문제 의미가 유지되는가
- 정렬하면 비슷한 것들이 이웃하게 되는가
- 인접 원소만 비교해도 되는 구조가 있는가
- 현재 구간의 끝점이나 현재 상태 하나만 기억하면 되는가
- 한쪽을 버려도 정답을 놓치지 않는 이유를 설명할 수 있는가
이 다섯 가지 중 두세 개만 강하게 보여도 정렬 후 스캔을 먼저 의심해볼 만합니다. 특히 가장 가까운 두 값, 겹치는 구간, 최소 차이, 두 배열 매칭, 시간순 이벤트 처리 같은 표현은 강한 신호입니다.
정리
애드혹 문제에서 정렬은 단순한 준비 작업이 아닙니다. 정렬은 흩어진 데이터를 줄 세워서 인접 비교를 가능하게 만들고, 구간의 앞뒤 관계를 드러내고, 쌍 맞추기 규칙을 단순하게 만들고, 이벤트를 한 번에 스캔할 수 있게 만듭니다.
결국 핵심은 이것입니다. 정렬을 한 뒤에 무엇을 더 이상 안 봐도 되는지가 보이면, 그 문제는 이미 절반쯤 풀린 것입니다. 다음에 애드혹 문제를 만났을 때는 먼저 이렇게 물어보면 좋습니다. 이 문제는 순서를 바꾸면 더 쉬워지지 않을까? 그 질문이 정렬 후 스캔의 출발점입니다.
