🪡 자료 구조가 중요한 까닭

제이 웬그로우의 『누구나 자료구조와 알고리즘』을 읽으며 정리한 기록
예제 소스

코드 품질의 두 가지 축

좋은 코드는 단순히 “동작하는 코드”만을 의미하지 않는다.
코드의 품질은 보통 다음과 같은 기준으로 평가할 수 있다.

• 유지 보수성 - 가독성 / 조직 / 코드 모듈성
• 효율성 - 실행 속도 / 메모리 사용

데이터를 어떻게 조작하느냐가 코드의 실행 속도에 큰 영향을 미친다.

자료 구조

• 데이터: 수, 문자열처럼 프로그램에서 다루는 값
• 자료 구조: 데이터를 조직하는 방법

같은 데이터라도 어떤 자료 구조를 사용하느냐에 따라 코드의 성능이 크게 달라진다.

배열 (Array)

배열은 가장 기본적인 자료 구조로, 데이터 원소들을 순서대로 저장한다.

array = ["apples", "bananas", "cucumbers", "dates", "elderberries"];

배열의 네 가지 기본 연산

다음 네 가지 연산을 통해 자료 구조의 성능을 분석할 수 있다.

• 읽기: 인덱스로 값 접근
• 검색: 값으로 인덱스 찾기
• 삽입: 새 데이터 삽입
• 삭제: 데이터 제거

연산의 속도 측정

연산의 빠르고 느림을 판단할 때는 실제 시간이 아닌 필요한 단계 수를 알아야 한다.

연산의 속도 측정 = 연산의 시간 복잡도 측정

① 읽기 (Read)

특정 인덱스에 저장된 값을 찾는 연산

💡 컴퓨터의 특징

• 1. 컴퓨터는 모든 메모리 주소에 한 번에 접근 가능
• 2. 배열 할당 시 시작 메모리 주소를 기록
• 3. 배열 할당 시 배열의 크기를 기록

위와 같은 특징 때문에 배열의 어떤 인덱스든 즉시 접근할 수 있다.

• 읽기 연산 = 1단계

② 검색 (Search)

값을 제공받아 그 값이 저장된 인덱스를 찾는 연산

선형 검색(Linear Search)

array = ["apples", "bananas", "cucumbers", "dates", "elderberries"];

// "elderberries" 검색
// [0]: "apples" - 1단계
// [1]: "bananas" - 2단계
// [2]: "cucumbers" - 3단계
// [3]: "dates" - 4단계
// [4]: "elderberries" - 5단계

• 배열에서 특정 값을 찾으려면 배열의 각 셀을 앞에서부터 하나씩 조사해야 한다.
  이처럼 처음부터 끝까지 순서대로 값을 확인하는 방식을 선형 검색이라고 한다.
• 즉, elderberries를 찾기 위해서는 모든 셀을 검색해야 한다. (5개 = 5개의 단계)

배열 중간에 있는 값 검색

// "dates" 검색
array = ["apples", "bananas", "cucumbers", "dates", "elderberries"];

// [0]: "apples" - 1단계
// [1]: "bananas" - 2단계
// [2]: "cucumbers" - 3단계
// [3]: "dates" - 4단계

• "dates"는 인덱스 3에 있기 때문에 4단계 만에 찾을 수 있다.

검색의 최악의 경우

최악의 경우는 찾는 값이 배열의 맨 뒤에 있거나, 배열 안에 없는 경우이다.

• 찾는 값이 맨 뒤에 있는 경우: 마지막 요소까지 확인해야 한다.
• 찾는 값이 없는 경우: 값이 없다는 것을 알기 위해 모든 요소를 끝까지 확인해야 한다.
• 최악의 경우: N개 요소 = N단계

③ 삽입 (Insert)

새 데이터를 배열에 추가하는 연산, 삽입 위치에 따라 효율성이 달라진다.

배열 끝에 삽입 (가장 효율적)

// 배열 끝에 "figs" 추가
array = ["apples", "bananas", "cucumbers", "dates", "elderberries"];

array.push("figs"); // → 1단계

배열 중간에 삽입

// array[2]에 "figs" 삽입
array = ["apples", "bananas", "cucumbers", "dates", "elderberries"];

// 1단계: 마지막 셀 오른쪽으로 이동
array = ["apples", "bananas", "cucumbers", "dates", "", "elderberries"];
// 2단계: "dates" 오른쪽으로 이동
array = ["apples", "bananas", "cucumbers", "", "dates", "elderberries"];
// 3단계: "cucumbers" 오른쪽으로 이동
array = ["apples", "bananas", "", "cucumbers", "dates", "elderberries"];
// 4단계: "figs" 삽입
array = ["apples", "bananas", "figs", "cucumbers", "dates", "elderberries"];

// → 3단계(이동) + 1단계(삽입) = 4단계

배열 맨 앞에 삽입 (가장 비효율적)

// array[0]에 "figs" 삽입
array = ["apples", "bananas", "cucumbers", "dates", "elderberries"];

// 모든 기존 요소를 오른쪽으로 이동
// → 5단계(이동) + 1단계(삽입) = 6단계

• 최악의 경우: N개 요소 = N + 1단계

