🤎 배열의 크기 조정
배열의 크기를 키우려면 어떻게 해야 할까?
배열의 크기가 3이고, 이 크기를 4로 하고 싶다면 단순히 생각하면 크기가 3인 배열 바로 옆에 한 바이트의 공간만 더 붙이면 된다. 실제로도 이런 방식으로 배열의 크기를 조정할 수 있을까?
실제로는 키우려는 배열 메모리 주위에는 다른 메모리들로 둘러 쌓여있을 확률이 높다. 기존에 사용하고 있던 메모리 뒤에는 다른 데이터들이 담겨 있을 수 있는데 이 상태에서 데이터를 메모리를 새로 할당하지 않고 메모리 크기를 키운다면 뒤에 있던 메모리에 데이터를 덮어쓰는 일이 발생할 수 있다.
따라서 안전하게 새로운 공간에 큰 크기의 메모리를 다시 할당하고 기존 배열의 값들을 하나씩 옮겨줘야 한다. 이런 작업은 배열의 크기 n 만큼 실행 시간이 걸리므로 시간 복잡도는 O(n)이다.
🤎 자료구조적인 측면에서 어떤 대안이 있을까?
배열이란 같은 종류의 데이터들 일렬로 저장하는 자료구조이다.
배열에 저장된 각 데이터들은 번호(index)를 가지고 있다.
하지만 이러한 배열만으로는 비효율적이거나 한계가 있는 작업이 있기 때문에 동적배열이나 연결 리스트 등과 같은 자료 구조를 만들어 사용한다. (동적배열이든 연결 리스트든 모두 기본적으로 배열을 이용하여 만들어낸 자료구조이다.)
🙋🏻♀️ 자료구조란?
자료구조란 여러 데이터들의 묶음을 저장하고, 사용하는 방법을 정의한 것이다.
❗️자료구조를 배우는 이유
- 데이터를 체계적으로 저장하고, 효율적으로 활용하기 위해서 자료구조를 사용한다.
- 대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는 데에 특화되어 있다.
- 많은 자료구조를 알아두면, 특정 문제를 해결하는 데에 상황에 가장 적합한 자료구조를 빠르게 찾아 데이터를 정리하고 활용하여 문제를 빠르고 정확하게 해결할 수 있다.이것은 문제 해결 능력을 필요로하는 알고리즘과 굉장히 밀접한 연관성이 있다. 결국 문제해결을 하기 위해서 배운다.
동적배열(Dynamic Array) 이란?
동적 배열이란 크기가 고정되지 않은 배열을 의미한다.
보통 우리가 흔히 말하는 배열은 동적(Dynamic)의 반대인 정적(Static)배열을 의미한다. 정적배열은 크기가 고정되어 있어 데이터를 크기 만큼만 저장할 수 있다.
대표적으로 C++ 의 vector 나 자바의의 ArrayList 등이 있다.
초기에 고정된 크기를 할당받으며 생성되고, 초기에 지정한 크기를 넘어서면 동적으로 크기를 늘린
다는 특징을 가지고 있다.
동적 배열은 다음과 같은 과정으로 동작한다.
- 처음 동적 배열이 생성될 때, 일정한 Capacity를 갖고 할당된다.
- 할당된 Capacity를 넘어서 원소가 추가되면, 기존 Capacity의 2배 크기로 배열을 새로 할당한 후, 기존 배열의 원소를 복사한다.
- 동적 배열을 구현하는 클래스는 할당된 배열을 가리키는 참조변수, Capacity 변수, Size 변수 세 가지 필드가 필요하다.
동적배열이 필요한 이유
동적배열은 이름에서 나타나듯이 배열의 크기를 동적으로 늘려서 사용하고 싶을 때 필요하다.
배열은 크기가 고정해야 되기 때문에 이를 해결하기 위해 동적배열이 고안된 것이다.
처음부터 자신이 사용할 배열의 크기를 알면 좋겠지만 크기를 너무 크게 잡으면 메모리가 낭비되고, 그렇다고 크기를 작게 잡으면 매번 배열을 새로 만들어서 기존의 배열을 옮겨 담아야 해서 번거롭다.
