[알고리즘][배열] - 1. 배열(Array)이란?

 

📖이 포스팅은 '파이썬 알고리즘 인터뷰 - 박상길님'을 보고 작성되었습니다.

---

[배열이란?]

배열이란 값 또는 변수 엘리먼트의 집합으로 구성된 구조로, 하나 이상의 인덱스 또는 키로 식별된다.

 

 

[자료구조를 나누는 방식 2가지]

자료구조를 나누는 방식은 크게 두가지로 나뉜다.

• 메모리 공간 기반의 연속(Contiguous)
• 포인터 기반의 연결(Link)

 

이때 배열은 연속 방식의 가장 기본이 되는 자료형이다.

 

 

[C언어와 배열]

C언어에서 배열은 크기를 지정하고 해당 크기만큼의 연속된 메모리 공간을 할당받는 작업을 수행하는 자료형을 말한다. 

• 크기가 조정되어 있어, 한번 생성한 배열은 크기를 변경하는 것이 불가능하다.
• int arr[5] = {4,7,29,0,1};
• 물리 메모리(= 실제 메모리)에는 이 배열의 요소의 값 4,7,29,0,1이 순서대로 배치된다.

 

 

[동적 배열의 등장]

[동적 배열이란?]

앞서서 살펴보았듯 배열이 고정된 크기만큼 연속된 메모리 할당이라고 설명했다. 그러나 실제 데이터에서는 전체 크기를 가늠하기 힘들 때가 많다. 때로는 너무 작은 영역을 할당하여 모자라거나, 또는 너무 많은 영역을 할당하여 메모리 낭비를 할 때도 있다. 이때 이러한 고민을 해결하고자 미리 크기를 지정하지 않고 자동으로 조정할 수 있게 한 것이 동적 배열이다.

 

대부분의 언어는 동적 배열을 지원한다. 

 

[각 언어별 동적 배열 형태]

자바	C++	파이썬
- ArrayList - 1.5배로 재할당 해준다.	- std::vector - 2배씩 재할당 해준다.	- List (이때 파이썬은 정적 배열은 지원하지 않고 list라고 하면 모두 동적 배열에 해당한다.) - 1.125배로 재할당 해준다.

 

[동적 배열의 원리]

동적 배열의 원리는 간단하다. 

• 미리 초깃값을 작게 잡아 배열을 생성한 뒤,
• 데이터가 추가 되면서 꽉 채워지면 늘려준 뒤,
• 모두 복사해준다. 
• 대게는 더블링(Doubling)이라고 하여 2배씩 늘려주는데, 모든 언어가 이와 같은 것은 아니다.(각 언어마다 늘리는 비율은 상이하다.)