그리디

언제 쓰나

매 순간 하나를 골라 나가는데, 지금 가장 좋아 보이는 것을 고르고 다시 바꾸지 않아도 전체 답이 가장 좋아지는 문제에 씁니다.

• 회의·수업·예약처럼 시간이 겹치면 안 되는 구간을 “최대한 많이 남기라”거나 “최소한으로 빼라”고 묻습니다.
• 한 가지 기준(끝나는 시각, 무게, 가격)으로 정렬하고 앞에서부터 한 번 훑으면 답이 나올 것 같은 모양입니다.
• 입력이 커서 경우를 모두 따져 볼 수 없습니다. LeetCode 435는 구간이 최대 10만 개입니다.

어떻게 동작하나

손으로 골라 보면

LeetCode 435는 구간 목록에서 나머지가 서로 겹치지 않도록 빼야 하는 구간의 최소 개수를 묻는 문제입니다. 예제 1의 [[1, 2], [2, 3], [3, 4], [1, 3]]에서 [1, 3] 하나만 빼면 [1, 2], [2, 3], [3, 4]가 남는데, 셋은 끝과 시작이 맞닿기만 할 뿐 겹치지 않습니다. 문제도 [1, 2]와 [2, 3]처럼 한 점에서 맞닿은 구간은 겹치지 않는다고 정해 둡니다. 그래서 답은 1입니다.

빼는 개수를 최소로 하는 것은 겹치지 않게 남기는 개수를 최대로 하는 것과 같습니다. 예제 1은 구간 네 개 중 최대 세 개를 남길 수 있으니 빼는 것은 하나입니다. 그래서 질문은 “어떤 구간부터 남겨야 가장 많이 남길 수 있는가”로 바뀝니다.

어떤 구간부터 남길까

구간을 한 가지 순서로 정렬해 앞에서부터 보면서, 이미 남긴 구간과 겹치지 않으면 남기고 겹치면 빼 보겠습니다. [[1, 9], [2, 3], [4, 5], [6, 8]]을 먼저 시작이 빠른 순서로 보면 이렇게 됩니다.

시작이 빠른 순 · 뺀 구간 3개

맨 먼저 시작하는 [1, 9]를 남기고 나면, 이 구간이 9까지 이어져서 뒤의 세 구간이 모두 겹칩니다. 세 개를 빼야 합니다. 이번에는 끝나는 시각이 빠른 순서로 봅니다.

끝이 빠른 순 · 뺀 구간 1개

3에 끝나는 [2, 3]을 먼저 남기면 3 이후의 시간이 모두 비어 있어서 [4, 5]와 [6, 8]도 남길 수 있고, [1, 9] 하나만 빼면 됩니다.

끝나는 시각 순서가 늘 맞는 이유는 이렇습니다. 가장 많이 남긴 답 하나를 가져와, 그 답의 첫 구간을 가장 먼저 끝나는 구간으로 바꿔 끼운다고 해 보겠습니다. 바꿔 넣은 구간은 원래 첫 구간보다 늦게 끝나지 않으므로, 원래 답에서 그 뒤에 있던 구간들과도 겹치지 않습니다. 남긴 개수는 그대로이니 가장 먼저 끝나는 구간을 먼저 남겨도 최대 개수를 놓치지 않고, 그다음 구간을 고를 때도 같은 이유가 되풀이됩니다.

이처럼 정해 둔 기준에서 지금 가장 좋아 보이는 것 하나를 고르고, 고른 것을 되돌리지 않는 방법을 그리디(greedy)라고 합니다. 눈앞의 최선을 바로 집는다는 뜻에서 탐욕법이라고도 부릅니다. 앞의 시작 순서도 모양은 똑같이 그리디인데 답이 틀렸습니다. 그래서 그리디로 풀 때는 기준을 정한 뒤, 그 기준이 왜 전체에서도 최선인지를 위처럼 따져 봐야 합니다.

직접 따라가 보기

아래 시각화는 예제 1의 네 구간에 [5, 8], [2, 6], [4, 7]을 더한 일곱 구간으로 진행합니다. 읽는 법은 이렇습니다.

• 한 행이 구간 하나이고, 막대는 시간축에서 시작부터 끝까지 걸칩니다.
• 파란 세로 점선 end는 마지막으로 남긴 구간이 끝나는 시각입니다. 다음 구간이 이 선보다 먼저 시작하면 겹칩니다.
• 겹친 구간에는 시작부터 end까지 빨간 칸이 덮입니다.

