Page 11 -

그림 1-1

ˮapplesˮ ˮbananasˮ ˮcucumbersˮ ˮdatesˮ ˮelderberriesˮ

인덱스 0 인덱스 1 인덱스 2 인덱스 3 인덱스 4

배열 같은 자료 구조의 성능을 알려면 코드가 자료 구조와 일반적으로 어떻게
상호 작용하는지 분석해야 한다.

대부분의 자료 구조는 네 가지 기본 방법을 사용하며, 이를 연산이라 부른다.

● 읽기: 읽기는 자료 구조 내 특정 위치를 찾아보는 것이다. 배열에서는 특
정 인덱스의 값을 찾아보는 것을 뜻한다. 가령 인덱스 2에 들어 있는 물
건을 찾는 게 배열 읽기의 예다.

● 검색: 검색은 자료 구조 내에서 특정 값을 찾는 것이다. 배열에서는 특정
값이 배열에 들어 있는지, 만약 그렇다면 어떤 인덱스에 있는지 알아보는
것을 뜻한다. 예를 들어 "dates"가 식료품 목록에 있는지, 어떤 인덱스
에 있는지 알아보는 게 배열 검색이다.

● 삽입: 삽입은 자료 구조에 새로운 값을 추가하는 것이다. 배열이라면 배
열 내에 슬롯을 더 만들어 새 값을 추가하는 것을 뜻한다. 앞선 쇼핑 목록
에 "figs"를 추가하는 게 배열에 새 값을 삽입하는 예다.

● 삭제: 삭제는 자료 구조에서 값을 제거하는 것이다. 배열에서는 배열의
값 중 하나를 제거하는 것을 뜻한다. 예를 들어 예제의 식료품 목록에서
"bananas"를 제거하는 게 배열 삭제다.

1장에서는 각 연산을 배열에 적용했을 때 얼마나 빠르게 수행되는지 알아본다.

이쯤에서 이 책이 다루는 첫 번째 깜짝 놀랄만한 개념이 나온다. 연산이 얼마나
“빠른가”를 측정할 때는 순수하게 시간 관점에서 연산이 얼마나 빠른가가 아니
라 얼마나 많은 단계가 필요한지를 논해야 한다.

022

algorith06.indd 22 2018-06-25 오전 10:32:02