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

1. 자료 구조

• 데이터: 모든 유형의 정보를 망라하는 용어
• 자료구조: 데이터를 조직하는 방법

2. 배열: 기초 자료 구조

• 배열: 데이터 원소들의 리스트

2.1 자료구조 연산

• 읽기: 특정 위치를 찾아보는 것
• 검색: 자료구조 내에서 특정 값을 찾는 것
• 삽입: 자료구조에 새로운 값을 추가하는 것
• 삭제: 자료구조에서 값을 제거하는 것

3. 속도 측정

• 연산이 얼마나 빠른가를 측정할 때는 시간 관점에서 측정하지 않고 얼마나 많은 단계가 필요한지를 논해야 한다.
• 연산의 속도 측정 → 시간 복잡도 측정
  • == 속도, 시간 복잡도, 효율성, 성능

4. 읽기

• 읽기: 배열 내 특정 인덱스에 어떤 값이 들어 있는지 찾아보는 것
• 컴퓨터의 특징
  1. 컴퓨터는 모든 메모리 주소에 한 번에 갈 수 있다.
  2. 컴퓨터는 배열을 할당할 때 어떤 메모리 주소에서 시작하는지도 기록해 둔다.
• 배열 읽기는 매우 효율적인 연산이다.
• O(1)

5. 검색

• 검색: 배열에 특정 값이 있는지 알아본 후, 있다면 어떤 인덱스에 있는지 찾는 것
• 컴퓨터가 특정 값으로 바로 갈 수 없기 때문에 오래 걸린다.
• 컴퓨터의 특징: 컴퓨터는 모든 메모리 주소에 한 번에 접근하지만 각 메모리 주소에 어떤 값이 있는지 바로 알 수 없다.
• O(N)

6. 삽입

• 배열에 새 데이터를 삽입하는 연산은 배열의 어디에 데이터를 삽입하는가에 따라 효율성이 다르다.
• 컴퓨터의 특징: 배열을 할당할 때 항상 배열의 크기를 기록한다
• 배열의 끝에 새 원소를 삽입하는 경우: 컴퓨터는 메모리 새롭게 추가되는 원소의 메모리 주소를 바로 알 수 있다.
• 배열의 처음이나 중간에 원소를 삽입하는 경우: 삽입할 공간을 만들기 위해 많은 데이터 조각을 이동시켜야 한다.
• O(N)

7. 삭제

• 특정 인덱스의 값을 제거한다.
• 배열에 비어 있는 공간이 생기면 효율적이지 않으므로, 데이터를 옮겨 빈 공간을 메워야 한다.
• O(N)

8. (배열기반)집합: 단 하나의 규칙으로 효율성이 달라진다

• 집합: 중복 값을 허용하지 않는 자료구조
• 배열 기반 집합: 값들의 단순 리스트, 배열과 거의 비슷하다. 그러나 집합은 중복 값의 삽입을 허용하지 않는다.
• 읽기, 검색의 시간 복잡도는 배열과 같다.
• 삽입
  • 배열에서는 다른 값을 확인하지 않고 적절한 자리에 넣으면 끝이다.
  • 집합에서는 새로운 값이 이미 집합에 들어 있는지 알아내야 한다.
  • 중복 데이터를 허용하지 않기 때문이다.
  • 따라서 삽입에는 검색이 우선이다.
  • 최선의 시나리오: 집합의 끝에 삽입할 때 → O(N+1)
  • 최악의 시나리오: 집합의 맨 앞에 삽입할 때 → O(2N+1)