Python을 사용하여 범위 배열 병합

발행: 2일 전 (2025년 12월 31일 오전 07:16 GMT+9)

12 min read

Source: Dev.to

파이썬으로 범위 배열을 병합하기

프로그래밍을 하다 보면 시작값과 끝값을 쌍으로 갖는 구간(범위)들의 리스트를 다루게 되는 경우가 많습니다.
예를 들어, 다음과 같은 구간들이 있다고 가정해 보세요.

ranges = [(1, 5), (3, 8), (10, 12), (11, 15)]

위 리스트에는 겹치는 구간이 존재합니다.
이러한 겹치는 구간들을 하나의 연속된 구간으로 합쳐야 할 때가 있습니다.
이 글에서는 파이썬만을 사용해 배열(리스트) 안에 있는 모든 구간을 병합하는 간단하고 효율적인 방법을 소개합니다.

1. 문제 정의

입력: (시작, 끝) 형태의 튜플을 원소로 갖는 리스트 ranges.
목표: 겹치거나 인접한 구간들을 하나의 구간으로 합쳐 새로운 리스트를 반환한다.
예시
- 입력: [(1, 5), (3, 8), (10, 12), (11, 15)]
- 출력: [(1, 8), (10, 15)]

2. 해결 전략

시작값을 기준으로 정렬한다.
정렬을 하면 겹치는 구간들이 연속해서 나타나므로 한 번의 순회만으로 병합이 가능하다.
결과 리스트 merged를 만든다.
- merged가 비어 있으면 현재 구간을 바로 추가한다.
- merged의 마지막 구간(prev)과 현재 구간(current)을 비교한다.
  - current의 시작값이 prev의 끝값보다 작거나 같으면 겹치는 구간이므로 두 구간을 합친다.
  - 그렇지 않으면 새로운 구간이므로 merged에 그대로 추가한다.

3. 구현 코드

아래 코드는 위 전략을 그대로 구현한 예시입니다.
코드 블록 내부는 그대로 유지하므로 번역하지 않았습니다.

def merge_ranges(ranges):
    # 시작값을 기준으로 정렬
    sorted_ranges = sorted(ranges, key=lambda x: x[0])
    merged = []

    for current in sorted_ranges:
        if not merged:
            # 첫 번째 구간은 무조건 추가
            merged.append(current)
        else:
            prev = merged[-1]
            # 현재 구간이 이전 구간과 겹치거나 인접하면 병합
            if current[0] <= prev[1]:
                merged[-1] = (prev[0], max(prev[1], current[1]))
            else:
                # 겹치지 않으면 새로운 구간으로 추가
                merged.append(current)

    return merged

사용 예시

ranges = [(1, 5), (3, 8), (10, 12), (11, 15)]
print(merge_ranges(ranges))
# 출력: [(1, 8), (10, 15)]

4. 동작 원리 상세 설명

정렬 단계
sorted(ranges, key=lambda x: x[0]) 은 구간들을 시작값이 작은 순서대로 정렬합니다.
정렬된 리스트는 [ (1,5), (3,8), (10,12), (11,15) ] 와 같이 됩니다.
첫 번째 구간 처리
merged 가 비어 있기 때문에 첫 구간 (1,5) 를 바로 merged 에 넣습니다.
두 번째 구간 (3,8)
- prev = (1,5)
- current[0] (=3) 가 prev[1] (=5) 보다 작으므로 겹칩니다.
- merged[-1] 를 (1, max(5,8)) 즉 (1,8) 로 업데이트합니다.
세 번째 구간 (10,12)
- prev = (1,8)
- current[0] (=10) 가 prev[1] (=8) 보다 크므로 겹치지 않습니다.
- 새로운 구간으로 merged 에 추가합니다 → [(1,8), (10,12)].
네 번째 구간 (11,15)
- prev = (10,12)
- current[0] (=11) 가 prev[1] (=12) 보다 작으므로 겹칩니다.
- merged[-1] 를 (10, max(12,15)) 즉 (10,15) 로 바꿉니다.

최종 결과는 [(1,8), (10,15)] 가 됩니다.

5. 시간 복잡도

정렬: O(n log n)
한 번의 순회: O(n)

따라서 전체 알고리즘의 시간 복잡도는 O(n log n) 입니다.
추가적인 메모리는 결과 리스트 merged 를 저장하기 위한 O(n) 정도만 필요합니다.

6. 마무리

이와 같이 파이썬의 기본 내장 함수와 리스트 조작만으로도 구간 병합 문제를 간결하고 효율적으로 해결할 수 있습니다.
코드가 짧고 가독성이 높아 실제 프로젝트에서도 바로 활용하기 좋습니다.

필요에 따라 인접 구간을 병합하지 않기(예: current[0] < prev[1] 로 조건을 바꾸는) 등 작은 변형을 적용할 수 있습니다.

