이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다.
출처 : https://www.onlybook.co.kr/entry/algorithm-interview
7장 배열
- 정의
- 값 또는 변수 엘리먼트의 집합으로 구성된 구조
- 하나 이상의 인덱스 또는 키로 식별
- 연속 방식
- 자료구조는 연속 방식과 포인터 기반 연결 방식으로 나뉨
- 배열은 연속 방식
- 요소의 주소가 연속적인 값으로 연결된 형태
- 추상 자료형 (ADT)의 실제 구현은 대부분 배열 또는 연결 리스트를 기반
- ex) 스택을 연결 리스트로 구현, 큐를 배열로 구현
- C언어 기준의 배열
- 크기를 지정하고, 해당 크기만큼 연속된 메모리 공간을 할당 받는 자료형
- 생성 후 크기를 변경할 수 없음 (크기 고정)
- 어느 위치나 O(1)에 조회가 가능하다는 장점
- 동적 배열
- 전체 데이터 크기를 미리 가늠하기 어려움
- 크기를 지정하지 않고 자동 resizing하는 배열이 동적 배열
- 자바는 ArrayList, C++은 std::vector, Python은 list
- 동적 배열의 원리
- 초기값을 작게 잡아 배열 생성
- 데이터가 추가되면서 꽉 차면 크기를 늘린 배열에 복사
- 더블링(Doubling)
- 크기가 보통 2배씩 증가
- 그로스 팩터(Growth Factor)
- 파이썬은 평균 1.125배, 자바는 1.5배, C++은 2배