알고리즘에서 이벤트 기반 접근

오늘은 특정 문제의 풀이를 가져오진 않았다. 주말에 Moloco 코딩테스트를 보다가 뼈아프게 실수한 게 있어서 복기의 목적으로 문제를 정리해본다.

 

몰로코 코딩 테스트는 4문제 70분으로 주어진다. 난이도는 전반적으로 쉬운 편이다. 백준 기준으로 실버 1~5 수준의 문제가 나오는데 복잡한 알고리즘과 자료구조를 묻기보다 빠른 문제 해결 능력을 물어보는 유형이 나온다.

결국 한 문제를 시간 내에 풀지 못하고 제출했다. 시험이 끝나고 곰곰이 생각해보니 분명히 풀었던 유형이었다. 코드트리의 "코드트리 오마카세"가 정확히 이런 유형이었다.

구간의 변화를 이벤트로 관리

코드시그널 문제를 구체적으로 밝힐 수는 없지만 코드트리 오마카세와 못 풀었던 문제의 유형을 일반화한다면 "구간의 변화를 이벤트로 관리"한다는 점이다. 이때, 변화를 관리하기 위해서 전체 순회를 사용하면 O(n ^ 2) 이상이 걸리는 알고리즘을 이벤트 기반의 구현으로 시간복잡도를 낮출 수 있다. 위에 제시한 두 개의 문제처럼 구간의 압축이나 구간 합 계산이 필요한 경우에서 특히 유용하게 사용되는 방법이다.

 

• 회의실 예약 문제: 여러 회의의 시작과 끝 시간이 주어졌을 때, 한 번에 필요한 회의실 수를 구하는 문제
• 최대 동시 방문자 수: 특정 시간대별로 입장과 퇴장이 기록된 상황에서 가장 많이 겹치는 시간대의 방문자 수를 구하는 문제

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class TreeShadowCoverage {

    static class Event implements Comparable<Event> {
        int position;
        int type; // 1은 그림자 시작, -1은 그림자 끝

        public Event(int position, int type) {
            this.position = position;
            this.type = type;
        }

        @Override
        public int compareTo(Event other) {
            // 위치가 같다면 끝 이벤트가 먼저 오도록 정렬
            if (this.position == other.position) {
                return Integer.compare(this.type, other.type);
            }
            return Integer.compare(this.position, other.position);
        }
    }

    public static int countShadowedCells(int[][] trees) {
        List<Event> events = new ArrayList<>();

        for (int[] tree : trees) {
            int position = tree[0];
            int height = tree[1];

            int start = position - height;
            int end = position + height;

            events.add(new Event(start, 1)); // 그림자 시작 이벤트
            events.add(new Event(end + 1, -1)); // 그림자 끝 이벤트 (end + 1)
        }

        // 이벤트 정렬
        Collections.sort(events);

        int shadowedCount = 0;
        int activeShadows = 0;
        int lastPosition = Integer.MIN_VALUE;

        for (Event event : events) {
            if (activeShadows > 0) {
                shadowedCount += event.position - lastPosition;
            }

            // 현재 이벤트 처리
            activeShadows += event.type;
            lastPosition = event.position;
        }

        return shadowedCount;
    }

    public static void main(String[] args) {
        int[][] trees = {
            {3, 2},
            {8, 4},
            {15, 3}
        };

        int result = countShadowedCells(trees);
        System.out.println("그림자로 덮인 칸의 개수: " + result);
    }
}

 

직접 복기하면서 작성했던 예시 코드를 한번 보자. ※ 주의!!! 이 예시는 코드시그널 문제와 연관이 없다.

각 나무의 위치와 높이를 나타내는 2차원 배열 int[][] trees가 주어집니다. trees[n][0]은 n번째 나무의 위치를, trees[n][1]은 n번째 나무의 높이를 나타냅니다.

나무가 그림자를 드리우는 범위는 해당 나무 위치에서 나무의 높이만큼 왼쪽과 오른쪽으로 퍼집니다.

예를 들어, 나무의 위치가 5이고 높이가 3이라면, 그림자는 위치 2부터 8까지 드리워집니다. 수직선 상에서 그림자로 덮인 위치를 1로 표시하고, 그 외는 0으로 표시한다고 가정합니다. 전체 그림자가 드리워진 칸(= 1로 표시된 칸)의 개수를 계산하는 코드를 작성하세요.

나무가 그림자를 만들 텐데 그림자가 시작하는 이벤트와 끝나는 이벤트를 나누어 문제를 푼다. 정렬하는 데에만 시간복잡도가 계산되므로 위 문제의 시간복잡도는 O(n log n)이다. 만약 전체 순회 두 번으로 시간복잡도가 O(n ^ 2)이 된다면 시간초과가 난다.

코드트리의 "코드트리 오마카세" 문제도 시간의 흐름에 따라 사람의 출입과 초밥의 출입을 관리하는 이벤트를 만들어 문제를 푼다.

 

두 문제 모두, 구간의 변화를 관리하는 데 특히 효과적이다. 이 방법은 배열을 생성할 수 없거나, 전체 범위를 1로 직접 설정하면 시간이 많이 걸리는 경우와 같은 문제에서 매우 유용하게 사용된다.

이벤트 기반 접근을 사용하는 일반적인 문제 유형

일반적으로 이런 이벤트 기반 접근을 사용하는 문제의 유형은 아래와 같다.

1. 구간 내의 특정 값 카운팅
   위 그림자 문제처럼 특정 위치에서 여러 구간이 겹치는 상황이 주어지고, 어느 구간이 현재 겹치는지, 또는 특정 위치에서 구간이 얼마나 겹치는지 알아야 할 때 사용된다.
2. 시간/위치에 따른 상태 변화 문제
   "코드트리 오마카세" 문제처럼 시간에 따른 이벤트가 발생하는 문제에서 특정 시간에 몇 개의 이벤트가 활성화되어 있는지를 구하는 문제에 유용하다.
3. 누적 구간 합 계산 문제
   이 문제는 특정 구간마다 값이 증가하거나 감소하는 패턴이 있을 때 유용하다. 예시로 특정 구간마다 사람 수가 증가하거나 줄어드는 문제(강의실 예약 시간에 따른 학생 수)에서 구간마다 변화를 기록하고 이를 통해 전체 값을 구할 수 있다.

 

 

... 대체 왜 다 끝나고 생각난 거지... 하...