왜 컴퓨터는 0부터 수를 셀까? 배열 인덱스와 0-based 인덱싱의 비밀

프로그래밍을 하다 보면 대부분의 언어들이 배열 인덱스를 0부터 시작하는데요. 이른바 0-based 인덱싱이라 불리는 이 방식은 인간의 입장에서는 부자연스러워 보이지만, 메모리 주소 연산과 배열 차원 변환 등에서 명확한 이점이 있습니다.

이번 글에서는 컴퓨터가 숫자를 0부터 계산했을 때 생기는 이점에 대해서 알아보겠습니다.

‍

배열 차원 변환과 0-based 인덱싱

인덱스를 0으로 시작하는 경우와 1로 시작하는 경우를 각각 C#과 Pascal로 구현하여 차이점을 살펴보겠습니다. 대부분의 언어가 0으로부터 인덱스를 시작하는 것과 달리 Pascal은 1부터 시작하는 언어입니다.

1차원 → 2차원: 0-based 인덱싱

0부터 시작하는 인덱스를 사용할 때, 1차원 배열의 인덱스를 2차원 배열의 인덱스로 변환하는 것은 다음과 같이 수행됩니다.

int[] oneDimensional = new int[100];
int[,] twoDimensional = new int[10, 10];

for (int i = 0; i < 100; i++) {
    twoDimensional[i / 10, i % 10] = oneDimensional[i];
}
```

2차원 배열의 인덱스를 [x, y]라고 했을 때, y는 1차원 배열의 인덱스가 10이 증가할 때마다 1이 증가됩니다. x의 경우에는 0부터 9까지 반복하게 됩니다.
```
1차원-i: [ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [10]
2차원-x: [ 0] [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [ 0] ==> i % 10
2차원-y: [ 0] [ 0] [ 0] [ 0] [ 0] [ 0] [ 0] [ 0] [ 0] [ 0] [ 1] ==> i / 10

‍

1차원 → 2차원: 1-based 인덱싱

1부터 시작하는 인덱스를 사용할 때, 1차원 배열의 인덱스를 2차원 배열의 인덱스로 변환하는 것은 약간 더 복잡합니다. 추가적인 연산이 필요하게 되는데요. 아래 Pascal 예제와 함께 살펴보겠습니다.

var
  i: Integer;
  oneDimensional: array[1..100] of Integer;
  twoDimensional: array[1..10, 1..10] of Integer;
begin
  for i := 1 to 100 do
    twoDimensional[(i-1) div 10 + 1, (i-1) mod 10 + 1] := oneDimensional[i];
end.
```

Pascal에서 정수 나누기는 div 연산자를 사용하고, 모듈로는 mod 연산자를 사용합니다. 아래의 도표에서는 편의상 C#과 동일하게 표현하였습니다.
```
1차원-i: [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [10] [11]
2차원-x: [ 1] [ 2] [ 3] [ 4] [ 5] [ 6] [ 7] [ 8] [ 9] [10] [ 1] ==> (i-1)%10 + 1
2차원-y: [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 1] [ 2] ==> (i-1)/10 + 1

‍

2차원 → 1차원: 0-based 인덱싱

0부터 시작하는 인덱스를 사용할 때, 2차원 배열의 인덱스를 1차원 배열의 인덱스로 변환하는 것은 다음과 같이 수행됩니다.

int[,] twoDimensional = new int[10, 10];
int[] oneDimensional = new int[100];

for (int i = 0; i < 10; i++) {
    for (int j = 0; j < 10; j++) {
        oneDimensional[i * 10 + j] = twoDimensional[i, j];
    }
}

‍

2차원 → 1차원: 1-based 인덱싱

1부터 시작하는 인덱스를 사용할 때, 2차원 배열의 인덱스를 1차원 배열의 인덱스로 변환하는 것은 다음과 같이 수행됩니다.

var
  i, j: Integer;
  twoDimensional: array[1..10, 1..10] of Integer;
  oneDimensional: array[1..100] of Integer;
begin
  for i := 1 to 10 do
    for j := 1 to 10 do
      oneDimensional[(i-1) * 10 + j] := twoDimensional[i, j];
end.

이렇게 예제를 통해 볼 수 있듯이, 1차원 배열과 2차원 배열의 전환은 0-based 인덱싱이 더 간단하고 직관적입니다.

일반적인 상황에서 프로그래머들은 배열의 차원 전환을 신경 써야 하는 경우가 많지 않습니다. 하지만, 프로그램이 운영되는 내부 상황에서는 이러한 연산들이 빈번하게 일어나고 있습니다. 따라서, 0부터 인덱스 시작하는 것이 컴퓨터 입장에서는 더욱 자연스러운 것이 됩니다.

‍

메모리 주소 연산에서 Offset이 0부터 시작하는 이유

배열이나 포인터의 기준점으로부터 각 요소가 얼마나 떨어져 있는 지를 파악하는 것은 자주 발생하는 연산입니다. 특히 포인터에서는 특정 위치의 데이터에 직접 접근하고 싶을 때가 많습니다. 이러한 경우 offset을 사용하게 되는데요. offset은 기본 주소로부터 얼마나 떨어져 있는 지를 나타내는 값입니다.

여기에서, offset이 0 또는 1로 시작하는 경우를 비교하여 설명하겠습니다.

‍

offset이 1인 경우

만약 offset이 1로 시작한다면, 첫 번째 바이트(또는 요소)에 접근하기 위해 -1을 해야 합니다. 이는 offset 값이 실제로 첫 번째 바이트보다 하나 더 앞서기 때문입니다.

char *data = (char *)malloc(1024);
// 첫 번째 데이터라는 의미로 1을 사용
int offset = 1;
// 첫 번째 바이트에 접근하기 위해 offset에서 1을 빼줍니다.
char *theFirstByte = data + offset - 1;

‍

offset이 0인 경우

만약 offset이 0으로 시작한다면, 첫 번째 바이트에 바로 접근할 수 있습니다. 이 경우 추가 연산 없이 포인터가 이미 데이터의 시작점을 가리키고 있기 때문입니다.

char *data = (char *)malloc(1024);
// 가리키는 위치를 바로 참조하겠다는 의미
int offset = 0;
// 첫 번째 바이트에 바로 접근합니다.
char *theFirstByte = data + offset;
```

위의 두 예제를 비교하면, offset이 0인 경우가 훨씬 더 직관적이고 간단하다는 것을 알 수 있습니다. 실제로 많은 프로그래밍 언어와 시스템은 0 기반 인덱싱을 사용하는데, 이는 메모리 주소 연산을 단순화하고 코드의 가독성을 향상시키기 때문입니다.

---

## 0-based vs 1-based: 범위 계산의 차이

이번에는 범위를 계산하는 경우에서의 차이를 아래와 같이 2가지의 경우를 각각 살펴보면서 0부터 시작했을 때 1부터 시작했을 때의 차이를 설명드리겠습니다.
```
(a) 0 ≤ i < 10
(b) 1 ≤ i ≤ 10
```

### 메모리 주소의 연산 간소화

배열의 첫 번째 원소의 메모리 주소를 기본 주소로 생각하면, 0 ≤ i < 10의 경우, 추가 연산 없이 바로 해당 원소에 접근할 수 있습니다. 1 ≤ i ≤ 10에서는 메모리 주소 계산 시 1을 빼야 하는 추가 연산이 필요합니다.

### 범위 계산의 직관성

0 ≤ i < 10의 경우, 배열이나 문자열의 첫 부분부터 특정 위치까지 슬라이싱 할 때, 시작 인덱스를 명시하지 않아도 됩니다. 1 ≤ i ≤ 10에서는 시작 위치 1을 항상 명시해야 합니다.

### 연속된 범위의 통합

0 ≤ i < 10과 10 ≤ i < 20처럼, 연속된 범위는 이전 범위의 마지막 값에서 바로 시작합니다. 반면, 1 ≤ i ≤ 10 다음의 연속된 범위는 11 ≤ i ≤ 20이 되어, 시작 값과 끝 값을 모두 조절해야 합니다.

---

## Dijkstra의 관점: "Why numbering should start at zero"

0-based 인덱싱에 대한 논의에서 빼놓을 수 없는 인물이 있습니다. 바로 네덜란드의 컴퓨터 과학자 **Edsger W. Dijkstra**입니다. 최단 경로 알고리즘(Dijkstra's Algorithm)으로 널리 알려진 그는 1982년에 "Why numbering should start at zero"라는 짧은 메모(EWD 831)를 남겼습니다.

Dijkstra는 이 메모에서 연속된 자연수의 부분 수열을 표기하는 네 가지 방식을 비교합니다.
```
(a) 2 ≤ i < 13
(b) 1 < i ≤ 12
(c) 2 ≤ i ≤ 12
(d) 1 < i < 13

‍

상한과 하한의 표기

Dijkstra는 (a)와 같이 하한은 ≤(이상), 상한은 <(미만)으로 표기하는 방식이 가장 우아하다고 주장했습니다. 이 방식에서는 상한과 하한의 차이가 곧 수열의 길이가 됩니다. 예를 들어 0 ≤ i < 10에서 원소의 개수는 10 - 0 = 10으로 즉시 계산됩니다.

‍

빈 수열의 자연스러운 표현

또한 (a) 방식에서는 수열이 비어있을 때 하한과 상한이 같아지는 자연스러운 표현이 가능합니다. 0 ≤ i < 0은 빈 수열을 의미하며, 음수나 부자연스러운 값 없이 표현됩니다.

‍

0부터 시작해야 하는 이유

하한을 0부터 시작하면 가장 작은 자연수를 포함할 수 있고, 하한에 부자연스러운 -1 같은 값이 등장하지 않습니다. Dijkstra는 이러한 수학적 근거를 바탕으로 "번호 매기기는 0부터 시작해야 한다"고 결론지었습니다.

이 메모는 40년이 넘은 지금까지도 0-based 인덱싱을 설명할 때 가장 많이 인용되는 자료 중 하나입니다.

‍

요약

0 ≤ i < 10과 같은 0부터 시작하는 인덱싱은 프로그래밍에서 연산의 간결함, 직관성, 그리고 메모리 접근의 효율성을 제공합니다. 반면, 1 ≤ i ≤ 10과 같은 1부터 시작하는 인덱싱은 추가 연산이나 명시적인 초기화가 필요하며, 연속된 범위 표현이 복잡해질 수 있습니다.

Dijkstra가 수학적으로 증명했듯이, 0-based 인덱싱은 단순히 관습이 아니라 연산의 효율성과 표현의 우아함에서 비롯된 합리적인 선택입니다.

‍

참고 자료

• Edsger W. Dijkstra, "Why numbering should start at zero" (EWD 831, 1982)https://www.cs.utexas.edu/~EWD/transcriptions/EWD08xx/EWD831.html