[자료구조] 배열(Array)

배열이란?

메모리 상에 원소를 연속하게 배치한 자료구조

• 배열에 저장되는 요소들은 모두 동일한 자료형을 가져야 한다.
• 배열은 생성될 때 크기가 정해진다.
• 파이썬에서는 리스트 타입이 배열의 기능을 한다.

 

 

배열의 성질

1. O(1)에서 k번째 원소를 확인/변경 가능
2. 추가적으로 소모되는 메모리 양(=overhead)가 거의 없음
3. Cache hut rate가 높음
   • 배열의 인접한 요소들은 함께 캐시에 로드되어 캐시 라인 활용을 최대화하며, 이로 인해 데이터 접근 시간을 줄여 더 빠른 연산을 가능케 하는 것
4. 메모리 상에 연속한 구간을 잡아야 해서 할당에 제약이 걸림

 

 

기능과 구현

# 1차원 배열 = 리스트
arr = [1, 2, 3, 4]
print(arr[3]) # 4 출력

# 2차원 배열
arr2 = [[1, 2, 3], [4, 5, 6]]
print(arr[1][0]) # 4 출력

임의의 위치에 있는 원소를 확인/변경 = O(1)

원소를 끝에 추가 = O(1)

마지막 원소를 제거 = O(1)

임의의 위치에 원소를 추가/임의 위치에 원소 제거 = O(N)

 

 

리스트 자료형과 메서드의 시간 복잡도

	Operation	Example	Class	Notes
1	Index	l[i]	O(1)	인덱스로 값 찾기
2	Store	l[i] = 0	O(1)	인덱스로 데이터 저장
3	Length	len(l)	O(1)	리스트 길이
4	Append	l.append(5)	O(1)	리스드 뒤에 데이터 저장
5	Pop	l.pop()	O(1)	가장 뒤의 데이터 pop
6	Clear	l.clear()	O(1)	l = []
7	Slice	l[a:b]	O(b-a)	슬라이싱되는 요소들 수 만큼 비례
8	Extend	l.extend(...)	O(len(...))	확장되는 길이만큼
9	Construction	list(...)	O(len(...))	리스트 길이만큼
10	check ==, !=	l1 == l2	O(N)	전체 리스트가 동일한지 확인
11	Insert	l[a:b] = ...	O(N)	데이터 삽입
12	Delete	del l[i]	O(N)	데이터 삭제
13	Containment	x in/not in l	O(N)	포함 여부 확인
14	Copy	l.copy()	O(N)	복제
15	Remove	l.remove(...)	O(N)	제거
16	Pop	l.pop(i)	O(N)	제거된 값 이후 전부 한칸씩 당겨줘야함
17	Extreme value	min(l)/max(l)	O(N)	전체 데이터 확인해야함
18	Reverse	l.reverse()	O(N)	뒤집기
19	Iteration	for v in l:	O(N)	전체 데이터 확인하므로
20	Sort	l.sort()	O(N Log N)	파이썬 기본 정렬 알고리즘
21	Multiply	k*l	O(k N)	리스트의 곱은 리스트 개수 늘어남