구간 처리 기법(Interval Processing) 완벽 정리 - 개념, 원리, 및 예제 코드

구간 처리 기법 총 정리

 

1. 구간 처리 기법이란?

구간 처리(Interval Processing)는 데이터에서 특정 구간(interval)과 관련된 문제를 효율적으로 해결하는 알고리즘 기법입니다. 이 기법은 주로 숫자, 시간, 또는 범위와 같은 연속적인 데이터 구조를 다룰 때 활용됩니다. 구간의 시작점과 끝점을 기준으로 정렬 및 탐색을 통해 문제를 해결하는 데 초점이 맞춰져 있습니다.

 

구간 처리 기법은 대표적인 애드혹(ad-hoc) 알고리즘 기법 중 하나입니다. 애드혹 알고리즘에 대해서는 아래 링크에 자세히 정리했습니다.

2024.12.26 - [알고리즘] - 애드혹(Ad-hoc) 알고리즘 완벽정리 - 개념, 주의점, 대표기법 총 정리

애드혹(Ad-hoc) 알고리즘 완벽정리 - 개념, 주의점, 대표기법 총 정리

 

---

 

 

2. 구간 처리 기법의 원리

 

구간 처리 기법은 다음의 단계를 따릅니다:

1. 정렬: 구간의 시작 또는 끝점을 기준으로 데이터를 정렬합니다.
2. 탐색 및 처리: 정렬된 구간을 순회하면서 특정 조건을 만족하는 구간을 찾거나 구간의 합집합, 교집합 등을 계산합니다.

구간 처리의 주요 원리는 정렬된 상태에서 최소한의 탐색으로 구간 관련 연산을 수행하는 데 있습니다. 예를 들어, 두 구간의 교집합을 구하려면 시작점과 끝점을 기준으로 정렬한 후 순차적으로 탐색하며 계산할 수 있습니다.

 

반응형

---

 

3. 시간 복잡도

1. 정렬 단계: 일반적으로 O(n log n) (효율적인 정렬 알고리즘 사용 시)
2. 탐색 단계: O(n) (정렬된 데이터를 순회하며 계산)

따라서, 구간 처리 기법의 전체 시간 복잡도는 O(n log n)로 매우 효율적입니다.

---

 

 

4. 구간 처리의 대표적인 적용 사례

(1) 회의실 배정 문제

• 문제: 시작 시간과 종료 시간이 주어진 여러 회의 중 최대한 많은 회의를 배정하세요.
• 풀이: 종료 시간을 기준으로 정렬 후 탐색.

 

(2) 최대 겹치는 구간 찾기

• 문제: 여러 구간 중 가장 많이 겹치는 시간대를 구하세요.
• 풀이: 시작점과 끝점을 각각 정렬하고, 두 포인터를 사용하여 겹치는 구간을 계산.

 

(3) 합집합 구간 계산

• 문제: 겹치는 구간을 합쳐서 새로운 구간을 계산하세요.
• 풀이: 시작점 기준 정렬 후 순차적으로 탐색하며 합침.

 

(4) 특정 값이 포함된 구간 찾기

• 문제: 특정 값이 포함된 구간을 찾아 출력하세요.
• 풀이: 이진 탐색과 정렬된 구간을 활용.

---

 

 

5. 장단점

장점

1. 효율성: 정렬 후 탐색만으로 결과를 도출하므로 시간 복잡도가 낮습니다.
2. 직관성: 정렬된 데이터를 순차적으로 탐색하므로 논리적으로 이해하기 쉽습니다.
3. 적용 범위가 넓음: 시간대, 숫자 범위 등 다양한 연속적 데이터에 활용 가능.

단점

1. 정렬 비용: 데이터가 크거나 정렬이 복잡한 경우 초기 비용이 부담이 될 수 있습니다.
2. 데이터의 정렬 조건: 문제마다 정렬 기준이 다르므로 설계 단계에서 세심한 고려가 필요합니다.

---

 

 

6. 설계 시 주의점

1. 정렬 기준의 명확화: 시작점 기준, 끝점 기준 등 문제에 따라 다르게 정렬해야 합니다.
2. 정렬 안정성: 데이터의 순서를 보존해야 할 경우 안정 정렬을 선택하세요.
3. 경계값 처리: 시작점과 끝점이 같은 경우 경계를 정확히 처리해야 합니다.

---

 

 

7. 예제 코드

C 언어

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    int start;
    int end;
} Interval;

int compare(const void* a, const void* b) {
    return ((Interval*)a)->start - ((Interval*)b)->start;
}

void mergeIntervals(Interval intervals[], int n) {
    qsort(intervals, n, sizeof(Interval), compare);

    int index = 0;
    for (int i = 1; i < n; i++) {
        if (intervals[index].end >= intervals[i].start) {
            if (intervals[index].end < intervals[i].end) {
                intervals[index].end = intervals[i].end;
            }
        } else {
            index++;
            intervals[index] = intervals[i];
        }
    }

    for (int i = 0; i <= index; i++) {
        printf("[%d, %d] ", intervals[i].start, intervals[i].end);
    }
}

int main() {
    Interval intervals[] = {{1, 3}, {2, 4}, {5, 7}, {6, 8}};
    int n = sizeof(intervals) / sizeof(intervals[0]);

    mergeIntervals(intervals, n);
    return 0;
}

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Interval implements Comparable<Interval> {
    int start, end;

    Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }

    @Override
    public int compareTo(Interval other) {
        return this.start - other.start;
    }
}

public class IntervalProcessing {
    public static List<Interval> mergeIntervals(List<Interval> intervals) {
        intervals.sort(null);

        List<Interval> result = new ArrayList<>();
        Interval current = intervals.get(0);

        for (int i = 1; i < intervals.size(); i++) {
            Interval next = intervals.get(i);
            if (current.end >= next.start) {
                current.end = Math.max(current.end, next.end);
            } else {
                result.add(current);
                current = next;
            }
        }
        result.add(current);
        return result;
    }

    public static void main(String[] args) {
        List<Interval> intervals = Arrays.asList(
            new Interval(1, 3),
            new Interval(2, 4),
            new Interval(5, 7),
            new Interval(6, 8)
        );

        List<Interval> merged = mergeIntervals(intervals);
        for (Interval interval : merged) {
            System.out.println("[" + interval.start + ", " + interval.end + "]");
        }
    }
}

Python

def merge_intervals(intervals):
    intervals.sort(key=lambda x: x[0])

    merged = [intervals[0]]
    for current in intervals[1:]:
        last = merged[-1]
        if current[0] <= last[1]:
            last[1] = max(last[1], current[1])
        else:
            merged.append(current)

    return merged

intervals = [[1, 3], [2, 4], [5, 7], [6, 8]]
merged = merge_intervals(intervals)
print(merged)

---

 

구간 처리 기법은 시간대, 구간 합, 교집합 등 범위와 관련된 다양한 문제를 효율적으로 해결할 수 있는 핵심적인 알고리즘 설계 방법입니다. 정렬과 탐색을 조합하여 높은 효율성을 제공하며, 다양한 문제 유형에 쉽게 적용할 수 있습니다.