배열 (Array)

사용자 Mgmix

·

2021. 7. 20. 22:23

배열은 값 또는 변수 요소의 집합으로 구성된 구조로, 하나 이상의 Index 또는 Key 로 식별 된다.

자료구조

일반적으로 연속 방식과, 연결 방식이 존재한다.

  • 메모리 공간 기반의 연속(Contiguous) 방식 (대표적으로 Array)
  • 포인터 기반의 연결(Link) 방식 (대표적으로 Linked List)

 

배열은 어느 위치에나 O(1) 에 조회가 가능하다!

 

 

O(1)인 이유

0x00에서 시작하는 int 배열에서 4번째 값에 접근하고자 하는 경우, int 배열 이므로 각각 4바이트로 계산한다.
메모리 크기에서 4*3 = 12 의 값인 0x0C 가 4번째 값의 시작점이 되고 이렇게 주소를 찾으면 메모리에 적재된 값을 바로 읽어 올 수 있다.

 

배열의 개수에 관계없이 주소를 즉시 계산 가능하기 때문에 O(1) 이다.

 

 

배열의 문제점

 

배열은 고정된 크기의 연속된 메모리 할당이다.

 

하지만 실제 데이터는 전체 크기가 고정시키기 어려울 경우가 많다.  너무 작게 영역을 할당하여 모자라거나, 너무 많이 할당하여 낭비되거나 하는 경우가 발생한다. 이럴 때 미리 크기를 지정해 놓지 않고, 자동으로 조정할 수 있는 동적 배열이 등장한다.  자바에서는 ArrayList, C++ 에서는 std::vector 가 대표적인 동적 배열 자료형이다.

 

 

동적 배열의 원리

 

미리 초깃값을 작게 잡아 배열을 생성하고, 데이터가 추가되면서 꽉 채워지면 늘려주고 모두 복사하는 방식으로 동작한다. 일반적으로 더블링(Doubling) 이라 하여 두 배씩 늘려주는데, 이는 언어마다 늘려가는 비율이 다르다.

이러한 재할당 비율을 그로스 팩터(Growth Factor) 라고 한다.

동적 배열은 정적 배열과 달리 크기를 지정할 필요가 없어 편리하게 활용할 수 있으며, 조회 또한 기존의 배열과 동일하게 O(1) 에 가능하다.  더블링이 필요할 만큼 공간이 차게 되면, 새로운 메모리 공간에 더 큰 크기의 배열을 할당하고 기존 데이터를 복사하는 작업이 필요하기에 O(n) 의 비용이 발생한다.

최악의 경우에는 삽입 시 O(n) 이 될 수 있으나, 분할 상환 분석에 따른 입력 시간은 O(1) 이다.

 

 

참고 자료

- http://www.jbiet.edu.in/coursefiles/cse/HO/cse1/DS1.pdf

- 파이썬 알고리즘 인터뷰

 

'Computer Science > 자료구조' 카테고리의 다른 글

배열 (Array)  (0) 2021.07.20

0개의 댓글