동적 배열
첫 번째 인덱스 위치에 원소를 삭제하거나 삽입할 때, O(n)이 걸린다. 끝에 삽입하거나 삭제할 때는 상수시간 O(1)이 걸린다. 따라서 스택으로 사용하기 좋지만, 큐로 사용할 때는 복잡도를 고려해야 한다.
| 파이썬 | list() or [ ] |
| C++ | std::vector |
| 자바 | ArrayList |
| 자바스크립트 | Array() or [ ] |
파이썬 리스트는 연속된 공간에 원소를 배치하는 배열의 장점과 다양한 타입을 배치하는 연결 리스트의 장점을 같이 취한 형태이다. 사실상 연결 리스트에 대한 포인터 목록을 배열형태로 관리한다. 결국 포인터의 위치를 찾아가서 확인해야 하므로 속도를 희생한 측면이 있다.
대부분의 동적 프로그래밍 언어들은 정적 배열 자체가 없다.
파이썬은 초반에는 2배씩 크기를 늘려가지만, 전체적으로는 1.125배 늘린다. 자바의 ArrayList는 1.5배, C++의 vector는 2배씩 늘려나간다.
해시 테이블
리스트는 인덱스를 숫자로만 지정할 수 있지만, 딕셔너리는 문자를 포함해 다양한 타입을 키로 사용할 수 있다. 입력과 조회 모두 O(1)에 가능하다. 물론 최악의 경우 O(n)이 될 수 있으나 분할 상환 분석에 따른 시간 복잡도는 O(1)이며 대부분 빠르게 실행된다.
보통 입력 순서가 유지되지 않는다.
파이썬은 collections.OrderedDict()가 있으며, 파이썬 3.7부터는 그냥 dict()에서도 입력 순서가 유지된다. collections.defaultdict()는 조회시 디폴트 값을 생성해 키 오류를 방지한다. collections.Counter()는 요소의 값을 키로 하고 개수를 값 형태로 만들어 카운팅한다.
각 언어별 해시 테이블을 이용한 자료형은 아래와 같다.
| 파이썬 | dict() or { key: value } |
| C++ | std::unordered_map |
| 자바 | HashMap |
| 자바스크립트 |
댓글