변수 칸의 end와 removed는 아래 풀이 코드의 변수입니다. end는 남긴 구간이 아직 없을 때 어떤 시작 시각보다도 작은 -Infinity에서 시작하고, removed는 지금까지 뺀 구간 수입니다.

2번째 단계에서 막대들이 끝나는 시각 순으로 자리를 옮깁니다. 4번째 단계의 [2, 3]은 end 2에서 바로 시작해 맞닿기만 하므로 남깁니다. 5번째 단계의 [1, 3]은 end 3보다 먼저 시작해 1부터 3까지가 빨갛게 덮이고 빠집니다. 마지막 10번째 단계에서 네 구간이 남고 답 3이 나옵니다.

처음부터 이전 자동 재생 다음

단계 1 / 10

구간 막대 · 끝나는 시각 순으로 남기기

변수

[start, finish]

–

end

-Infinity남긴 구간의 끝

removed

0뺀 구간 수

return

–

입력 순서대로 놓인 구간 일곱 개입니다. "다음"을 누르면 끝나는 시각이 빠른 순서로 정렬합니다

• 지금 보는 구간
• 남긴 구간
• 겹쳐서 뺀 구간
• 마지막으로 남긴 구간의 끝 (end)

대표 문제 풀이

참고 풀이입니다. 변수 이름은 위 시각화의 변수 칸과 같습니다.

var eraseOverlapIntervals = function (intervals) {
  // ① 끝나는 시각이 빠른 순서로 정렬한다
  intervals.sort((a, b) => a[1] - b[1]);

  let end = -Infinity; // 마지막으로 남긴 구간이 끝나는 시각
  let removed = 0;
  for (const [start, finish] of intervals) {
    if (start >= end) {
      // ② 겹치지 않으면 남기고 end를 옮긴다
      end = finish;
    } else {
      // ③ 겹치면 뺀다
      removed++;
    }
  }
  return removed;
};

①에서 정렬한 순서대로 한 번 훑습니다. ②는 시각화에서 막대가 청록이 되고 end 선이 옮겨 가는 단계이고, ③은 빨간 칸이 덮이고 막대가 회색이 되는 단계입니다. ②의 조건이 start > end가 아니라 start >= end인 것은 맞닿은 구간을 겹치지 않는 것으로 보기 때문입니다.

정렬에 O(n log n), 한 번 훑는 데 O(n)이 들어 전체 시간은 더 큰 쪽인 O(n log n)입니다. 정렬이 쓰는 공간을 빼면 변수 두 개만 쓰므로 추가 공간은 O(1)입니다.

자주 하는 실수

시작 시각 순서로 정렬합니다. 구간 문제는 시작 순으로 정렬해 푸는 경우가 많아서 이 문제에서도 그렇게 정렬하기 쉽습니다. 저도 구간 병합(LeetCode 56)은 시작 순으로 정렬해 풀었고, 겹치는 구간을 합치는 그 문제에서는 그게 맞았습니다. 하지만 이 문제에서 시작 순으로 앞에서부터 남기면, 위 그림처럼 [[1, 9], [2, 3], [4, 5], [6, 8]]에서 1이 아니라 3이 나옵니다.

맞닿은 구간을 겹친다고 봅니다. 구간 병합에서는 [1, 4]와 [4, 5]처럼 맞닿은 구간도 하나로 합쳐야 해서, 제 풀이는 cur[1] >= start를 겹침으로 봤습니다. 이 문제에서 같은 기준으로 start > end일 때만 남기면 예제 1의 [1, 2]와 [2, 3]이 겹친다고 판단해, 답 1 대신 2가 나옵니다.

end를 0으로 시작합니다. 이 문제의 시작 시각은 -50,000까지 내려갑니다. end = 0으로 시작하면 [[-2, -1]]처럼 음수에서 시작하는 첫 구간을 겹친다고 보고 빼서, 0 대신 1을 돌려줍니다. 남긴 구간이 아직 없다는 뜻으로 -Infinity에서 시작합니다.

정렬 비용을 빼고 복잡도를 셉니다. 저는 구간 병합의 복잡도를 답하면서 “O(n)+O(nlogn) -> O(n)이 될거야”라고 했다가, 구현을 마친 뒤 두 비용을 더하면 더 큰 O(n log n)이 남는다고 바로잡았습니다. 이 문제도 정렬한 뒤 한 번 훑는 같은 모양이라 전체는 O(n log n)입니다.