[CS] 배열의 인덱스가 0부터 시작하는 이유

1. 들어가며

1학년 때 C언어를 처음 배울 때, 배열의 인덱스가 0에서 시작한다고 해서 1부터 수를 세는 것에 익숙해 꽤 헷갈려했었는데, 지금은 오히려 인덱스가 0에서부터 시작하는게 너무나 당연해졌다. 그런데 왜 0에서부터 시작하는걸까? 하는 의문이 들었다. 왜 하필이면 0일까?

 

2. 다익스트라의 설명

컴퓨터공학과 학생이라면 정말 익숙할 그 이름인 다익스트라 가 이에 대해 이유를 설명한 글이 있다. 이 글을 한 번 정리해보자.

https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html

E.W. Dijkstra Archive: Why numbering should start at zero (EWD 831)

 

우리가 어떤 수의 범위를 표현할 때, 다음과 같은 4가지 표현 방식이 가능하다.

1. [a, b] , a <= x <= b

2. [a, b) , a <= x < b

3. (a, b], a < x <= b

4. (a, b) , a < x < b

 

x에 포함되는 수의 개수를 한 번 구해보자.

 

1번의 경우, x에 해당되는 수의 개수는 |b - a + 1|

2번과 3번의 경우, x에 해당되는 수의 개수는 |b - a|

4번의 경우, x에 해당되는 수의 개수는 |b - a - 1|

 

4가지의 컨벤션 중에서, 보여지는 숫자만을 통해 x에 포함되는 수의 개수를 바로 구할 수 있는 것은 2번과 3번 표기법이다.

 

 

이제 한 가지를 더 고려해보자. 가장 작은 자연수(natural number, 여기에서는 0을 포함한다)인 0을 표현하고자 할 때, 4가지 컨벤션은 다음과 같이 표기를 해야한다.

 

1번과 2번은 0 <= x ...

3번과 4번은 -1 < x ...

 

3번과 4번은 0이라는 수를 표기하기 위하여 추가적인 메모리를 사용해야 한다. C언어를 예로 들자면, 1번과 2번의 경우 signed type만으로 0을 나타낼 수 있지만, 3번과 4번의 표기법을 사용하려면 unsigned type을 사용해야 한다. unsigned type은 맨 앞의 bit 1개를 음수/양수 판별에 사용해야 하므로, 1번과 2번 표기법에 비해 bit를 하나 더 할애해야 한다.

 

따라서 우리는 4가지 컨벤션 중, 2번 컨벤션 [a, b) 을 선호한다.

 

그럼 이제 고려해야 할 사항은 N이라는 길이를 가진 sequence를 표현하고자 할 때, 어떤 숫자로 시작하는 것이 좋은지 살펴보아야 한다. 만약 우리가 일반적으로 생각하듯이 1로 시작을 하게 된다면, 1 <= x < N + 1 로 표기를 해야 한다. 그러나 0부터 시작을 하게 된다면, 0 <= x < N 으로 표기를 하게 되는데, 이 경우 N이라는 길이와 일치하기 때문에 더욱 깔끔하게 표현이 가능하다.

 

위와 같은 이유로, 다익스트라는 0부터 시작하는게 낫다고 했다.

 

3. 컴퓨터 공학적 측면의 이유

컴퓨터 공학적 측면에서도 0에서 시작하는게 낫다고 한다. Wikipedia를 한 번 살펴보자.

https://en.wikipedia.org/wiki/Zero-based_numbering

Zero-based numbering - Wikipedia

 

C언어를 처음 배울 때, 어떤 배열의 원소값에 접근하기 위해서 배열의 주소값을 사용했을 것이다. 예를 들어 p라는 배열이 있다고 해보자. p 배열의 각 원소에 접근을 할 때 다음과 같이 접근을 했을 것이다.

 

1번째 원소: *(p + 0)

2번째 원소: *(p + 1)

3번째 원소: *(p + 2)

4번째 원소: *(p + 3)

...

 

배열의 인덱스가 0부터 시작을 할 경우, 우리는 배열의 각 원소에 접근을 할 때 주어진 주소값에서 offset을 더하는 방식으로 각 원소에 쉽게 접근을 할 수 있게 된다. (배열의 3번 인덱스의 경우, 주소값에서 offset이 3인 원소에 접근하면 된다.)

만약 배열이 0이 아니라 1부터 시작을 한다면, 위 같은 주소값 체계에서 *(p + 0)을 낭비하게 되며, 배열의 주소값에서 얼마만큼의 offset이 떨어져있는지로 원소에 접근하는 것도 힘들어질 것이다. 따라서 배열의 인덱스는 0부터 시작한다고 한다.

 

참고

0부터 시작하는 이유와 마지막 수를 인덱스로 포함하지 않는 이유

0부터 시작하는 이유와 마지막 수를 인덱스로 포함하지 않는 이유