Page 22 -

2. 컴퓨터는 배열을 할당할 때 어떤 메모리 주소에서 시작하는지도 기록해 둔다. 그래서 배열의 첫 1
번째 원소를 찾으라고 요청하면 적절한 메모리 주소로 바로 가서 찾는다.

위와 같은 점들이 컴퓨터가 배열의 첫 번째 값을 어떻게 한 번에 찾아내는지 설명한다. 하지만 컴 자료 구조가 중요한 까닭
퓨터는 어떤 인덱스에 있는 값이든 간단한 덧셈을 수행해 찾을 수 있다. 컴퓨터에 인덱스 3에 있

는 값을 찾으라고 요청하면 컴퓨터는 인덱스 0의 메모리 주소를 가져와 3을 더한다(어차피 메모
리 주소는 순차적이다).

이제 식료품 리스트 배열에 적용해 보자. 예제 배열은 메모리 주소 1010에서 시작한다. 컴퓨터에
인덱스 3에 있는 값을 읽으라고 명령하면 컴퓨터는 다음과 같은 과정을 밟는다.

1. 배열의 인덱스는 0부터 시작하며 인덱스 0의 메모리 주소는 1010이다.

2. 인덱스 3은 인덱스 0부터 정확히 세 슬롯 뒤에 있다.

3. 따라서 인덱스 3을 찾으려면 1010+3인 1013 메모리 주소로 간다.

인덱스 3의 메모리 주소가 1013임을 알아낸 컴퓨터는 바로 접근해서 "dates"라는 값을 찾을 수
있다.

보다시피 컴퓨터는 어떤 메모리 주소에든 한 번에 접근해 어떤 인덱스든 읽을 수 있으니 배열 읽
기는 매우 효율적인 연산이다. 컴퓨터의 사고 과정을 세 부분으로 나누어 설명했으나 우선은 가장

핵심적인 컴퓨터가 메모리 주소로 가는 단계를 중점적으로 살펴봤다(이어지는 장들에서 중점적으
로 살펴야 할 단계를 어떻게 알아내는지 설명한다).

한 단계로 끝나는 연산은 당연히 가장 빠른 연산 유형이다. 배열은 기초 자료 구조일 뿐만 아니라
빠르게 읽을 수 있는 아주 강력한 자료 구조이다.

그렇다면 컴퓨터에 인덱스 3에 들어 있는 값이 무엇인지 묻는 대신 "dates"가 배열의 어느 인덱
스에 들어 있는지 물어보면 어떨까? 이를 검색 연산이라 부르며 다음 절에서 알아본다.

1.5 검색 DATA STRUCTURES AND ALGORITHMS

앞서 언급했듯이 배열 검색은 배열에 특정 값이 있는지 알아본 후, 있다면 어떤 인덱스에 있는지
찾는 것이다.

035