1. 정적 배열
- 크기가 고정되어 있으며, 선언 시 크기를 지정해야 함.
- 크기 변경이 불가능함. 크기를 늘리려면 새로운 배열을 만들어 재할당해야함.
- 메모리에 연속된 공간을 할당받음.
- C언어 : 그냥 `int arr[10];` 같은 기본적인 배열이 정적 배열임.
- C++ : C언어와 마찬가지, `std::array<T, N>`도 있음.
- 자바 : 그냥 `int[] arr = new int[10];` 같은 기본적인 배열이 정적 배열임.
- 파이썬 : `array.array`와 `np.array`이 정적 배열임.
2. 동적 배열
- 크기가 `doubling`을 통해 자동으로 늘어남.
- 초기에는 작은 크기로 시작해, 크기가 부족하면 지정된 `Growth Factor`대로 더 큰 크기의 배열을 할당한 후, 기존 배열의 데이터를 복사해주게됨.
- 메모리에 연속된 공간을 할당받음.
- C언어 : 제공되지 않음, `malloc()`와 `realloc()`을 사용해 직접 구현해야함.
- C++ : `std::vector<T>`가 동적 배열임.
- 자바 : `ArrayList<E>`가 동적 배열임.
- 파이썬 : 기본적인 `list`가 동적 배열임.
3. 연결 리스트
- 노드(Node)들이 포인터로 연결된 구조.
- 동적으로 메모리를 할당하여 계속 확장해나가는 구조이기 때문에, 크기 제한이 따로 없음.
- 메모리에 연속된 공간을 할당받지 않음.
- C언어 : 제공되지 않음, 직접 구조체를 써서 구현해야함.
- C++ : `std::list<T>`가 이중 연결 리스트로 구현됨.
- 자바 : `LinkedList<E>`가 이중 연결 리스트로 구현됨.
- 파이썬 : 제공되지 않음, 클래스(ex. Node)를 직접 만들어 구현해야 함.
대신, `collections.deque`를 사용하면 연결 리스트와 유사한 기능을 제공함.(추가 공부 필요)
- 단일 연결 리스트, 이중 연결 리스트, 원형 연결 리스트 등 다양한 구현 방식의 리스트가 존재함.
- 이거 복습 필요하면 자료구조 책 공부한 거 찾아보기
시간복잡도 비교
나중에 정리하기.
파이썬 list의 주요 연산들 시간복잡도
| len(a) | O(1) | 전체 요소의 개수를 리턴한다. |
| a[i] | O(1) | 인덱스 i의 요소를 가져온다. |
| a[i:j] | O(k) | 인덱스 i부터 j-1까지 슬라이스의 길이만큼인 k개의 요소를 가져온다. 이 경우 객체 k개에 대한 조회가 필요하므로 O(k)이다. |
| elem in a | O(n) | elem 요소가 존재하는지 확인한다. 처음부터 순차 탐색하므로 n만큼 시간이 소요된다. |
| a.count(elem) | O(n) | elem 요소의 개수를 리턴한다. |
| a.index(elem) | O(n) | elem 요소의 인덱스를 리턴한다. |
| a.append(elem) | O(1) | 리스트 마지막에 elem 요소를 추가한다. |
| a.pop() | O(1) | 리스트 마지막 요소를 추출한다. 스택의 연산이다. |
| a.pop(0) | O(n) | 리스트 첫번째 요소를 추출한다. 큐의 연산이다. 이 경우 전체 복사가 필요하므로 O(n)이다. 큐의 연산을 주로 사용한다면 리스트보다는 O(1)에 가능한 데크(deque)를 권장한다. |
| del a[i] | O(n) | i에 따라 다르다. 최악의 경우 O(n)이다. |
| a.sort() | O(NlogN) | 정렬한다. 팀소트(Timsort)를 사용하며, 최선의 경우 O(n)에도 실행될 수 있다. |
| min(a), max(a) | O(n) | 최솟값/최댓값을 계산하기 위해서는 전체를 선형 탐색해야 한다. |
| a.reverse() | O(n) | 뒤집는다. 리스트는 입력 순서가 유지되므로 뒤집게 되면 입력 순서가 반대로 된다. |
표 출처 : 파이썬 알고리즘 인터뷰
Ref.
- GPT
- 파이썬 알고리즘 인터뷰
'Programming > Practical Algorithms' 카테고리의 다른 글
| [알고리즘] 안정 정렬 vs 불안정 정렬 (Stable Sort vs Unstable Sort) (0) | 2025.01.30 |
|---|