④ 삭제 (Delete)

배열에서 특정 인덱스의 값을 제거하는 연산

💡 삭제의 핵심

삭제 후 빈 공간을 채우기 위해 뒤의 모든 요소를 한 칸씩 왼쪽으로 이동해야 함

배열 끝에서 삭제 (가장 효율적)

// 배열 끝에 "elderberries" 삭제
array = ["apples", "bananas", "cucumbers", "dates", "elderberries"];

array.pop(); // → 1단계

배열 중간에서 삭제

// array[2] cucumbers 삭제
array = ["apples", "bananas", "cucumbers", "dates", "elderberries"];

// 1단계: "cucumbers" 삭제
array = ["apples", "bananas", "", "dates", "elderberries"];
// 2단계: "dates" 왼쪽으로 이동
array = ["apples", "bananas", "dates", "", "elderberries"];
// 3단계: "elderberries" 왼쪽으로 이동
array = ["apples", "bananas", "dates", "elderberries", ""];

// 1단계(삭제) + 2단계(이동) = 3단계

배열 맨 앞에서 삭제 (가장 비효율적)

array = ["apples", "bananas", "cucumbers", "dates", "elderberries"];

// 모든 나머지 요소를 왼쪽으로 이동해야 한다.
// → 4단계(이동) + 1단계(삭제) = 5단계

• 최악의 경우: N개 요소 = N개 단계

배열 성능 요약

연산	최악의 경우
읽기	1단계
검색	N단계
삽입	N + 1단계
삭제	N단계

집합 (Set)

집합은 중복 값을 허용하지 않는 자료 구조 (이 글에서는 배열 기반 집합을 다룸)

• 읽기, 검색, 삭제: 배열과 동일한 효율성을 가진다.

삽입

집합의 핵심 특징은 중복을 허용하지 않는 것이다. 따라서 삽입 전에 검색이 필수다.

set = ["apples", "bananas", "cucumbers", "dates", "elderberries"];

// "figs" 삽입
// 1단계 - set[0]에서 "figs" 검색
// 2단계 - set[1]에서 "figs" 검색
// 3단계 - set[2]에서 "figs" 검색
// 4단계 - set[3]에서 "figs" 검색
// 5단계 - set[4]에서 "figs" 검색
// 6단계 - 집합 끝에 "figs" 삽입

// 5단계(검색) + 1단계(삽입) = 6단계

• 집합의 끝에 새 값 삽입: N+1단계

정리

자료 구조의 성능을 측정하는 것은 연산에 필요한 단계 수를 구하는 것이다.
같은 데이터도 어떤 자료 구조를 선택하고, 어느 위치에서 연산을 수행하느냐에 따라 효율성이 크게 달라진다.

연습 문제

1. 원소 100개를 포함하는 배열이 있을 때, 다음 연산에 걸리는 단계 수를 계산

a. 읽기

1단계 (배열의 어떤 인덱스든 직접 접근할 수 있다.)

b. 배열에 들어 있지 않은 값 검색

100단계 (값이 배열에 없는지 확인하려면 모든 요소를 끝까지 검사해야 한다.)

c. 배열 맨 앞에 삽입

101단계 (100개 요소를 모두 오른쪽으로 이동(100단계) + 삽입(1단계))

d. 배열 맨 뒤에 삽입

1단계 (배열의 끝에 추가하면 기존 요소를 이동할 필요가 없다.)

e. 배열 맨 앞에서 삭제

100단계 (삭제(1단계) + 99개 요소를 모두 왼쪽으로 이동(99단계) = 100단계)

f. 배열 맨 뒤에서 삭제

1단계 (배열의 마지막 요소를 삭제하면 이동할 요소가 없다.)

2. 원소 100개를 포함하는 배열 기반 집합이 있을 때, 다음 연산에 걸리는 단계 수를 계산

a. 읽기

1단계 (배열 기반 집합도 배열처럼 인덱스를 알고 있으면 바로 접근할 수 있다.)

b. 배열에 들어 있지 않은 값 검색

100단계 (값이 집합에 없는지 확인하려면 모든 요소를 끝까지 검사해야 한다.)

c. 집합 맨 앞에서 새 값 삽입

201단계 (검색 100단계 + 이동 100단계 + 삽입 1단계 = 201단계)

d. 집합 맨 뒤에 새 값 삽입

101단계 (검색 100단계 + 삽입 1단계)

e. 집합 맨 앞에서 삭제

100단계 (삭제 1단계 + 99개 요소를 모두 왼쪽으로 이동 99단계 = 100단계)

f. 집합 맨 뒤에서 삭제

1단계 (마지막 요소를 삭제하면 이동할 요소가 없다.)

3. 일반적으로 배열에서 검색 연산은 주어진 값의 첫 인스턴스를 찾는다.

하지만 주어진 값의 모든 인스턴스를 찾을 때가 있다. 예를 들어 배열에 "apple"이 몇 번 나오는지 세고 싶다. 모든 "apple"을 찾는 데 몇 단계가 걸릴까? N에 대해 답하라.

답

N단계 (모든 인스턴스를 찾으려면 배열의 모든 요소를 검사해야 하므로, 배열의 크기와 같은 N단계가 필요)