기능과 구현
기능 : 연산이 무엇을 하는지
구현 : 연산의 기능을 어떻게 하는지
추상 자료형
자료구조를 추상화 한 것
-> 데이터를 저장, 사용할 때 기능만 생각
추상화
구현을 몰라도 기능만 알면 프로그래밍을 할수있게 해주는 개념
자료구조는 구현까지 알아야해서 생각할 부분이 기능 뿐만 아니라 구현까지 해서 복잡해지지만 추상 자료형은 기능에만 집중 할 수있기 때문에 조금더 생각을 줄일 수있다.
⇒ 추상 자료형을 생각하면 코드의 흐름에 집중 할 수있다.
파이썬
- 추상화가 많이된 고수준 언어
- 많은 자료형 이름이 추상 자료형
리스트
- 데이터간 순서 관계를 유지 할 수있다.
- 접근 연산 : 특정 위치에 있는 데이터를 가지고 오거나 수정한다.
- 탐색 연산 : 특정 조건을 만족하는 데이터를 찾는다.
- 삽입 연산 : 특정 위치에 새로운 데이터를 저장한다.
- 삭제 연산 : 특정 위치에 있는 데이터를 지운다.
파이썬 자료형 list → 구현을 몰라도 기능 만 알고 있으면 사용할 수있다.
⇒ 파이썬 리스트는 동적배열로 구현되어있다.→ 아마 접근을 많이 하기때문이 아닐까 싶다.
추상 자료형을 어떤 자료 구조로 구현 할것인지는 이 기능이 많이 하고자하는 연산의 시간 복잡도를 비교해서 결정 하면된다.
큐
- 데이터간 순서 관계를 유지 할수있다.
- 선입 선출
- 맨뒤 데이터 추가
- 맨앞 데이터 삭제
- 맨앞 데이터 접근
파이썬은 데크 deque 즉, 양면 큐를 제공한다.
데크
- 맨앞과 뒤에 데이터를 삽입하고 삭제 할수있게 해주는 자료형
⇒ 파이썬 데크는 더블 링크드 리스트로 구현이 되어있다. → 맨앞삭제 연산이 O(1)이기 때문이다.
스택
- 데이터 간 순서관계를 유지할 수있다.
- 후입선출
- 맨 뒤 데이터 추가
- 맨 뒤 데이터 삭제
- 맨 뒤 데이터 접근
파이썬의 deque와 리스트를 활용하여 스택을 구현 할수있다.
둘다 스택관련 기능의 시간 복잡도가 O(1)밖에 걸리지 않기 때문이다.
딕셔너리 (맵)
- 데이터간 순서 관계를 약속하지 않는다
- 키 밸류 데이터 쌍 삽입
- 키를 이용한 데이터 탐색
- 키를 이용한 데이터 삭제
파이썬은 딕셔너리를 제공하고 있으며 해시테이블로 구현이 되어있다. 이때 딕셔너리 관련 연산의 시간복잡도는 모두 O(1)이다.
세트
- 데이터간 순서관계를 약속하지 않음
- 삽입 : 데이터를 저장할 수있다.(중복데이터 X)
- 탐색 : 데이터가 저장되었는지 확인할수있다.
- 삭제 : 저장한 데이터를 지울수있다.
세트는 해시테이블로 구현이 되어있다. 인덱스에 키만 저장하는식으로 해시테이블을 사용하여 세트를 구현할수있다. 해시테이블로 구현하므로 세트관련 연산의 시간 복잡도는 O(1)이다
파이썬 자료형 주요 시간 복잡도
리스트 (동적 배열)
| 연산 | 시간 복잡도 |
| 접근 | O(1) |
| 추가 | O(1) (분할 상환) |
| 맨 뒤 삭제 | O(1) (분할 상환) |
| 길이 확인 | O(1) |
| 삽입 | O(n) |
| 삭제 | O(n) |
| 탐색 | O(n) |
deque (더블리 링크드 리스트)
| 연산 | 시간 복잡도 |
| 맨 앞 삭제 | O(1) |
| 맨 앞 삽입 | O(1) |
| 맨 뒤 삭제 | O(1) |
| 맨 뒤 삽입 | O(1) |
| 길이 확인 | O(1) |
딕셔너리 (해시 테이블)
| 연산 | 시간 복잡도 |
| 탐색 | O(1) (평균) |
| 삽입 | O(1) (평균) |
| 삭제 | O(1) (평균) |
| 길이 확인 | O(1) |
세트 (해시 테이블)
| 연산 | 시간 복잡도 |
| 탐색 | O(1) (평균) |
| 삽입 | O(1) (평균) |
| 삭제 | O(1) (평균) |
| 길이 확인 | O(1) |
💡 데이터의 어떤 관계가 필요하고 어떤 기능들을 사용 할건지 잘생하면 더 효율적인 프로그램을 작성할수있다.
