구간을 잡을 때 $[l, r)$을 쓰기도 하는 이유

구간을 잡는 두 가지 방법

PS에서 구간을 잡아야 할 때 주로 $[l, r]$와 $[l, r)$ 두 가지 방법을 사용합니다.

• $[l, r]$는 $l$부터 $r$까지 포함하는 구간입니다.
• $[l, r)$는 $l$부터 $r$ 이전까지 포함하는 구간입니다. $r$를 포함하지 않습니다.

 

수열 $A = [A_1, A_2, \cdots, A_N]$의 구간을 두 가지 방법으로 잡아봅시다.

• 구간 $[l, r]$에 속한 원소는 $[A_l, A_{l+1}, \cdots, A_r]$입니다.
• 구간 $[l, r)$에 속한 원소는 $[A_l, A_{l+1}, \cdots, A_{r-1}]$입니다.

 

$[l, r]$는 설명이 필요 없을 정도로 직관적입니다.

대부분의 문제 지문이나 풀이 해설에서 기본적으로 $[l, r]$을 사용합니다.

 

$[l, r)$는 마지막을 포함하지 않는다는 점에서 그리 직관적이지는 않습니다.

그렇지만 파이썬의 range(l, r)처럼 기본적으로 $[l, r)$가 쓰이는 분야가 있습니다.

 

 

인덱스를 바라보는 관점을 바꿔보자

보통 인덱스는 위 그림과 같이 원소와 일대일로 대응되는 개념처럼 쓰입니다.

 

그러다보니 $l$부터 $r$까지라고 하면 자연스럽게 $[l, r]$을 떠올리게 됩니다.

당연합니다. $[l, r]$의 마지막은 $r$이지만 $[l, r)$의 마지막은 $r - 1$이거든요. 어색할 수밖에 없습니다.

 

이번에는 인덱스를 0.5칸 왼쪽으로 움직여봅시다.

이렇게 보면 인덱스는 배열의 맨 끝 혹은 두 인접한 원소 사이를 나타내는 위치의 개념처럼 느껴지게 됩니다.

 

따라서 $l$부터 $r$까지라고 하면 자연스럽게 $[l, r) = [l, l + 1), [l + 1, l + 2), \cdots, [r - 1, r)$를 떠올릴 수 있습니다.

이렇게 보면 $[l, r)$도 꽤 자연스러워보이지 않나요?

 

 

$[l, r)$의 장단점

$[l, r)$로 구간을 다루면 시작과 끝이 맞물리기 때문에 구간을 덩어리로 다루기 좋습니다.

• $[l, r]$ 구간의 길이는 $r - l + 1$이지만 $[l, r)$ 구간의 길이는 $r - l$입니다.
• $[l, r]$ 구간은 $[l, m - 1], [m, r]$ 또는 $[l, m], [m - 1, r]$로 나눌 수 있지만 $[l, r)$ 구간은 $[l, m), [m, r)$로 나눌 수 있습니다.

 

$[l, r)$는 구간 자체의 각 원소를 다룰 때에는 꽤 골치아픈 면도 있습니다.

• $[l, r]$ 표현에서의 $[i, i]$는 대칭적이지만 $[l, r)$ 표현에서의 $[i, i + 1)$는 비대칭적입니다.
• 뒤에서부터 원소를 확인해야 할 때 $r - 1, r - 2, \cdots, l + 1, l$ 순으로 읽어야 합니다.