여러분도 이 함수를 자신의 데이터에 맞게 변형해 보세요! 🚀

겹치는 구간에서 고유 번호 세기

Advent of Code 2025 챌린지와 이전 예약‑시스템 구현에서 영감을 받았습니다.

순진한 접근법

unique_values = set()
for start, end in ranges:
    unique_values.update(range(start, end + 1))

1‑100_000_000_000와 같은 범위는 메모리에 10억 개의 정수를 생성하게 됩니다 – 너무 비쌉니다. 모든 값을 실제로 만들지 않고도 숫자를 셀 방법이 필요합니다.

Source: …

해결책 – 먼저 병합하고 나중에 계산

모든 숫자를 저장하는 대신, 겹치거나 인접한 구간을 병합하여 더 작은 개별 구간 집합으로 만든 뒤, 수학적으로 전체 개수를 계산합니다.

예시 구간

3‑5,
10‑14,
16‑20,
12‑18

10‑14와 12‑18은 겹칩니다(12, 13, 14를 공유). 이를 병합하면 10‑18이 됩니다. 병합하지 않으면 겹치는 부분을 두 번 세게 되거나 메모리를 낭비하게 됩니다.

겹치는 구간 병합 방법

1️⃣ 구간 정렬하기

시작 위치로 정렬하면 수직선에서 구간을 왼쪽 → 오른쪽 순으로 처리할 수 있습니다.

sorted_ranges = sorted(fresh_ranges)
# Before: [(3,5), (10,14), (16,20), (12,18)]
# After : [(3,5), (10,14), (12,18), (16,20)]

리스트가 정렬되면 새로운 구간은 마지막으로 병합된 구간과만 겹칠 수 있으므로, 이전을 다시 살펴볼 필요가 없습니다.

정렬된 수직선 보기:
   3---5      10----14
              12------18
                  16----20
# 겹침은 왼쪽 → 오른쪽으로 흐릅니다!

2️⃣ 겹치거나 인접한 구간 병합하기

merged = []
for start, end in sorted_ranges:
    # 현재 구간이 마지막 병합 구간과 접촉하거나 겹치면 …
    if merged and start <= merged[-1][1] + 1:
        # … 마지막 병합 구간을 확장합니다
        merged[-1] = (merged[-1][0], max(merged[-1][1], end))
    else:
        # 겹치지 않으면 새로운 구간을 시작합니다
        merged.append((start, end))

왜 `start <= merged[-1][1] + 1` 인가?

상황	마지막 병합 구간	현재 구간	검사 (`start <= last_end + 1`)	결과
인접 (접촉)	(10, 14)	(15, 20)	15 ≤ 14 + 1 → True	병합
간격	(3, 5)	(10, 14)	10 ≤ 5 + 1 → False	분리

+ 1을 더함으로써 인접한 구간(예: (5, 9)와 (10, 15))도 겹치는 것으로 처리됩니다. 9와 10 사이에 정수가 없기 때문입니다.

시각적 예시

구간 A: (5, 9)   → 5,6,7,8,9
구간 B: (10,15)  → 10,11,12,13,14,15
# 9와 10이 맞닿아 있음
검사: 10 <= 9 + 1 → True → 병합 → (5,15)

구간 A: (5, 9)   → 5,6,7,8,9
구간 B: (11,15) → 11,12,13,14,15
# 10에 빈칸
검사: 11 <= 9 + 1 → False → 별도 유지

3️⃣ 숫자 개수 세기

병합이 끝난 뒤, 서로 겹치지 않는 구간들의 길이를 합하면 전체 서로 다른 정수의 개수가 됩니다.

total_count = sum(end - start + 1 for start, end in merged)
return total_count

최종 구현

def count_unique_numbers(fresh_ranges):
    # 1️⃣ Sort by start position
    sorted_ranges = sorted(fresh_ranges)

    # 2️⃣ Merge overlapping / adjacent ranges
    merged = []
    for start, end in sorted_ranges:
        if merged and start <= merged[-1][1] + 1:
            # Overlap or adjacency – extend the last interval
            merged[-1] = (merged[-1][0], max(merged[-1][1], end))
        else:
            # No overlap – start a new interval
            merged.append((start, end))

    # 3️⃣ Compute total count
    total_count = sum(end - start + 1 for start, end in merged)
    return total_count

실생활 사용 사례

예약 시스템

Meeting A: 09:00‑10:30
Meeting B: 10:15‑11:00
Meeting C: 14:00‑15:30
Meeting D: 15:30‑17:00

정렬됨: [(09:00,10:30), (10:15,11:00), (14:00,15:30), (15:30,17:00)]
병합됨: [(09:00,11:00), (14:00,17:00)]

병합된 구간은 겹치는 회의를 중복 계산하지 않고 전체 사용 시간을 나타냅니다.

기타 시나리오

