자료 구조를 파이썬으로 공부해보기
자료 구조
자료 구조는 크게 선형 자료구조와 비선형 자료구조로 나눌 수 있다.
배열
배열은 데이터(원소)를 순서대로 가지고 있으며 변경 가능한 선형 자료 구조다. 배열은 인덱스를 통해 어떤 원소든 쉽게 접근할 수 있지만, 원소를 추가하거나 삭제할 때는 비효율적이다. 파이썬에서 배열은 list이며, 내부적으로 동적 배열로 구
현되어 있다. 객체들이 연속한 메모리에 있지 않지만, 객체의 메모리 주소가 연속한 메모리에 저장되어 있어 인덱싱이 가능하다.
배열와 관련된 연산의 시간 복잡도
| 연산 | 시간 복잡도 | 비고 |
| len(a) | O(1) | |
| a[i] | O(1) | |
| a[i:j] | O(k) | i 부터 j - 1까지 k개에 대한 조회가 필요하다. |
| elem in a | O(n) | 처음부터 끝까지 순차 탐색한다. |
| a.count(elem) | O(n) | |
| a.index(elem) | O(n) | index 함수는 배열에서 원하는 값을 처음 찾았을 때 위치를 알려준다. |
| a.append(elem) | O(1) | |
| a.pop() | O(1) | |
| a.pop(0) | O(n) | 이럴 경우 deque를 사용하는 게 좋다. |
| del a[i] | O(n) | pop과 비슷하다. |
| a.sort() | O(nlogn) | Timsort를 사용하고 최선의 경우에는 O(n) 실행된다. |
| a.reverse() | O(n) | |
| min(a), max(a) | O(n) | 전체를 선형 탐색해 찾는다. |
연결 리스트
연결 리스트는 원소 대신 노드라는 개념을 사용한다. 각 노드는 데이터(객체에 대한 메모리 주소)와 다음 노드의 주소(포인터)를 가지고 있으며, 서로 연결된 구조를 띄고 있어 연결 리스트라고 한다. 연결 리스트는 배열과 다르게 새로운 노드를 삽입하거나 삭제할 때 시간이 적게 걸린다.
연결 리스트는 단방향으로 연결된 단일 연결 리스트, 양 옆의 노드와 연결된 이중 연결 리스트, 마지막 노드가 첫 번째 노드를 가리키는 원형 연결 리스트가 있다.
스택
스택은 후입선출(LIFO)을 원칙으로 하는 선형 자료 구조다. 프링글스 통에서 맨 위의 과자부터 꺼내 먹는 것과 비슷하다. 파이썬에서는 스택 자료 구조를 따로 제공하지 않지만 리스트나 연결 리스트로 구현할 수 있다.
큐
큐는 선입선출(FIFO)을 원칙으로 하는 선형 자료 구조다. 우리가 놀이공원에서 줄을 설 때 먼저 선 사람이 먼저 놀이기구를 이용하는 것과 비슷하다. 파이썬에서는 queue 라이브러리를 이용해 큐를 구현할 수 있다.
해시 테이블
key와 value로 구성된 자료 구조며, 키를 해시 함수에 넣을 때 나오는 고유한 값을 인덱스로 사용한다.
참고 및 출처
파이썬 알고리즘 인터뷰 책