자바 알고리즘 | IMOS 알고리즘을 활용한 구간 중첩 최대값 찾기

 

✅ IMOS 알고리즘

시작점과 끝점이 주어진 구간을 처리하는 데 유용한 알고리즘이다.

각 지점에서의 변경 값을 저장하고 누적하여 계산함으로 가장 중첩되는 영역을 구할 수 있다.

쇼핑몰의 판매 기록을 분석하여 특정 기간 동안 가장 많이 판매된 상품의 수량을 구한다.

판매 기록을 날짜별로 분류하여 날짜마다 판매된 상품 수량을 저장한다.
7월 1일부터 7월 3일까지의 구간에서 가장 많이 판매된 상품의 수량을 구하려고 한다.

7월 1일부터 7월 3일까지의 판매량의 누적 합을 구하고 가장 큰 값을 찾으면 된다.

이처럼 구간 중첩 문제를 해결하는 데에 유용한 알고리즘이다.

다양한 문제를 효율적으로 해결할 수 있다.

 

💡 IMOS 알고리즘 시간 복잡도

입력 데이터의 개수 N과 구간의 개수 M에 선형적으로 비례한다.

 

전체 시간 복잡도는 O(N + 2Mlog2M)이다.

• 이벤트를 정렬하는데 O(2Mlog2M)의 시간이 소요된다.
  • 구간이 M개일 때 구간의 시작점과 끝점을 기준으로 총 2M 개의 이벤트가 발생한다.
• 이벤트들을 처리하는 과정에서 각각의 데이터마다 한 번씩만 처리하므로 O(N)의 시간이 소요된다.

 

대부분 구간의 개수가 입력 데이터의 개수보다 작은 경우에 유용하게 사용된다. 

 

💡 IMOS 알고리즘 조건

• 입력된 구간 정보의 시작점과 끝점이 정해져 있어야 한다.
• 입력된 구간 정보의 시작점과 끝점이 양의 정수이어야 한다.
• 구간 정보를 담을 배열을 미리 할당해야 한다.

 

💡  IMOS 알고리즘 유형

• 구간 합 구하기 (Interval Sum)
• 구간 최댓값, 최솟값 구하기 (Interval Maximum/Minimum)
• 구간 내 포함된 값 구하기 (Interval Count)
• 구간 내 중복된 값 구하기 (Interval Overlap)
• 구간 내 구간이 포함된 값 구하기 (Interval Containment)
• 2차원 평면 상에서 직사각형이 겹치는 부분 구하기 (Rectangle Intersection)

 

💡 IMOS 알고리즘 과정

입력과 출력 단계에서 간단하게 반복문으로 구현한다.

중요한 것은 누적합 배열을 만드는 것으로 누적 합 배열을 만들어 각 구간의 합을 빠르게 계산한다.

 

데이터의 개수 N과 구간의 개수 M을 사용하여 IMOS 알고리즘을 구현한 예시이다.

• 데이터를 입력한다.
• 각 시작점과 끝점에 1과 -1을 더한다.
• 누적합을 이용해 중첩 구간 개수를 구한다.
• 구간 별 중첩 구간 개수를 출력한다.

public class Main {
    public static void main(String[] args) {
        int n = 6; // 데이터 개수
        int m = 3; // 구간 개수

        // 데이터를 입력한다
        int[] start = {1, 2, 2, 3, 4, 5};
        int[] end = {5, 4, 6, 6, 5, 6};

        // 각 시작 지점과 끝 지점에 1과 -1을 더한다
        int[] imos = new int[7]; // 1~6번 인덱스 사용
        for (int i = 0; i < n; i++) {
            imos[start[i]] += 1;
            imos[end[i] + 1] -= 1;
        }

        // 누적합을 이용해 중첩 구간 개수를 구한다
        for (int i = 1; i < imos.length; i++) {
            imos[i] += imos[i - 1];
        }

        // 구간 별 중첩 구간 개수를 출력한다
        int[][] interval = {{2, 4}, {1, 5}, {3, 6}};
        for (int i = 0; i < m; i++) {
            int s = interval[i][0];
            int e = interval[i][1];
            System.out.println("[" + s + "," + e + "]: " + imos[e] - imos[s - 1]);
        }
    }
}

 

 [2,4] 구간에는 중첩 구간이 1개, [1,5] 구간에는 중첩 구간이 3개, [3,6] 구간에는 중첩 구간이 2개 있다.

[2,4]: 1
[1,5]: 3
[3,6]: 2

 

💡  IMOS 알고리즘 활용

IMOS 알고리즘은 구간 중첩 문제를 해결할 때 다른 알고리즘보다 간단하고 빠른 속도로 결과를 구할 수 있어 많은 분야에서 사용된다.

 

• 통계 분석: 어떤 통계 데이터에서 특정 기간 동안 최댓값, 최솟값, 합계 등을 구할 때 사용할 수 있다.
• 시계열 데이터 분석: 시간에 따라 변하는 양을 분석할 때 사용할 수 있다.
• 이벤트 처리: 특정 기간 동안 발생한 이벤트의 횟수를 계산할 때 사용할 수 있다.
• 쇼핑몰 판매 분석: 특정 기간 동안 판매된 상품의 수량, 가격 등을 분석할 때 사용할 수 있다.
• 게임 개발: 충돌 처리 등에서 사용할 수 있다.