IP 주소 할당 – CIDR 블록 병합.
유전체 구간 분석 – 겹치는 유전자 영역 결합.
로그 파일 처리 – 활동 시간 창을 통합.
자원 예약 – 장비나 회의실에 대한 예약 슬롯을 집계.

겹침 — 회의 C + D 터치 (인접)

가능 시간:

9:00 이전
11:00 – 14:00
17:00 이후

실제로 방이 비어 있는 시간은 언제인가요?

IP 주소 차단

차단: 192.168.1.0 - 192.168.1.50
차단: 192.168.1.45 - 192.168.1.100
차단: 192.168.1.200 - 192.168.1.255

병합 없이: 각 연결마다 3개의 규칙을 확인합니다.

병합 시:

[(192.168.1.0, 192.168.1.100), (192.168.1.200, 192.168.1.255)]

2개의 규칙만 확인하면 → 방화벽이 더 빠릅니다!

유지보수 다운타임

정비가 예정된 서버 또는 기계:

Maintenance A: Hour 0‑5
Maintenance B: Hour 4‑8
Maintenance C: Hour 20‑24

통합 중단 시간:

[(0, 8), (20, 24)]

총 중단 시간: 8 + 4 = 12 시간 (개별적으로 계산하면 17 시간이 아니라).

Why This Matters in All Cases

겹치는 기간을 이중 계산하는 것을 방지합니다.
검사를 최적화합니다 – 검색할 범위가 줄어듭니다.
빈틈을 찾습니다 – 사용 가능한 시간 슬롯을 확인합니다.
정확한 보고 – 실제 바쁜 시간과 자유 시간을 구분합니다.
성능 향상 – 많은 겹치는 범위 대신 병합된 범위가 적게 검사됩니다.

결론

위 패턴/방법은 전 세계 여러 기업에서 캘린더 초대 처리, 데이터베이스 인덱싱, 네트워크 트래픽 분석 등 다양한 용도로 사용됩니다.

앞으로—코드를 사용하여 애플리케이션 성능을 향상시키세요.

채팅이나 연락을 원하시면 아래에 댓글을 남기시거나 X/Twitter에서 팔로우해 주세요.

Python을 사용하여 범위 배열 병합

파이썬으로 범위 배열을 병합하기

1. 문제 정의

2. 해결 전략

3. 구현 코드

사용 예시

4. 동작 원리 상세 설명

5. 시간 복잡도

6. 마무리

겹치는 구간에서 고유 번호 세기

순진한 접근법

해결책 – 먼저 병합하고 나중에 계산

예시 구간

겹치는 구간 병합 방법

1️⃣ 구간 정렬하기

2️⃣ 겹치거나 인접한 구간 병합하기

왜 `start <= merged[-1][1] + 1` 인가?

시각적 예시

3️⃣ 숫자 개수 세기

최종 구현

실생활 사용 사례

예약 시스템

기타 시나리오

겹침 — 회의 C + D 터치 (인접)

실제로 방이 비어 있는 시간은 언제인가요?

IP 주소 차단

유지보수 다운타임

Why This Matters in All Cases

결론

관련 글

주간 챌린지: 새해, 새로운 도전

🎯 초보자용 가이드 'N-Repeated Element in Size 2N Array' – LeetCode 961 (C++ | Python | JavaScript)

Python 확장 플랫폼으로서의 WebAssembly

Pip 사용을 중단하세요: Python 프로젝트에 “uv”를 전환한 이유 (10배 빠르게)

파이썬으로 범위 배열을 병합하기

1. 문제 정의

2. 해결 전략

3. 구현 코드

사용 예시

4. 동작 원리 상세 설명

5. 시간 복잡도

6. 마무리

겹치는 구간에서 고유 번호 세기

순진한 접근법

해결책 – 먼저 병합하고 나중에 계산

예시 구간

겹치는 구간 병합 방법

1️⃣ 구간 정렬하기

2️⃣ 겹치거나 인접한 구간 병합하기

왜 start <= merged[-1][1] + 1 인가?

시각적 예시

3️⃣ 숫자 개수 세기

최종 구현

실생활 사용 사례

예약 시스템

기타 시나리오

겹침 — 회의 C + D 터치 (인접)

실제로 방이 비어 있는 시간은 언제인가요?

IP 주소 차단

유지보수 다운타임

Why This Matters in All Cases

결론

관련 글

주간 챌린지: 새해, 새로운 도전

🎯 초보자용 가이드 'N-Repeated Element in Size 2N Array' – LeetCode 961 (C++ | Python | JavaScript)

Python 확장 플랫폼으로서의 WebAssembly

Pip 사용을 중단하세요: Python 프로젝트에 “uv”를 전환한 이유 (10배 빠르게)

왜 `start <= merged[-1][1] + 1` 인가?

겹침 — 회의 C + D 터치 (인접)