누구나 자료 구조와 알고리즘

1장 자료 구조가 중요한 까닭

주로 배열을 예시로 들면서 설명하고 있음

목차

1. 코드가 자료 구조와 상호작용하는 기본 방법: 네 가지 연산
2. 읽기
3. 검색
4. 삽입
5. 삭제
6. 집합: 단 하나의 규칙이 효율성을 바꾼다
7. 마무리

1. 코드가 자료 구조와 상호작용하는 기본 방법: 네 가지 연산

1. 읽기
   • 자료 구조 내 특정 위치를 찾는 것
   • ex. 배열에서는 특정 인덱스의 값을 찾아보는 것
2. 검색
   • 자료 구조 내 특정 값을 찾는 것
   • ex. 배열에서는 특정 값이 배열에 들어 있는지, 어떤 인덱스에 있는지 알아보는 것
3. 삽입
   • 자료 구조에 새로운 값을 추가하는 것
   • ex. 배열에서는 배열 내 슬롯을 만들어 새 값을 추가하는 것
4. 삭제
   • 자료 구조에서 값을 제거하는 것
   • ex. 배열의 값 중 하나를 제거하는 것

연산이 얼마나 "빠른가"를 측정할 때는 순수하게 시간 관점에서 연산이 얼마나 빠른지가 아니라 얼마나 많은 단계가 필요한지 논해야 한다.

속도는 하드웨어의 성능에 따라 달라지기 때문

연산 속도 측정은 시간 복잡도(연산에 걸리는 단계 수)를 측정하는 것

2. 읽기

: 배열 내 특정 인덱스에 어떤 값이 들어 있는지 찾아보는 것

컴퓨터는 배열 내 특정 인덱스에 한 번에 접근할 수 있기 때문에 배열에서 읽기는 딱 한 단계.

프로그램이 배열을 선언 -> 연속된 빈 셀들의 집합을 할당 -> 배열의 인덱스에 메모리 주소 저장

값 읽는 과정
1. 배열의 인덱스 0의 주소는 1010
2. 인덱스 3은 인덱스 0부터 3슬롯 뒤다.
3. 1010 + 3 = 1013 메모리 주소로 간다.

3. 검색

: 배열에 특정 값이 있는지 알아본 뒤, 있다면 어떤 인덱스에 있는지 찾음

검색 과정

1. 인덱스 0부터 값을 확인하고 다음 인덱스 값 확인 (선형 검색)
   • 한 번에 한 셀의 값을 확인한다.
2. 찾는 값이 인덱스 n에 있으면 n-1만큼의 단계가 필요

4. 삽입

: 배열 내 슬롯을 만들어 새 값을 추가

삽입 종류

1. 배열의 맨 끝에 삽입하는 경우: 1단계
2. 중간에 삽입하는 경우: n/2 + 1
   • 중간에 삽입하는 경우, 삽입하려는 위치 뒤쪽에 있는 값들을 한 칸씩 뒤로 밀고 삽입해야 한다.
3. 맨 처음 삽입: n + 1 (최악의 경우)

5. 삭제

: 배열의 값 중 하나를 제거하는 것

삽입 종류

1. 배열의 맨 끝에 삭제하는 경우: 1단계
2. 중간의 값을 삭제하는 경우: n/2 + 1
   • 중간 값을 삭제하는 경우, 삭제한 뒤 위치 뒤쪽에 있는 값들을 한 칸씩 앞으로 당겨야 한다.
3. 맨 처음 삭제: n (최악의 경우)

6. 집합: 단 하나의 규칙이 효율성을 바꾼다

집합은 중복을 허용하지 않는 배열.
집합과 배열은 읽기와 검색, 삭제는 차이가 없다.

삽입의 경우에는 먼저 삽입할 값이 집합에 있는지 확인한 뒤 삽입해야 하므로 모든 삽입에는 검색이 우선된다.

따라서 집합은 배열보다 느리지만 중복 데이터가 없어야 할 때는 집합이 답이다.

요구사항을 분석한 후 자료 구조를 결정해야 한다.