문인철 교수님의 ‘데이터 구조 및 분석: Linear Structure and Dynamic Programming’ 수업
Abstract Data Types and Array
Abstract Data Types
Data abstraction is the reduction of a particular body of data to a simplified representation of the whole
- 데이터를 store (insert, delete), search 를 할 수 있음
- 어떤 데이터가 저장될 것인가
- 데이터의 Operations
- 해당 데이터의 operations 의 에러 조건 - 특정 데이터가 없는 경우 에러를 어떻게 할것인가? - 속의 데이터는 알지 못하나, 어떤 operation 을 통해 어떤 영향을 받는지를 알 수 있음
Array
Create
- Python 에서는 List 라고 불리고 있음
- 각 요소들을 index 를 이용하여 접근
- 매우 간단하게 생성할 수 있음
Search
- 모든 인덱스를 다 탐색해서 원하는 요소를 찾을 수 있음
- 최악의 경우 n 번만큼 탐색 후에 원하는 요소를 찾을 수 있음
Insert
- 조건 c 를 b 와 d 사이에 삽입하는 경우 (a = 삽입 index) - 새로운 배열 y 를 생성 → x 보다 셀이 하나 더 많게 생성 - x[0: a-1] 를 y[0:a-1] 까지 복사 - y[a] 에 c 링크 - x[a:] 를 y[a+1:] 복사 - 전체 탐색 수: n 만큼
- 코드
x = ['a', 'b', 'd', 'e', 'f']
y = list(range(len(x) + 1))
insert_index = 2
insert_value = 'c'
for i in range(len(y))):
if i < insert_index:
y[i] = x[i]
if i == insert_index:
y[i] = insert_value
else:
y[i] = x[i-1]
Delete
- 조건 d 를 삭제 하는 경우 (a = 삽입 index) - 새로운 배열 y 를 생성 → x 보다 셀이 하나 더 적게 생성 - x[0: a-1] 를 y[0:a-1] 까지 복사 - x[a+1:] 를 y[a:] 복사 - 전체 탐색 수: n - 1 만큼
- 코드
x = ['a', 'b', 'c', 'd', 'e', 'f']
y = list(range(len(x) - 1))
delete_index = 3
for i in range(len(x))):
if i < insert_index:
y[i] = x[i]
if i > insert_index:
y[i-1] = x[i]
단점
- Array 에 어떤거를 삭제하거나 추가할때 line-wise 탐색해야함, 즉 배열 n만큼