TIL_32 : 배열

🙄 배열

---

➡ 배열이란?

• Python의 list 와 유사

C 배열	Python list
크기가 고정돼 있다	.append 를 이용해 크기를 늘릴 수 있다
같은 type의 데이터만 담을 수 있다	여러 type의 데이터를 담을 수 있다
데이터가 메모리에 연속적으로 저장	레퍼런스가 메모리에 임의적으로 저장

👉 list 에는 값 자체가 저장되는 것이 아니기 때문에 값의 type, 크기가 상관없다
👉 배열은 가장 기본적인 자료 구조기 때문에 중요

➡ 배열 인덱스를 이용한 데이터 저장/접근

• 시작 주소 값만 알면 어떤 인덱스든 주소를 쉽게 구할 수 있음
• 주소만 있으면 그 주소가 어디에 있든 $O(1)$으로 접근할 수 있음

➡ 배열 탐색

• 특정 조건을 만족하는 값을 찾기 위해서 배열을 순회하기 때문에 접근보다 비효율적
• 특정 순서로 정렬되어 있지 않으면 선형 탐색 보다 효율적일 수 없음
• 선형 탐색 시간복잡도 : $O(n)$

➡ 정적 배열

• 크기 고정 (요소 수 제한)
• 보통 배열을 얘기하면 정적 배열

➡ 동적 배열

• 크기 변함 (요소 계속 추가 가능)
• 정적 배열로 만들어진 자료 구조
• 정적 배열의 크기를 상황에 맞게 조절

➡ 동적 배열 추가 연산 시간 복잡도

• 추가 연산 (append operation) : 배열의 가장 끝에 새 값을 넣는 것

1. 정적 배열 남는 공간 있을 때
   비어 있는 공간 중 가장 앞에 값을 추가하면 됨 (최선의 경우) = $O(1)$

2. 정적 배열이 꽉 찼을 때
   2.1 현재 배열이 사용 중인 공간보다 큰 메모리 공간 예약
   2.2 기존 배열에서 새로운 배열로 값을 모두 복사
   2.3 빈칸에 값을 추가 (최악의 경우) = $O(n)$

➡ 분할 상환 분석 (Amortized Analysis)

• 같은 동작을 $n$번 했을 때 드는 시간이 $X$일때 동작을 한 번 하는 데 걸린 시간 : $X/n$
• 보통 시간 복잡도는 최악의 경우를 이야기, 동적 배열 추가 연산 시간 복잡도는 $O(n)$
• 최선의 경우가 자주 일어나는 반면 최악의 경우는 가끔 일어남

👉 분할 상환 분석은 시간 복잡도를 최악의 경우가 아닌 평균을 내는 것
👉 최악의 경우로 시간 복잡도를 얘기하는 것이 비합리적인 경우에 사용

➡ 동적 배열 삽입 연산

• 삽입 연산 (insert operation) : 아무 위치에 데이터를 추가

1. 정적 배열 남는 공간 있을 때
   1.1 최악의 경우 $n$개의 요소를 한칸씩 뒤로 옮김 = $O(n)$
   1.2 새로운 데이터 추가 = $O(1)$
   시간 복잡도 = $O(n+1)$ = $O(n)$

2. 정적 배열이 꽉 찼을 때
   2.1 현재 배열이 사용 중인 공간보다 큰 메모리 공간 예약
   2.2 기존 배열에서 새로운 배열로 값을 모두 복사 = $O(n)$
   2.3 최악의 경우 $n$개의 요소를 한칸씩 뒤로 옮김 = $O(n)$
   2.4 새로운 데이터 추가 = $O(1)$
   시간 복잡도 = $O(2n+1)$ = $O(n)$

➡ 동적 배열 삭제 연산

1. 맨 앞 데이터를 지울 때 (최악의 경우)
   1.1 데이터 삭제 후 $n-1$개의 요소를 한칸씩 앞으로 옮김 = $O(n-1)$
   시간 복잡도 = $O(n-1)$ = $O(n)$

2. 맨 뒤 데이터를 지울 때
   시간 복잡도 = $O(1)$

➡ 배열 vs 동적 배열

연산 & 시간 복잡도

	배열	동적 배열
접근 (access)	$O(1)$	$O(1)$
탐색 (search)	$O(n)$	$O(n)$
삽입 (insert)	$N/A$	$O(n)$, 맨 뒤 $O(1)$
삭제 (delete)	$N/A$	$O(n)$, 맨 뒤 $O(1)$

낭비하는 공간

• 배열 : 크기가 고정되어 있기 때문에 낭비하는 공간이 없다
• 동적 배열 : 공간을 낭비할 수도 있고 안 할 수도 있다
  최악의 경우 (새로운 배열을 만들었을 때) : 낭비되는 공간이 최대
  저장된 요소 수 : $n$
  낭비되는 공간 : $n-2$ = $O(n-2)$ = $O(n)$