동적배열 왜 반드시 알아야하는가

이전 알고리즘을 반드시 알아야하는 이유에 대해 짧에 글을 남겨봤습니다

오늘은 실제로 동적배열을 구현해보는 글을 써보려합니다.

 

우리가 동적배열을 알고리즘에서 필수로 알아야하는이유

가변 배열은 자료구조 중에서도 가장 기본적이면서도 강력한 구조 중 하나입니다. 알고리즘은 데이터를 효과적으로 저장하고 관리하는 데에 핵심이기 때문에, 가변 배열은 이를 위한 기본 요소로 자주 사용됩니다.

이번글을 모두 읽으신다면 여러분은 배열 가변배열 리스트중 무엇을 기능에 맞게 사용해야하는지 선택하실수있습니다.

 

동적배열이란?

동적 배열은 크기를 동적으로 조절할 수 있는 배열로, 프로그램 실행 중에 메모리 공간을 유연하게 할당 및 해제할 수 있는 자료구조입니다. 주로 동적 배열은 배열의 기본적인 특성을 가지면서도, 크기 조절이 필요한 상황에서 효율적으로 사용됩니다. 아래는 동적 배열에 대한 설명입니다

 

연결리스트와 일반 배열의 차이

 

우선 기본적인 배열,동적배열 과 연결리스트의 중요한 차이에 대해 이해하고 실습을 이어가보겠습니다

위 표는 배열과 연결리스트의 차이점들을 정리해둔 표입니다.
우리가 앞으로 실습하게될 동적배열과 링크드 리스트를 구현하기 앞서 위에 정리된 표를 반드시 이해고있어야만 합니다.

• 크기
  배열(Array)의 경우 선언 당시에 일련된 메모리주소를 순차적으로 선언합니다
  한번 선언된 배열의 메모리 크기는 프로그램 실행 도중에 수정 할수 없기에 고정적입니다.
  하지만 주의하셔야할 점은
  동적 배열의 경우에는 메모리의 주소는 순자척으로 나열된 상태로 데이터를 추가로
  받을수있기에 크기가 정적이지 않습니다.
  
• 주소 
  매우 중요한 차이점입니다 위 차이점을 좀더 이해하기 위해 그림판으로
  예제를 하나 그려봤습니다.
  

배열의 메모리 주소

배열 또는 동적 배열

위 표는 배열의 선언을 예시로 메모리의 상태를 그림으로 표현한것입니다.
흰색의 상자들은 메모리이자, 주소입니다
아파트로 예시를 들자면 각각의 방(memory)은 사람(data)이 살기위해 존재합니다.
방은 101호 ,102호로 불리는 주소(memory address)를 가지고있습니다.

위 그림은 1,2,3,5의 데이터가 순차적으로 메모리를 할당받고 데이터를 저장한 상태입니다.

int[] arr = new int[] {1,2,3,5};

vector v;
v.push_back(1);
v.push_back(2);
v.push_back(3);
v.push_back(5);

동적 배열의 경우에는 약간의 차이가 존재하지만
위 그림과 같이 할당된 메모리의 주소가 순차적이란 사실은 배열과 같습니다.

 

배열 또는 동적 배열의 경우 메모리를 할당하고 초기화를 받게되면
그 메모리의 주소는 위 표에 정리된 내용과 같이 순차적으로 받게 되어있습니다.

이는 곧바로 접근속도와도 연관되는 차이입니다 메모리의 주소가 일정하니 알고싶은 요소값의
인덱스만 알면 어디서든 데이터를 찾을수 있기에 상대적으로 리스트보다 빠른 접근속도를 가지게됩니다.

리스트의 메모리 주소

링크드 리스트의 주소

 

위 그림은 반대로 링크드 리스트의 메모리 할당시 데이터들의 주소를 표현한것입니다.
배열과 상대적으로 메모리의 주소가 순차적이지 않고 랜덤으로 선언되어있는것을 보실수있습니다.

위 그림은 1,2,3,5의 데이터가 랜덤으로 메모리를 할당받고 데이터를 저장한 상태입니다.

list<int> numbers = new list{1,2,3,5};

lint<int> numbers2 = new list();
numbers.push_back(1);
numbers.push_back(2);
numbers.push_back(3);
numbers.push_back(5);

 

랜덤의 메모리에 할당 받게된 데이터들은 어디에 저장되어있는지 개발자들은 알수가 없습니다
따라서 링크드 리스트에 자체적으로 데이터를 접근할수있는 탐색로직을 가지고 있고
이는 배열보다는 상대적으로 느린 접근 방식을 가지게됩니다.
링크드 리스트의 내부 로직은 다음 글로 정리하겠습니다.

---

 

인테넷에서도 위 배열과 링크드 리스트의 차이를 검색하면 위 차이에 대해서 정말 쉽게 찾아볼수있고

구현의 차이가 명백히 다르기 때문에 장단점을 이해하기도 쉽습니다.

하지만, 이중에서 배열(Array)과 동적배열(Dynamic Array)의 차이는 무엇인지 모르는경우가 많습니다.

 

배열은 할당받는 주소가 일정하고 가변배열 또한 일정합니다.

심지어 배열은 단한번의 초기화만으로 크기를 지정받지만 벡터는 동적으로 크기를 늘릴수가있습니다

이 점들만으로 보면 그저 벡터는 배열의 상위호환이고 배열은 절때 사용할 일이 없는 자료구조일까요?

벡터의 장점들만을 생각하고 단점을 모른다면 여러분은 실무개발에서 큰 메모리 낭비를 하게되실수있습니다.

 

우리는 이러한 단점을 이해하기위해 C++에서 대표적으로 자주사용하는 자료구조형인

Vector함수를 예시로 구현과 설명을 하겠습니다.

벡터의  특징

배열의 내부 구조는 동적배열이란 이름의 뜻으로 무슨 구조를 가지고있는지 유추가 가능합니다

단순히 push_back을 호출할 시 배열을 동적으로 새로 할당하는것입니다.

대충 러프하게 Puch_back의 내부를 상상해서 구현해봅시다.

 

예시)

A라는 벡터에 1,2,3,4,5 라는 요소값을 가지고있습니다.

우리는 push_back 함수를 호출하여 6이란 값을 요소로 추가할것입니다.

1. 새로운 배열 동적할당 및 추가 요소값 초기화

 

2. 내부 요소값을 깊은복사로 다시 씁니다.

3. Vecotr A 재정의

완성된 배열을 다시 벡터 A로 재정의 하여 끝납니다

 

이러면 끝이지만 너무 비효율적입니다 매번 값을 추가할때마다 메모리를 새로 할당받는다고??

이러한 비효율적인 단점을 보안하기위해 배열과 가장 큰 차이점이 존재합니다.

 

벡터와 배열의 가장 큰 차이점은 capacity(용량)의 존재 여부입니다.

배열은 용량이 존재하지않고 벡터는 용량이 존재합니다 이 사실 하나만을 기억하신다면 여러분은 이후 갑작스럽게

백터를 구현해야하는 상황속에서 capacity란 단어 하나만을 기억하시면 손쉽게 구현할수있습니다.

 

벡터의 Capacity란?

동적 배열이란 이름을 가진 벡터는 말 그대로 동적으로 배열을 할당해줍니다.

하지만, 매번 push_back을 호출할때 마다 동적으로 배열을 새로 만들어야한다면

그 연산량과 속도는 매우 비효율적일겁니다 따라 벡터는 이러한 비효율적인 부분을 개선하고자

배열의 사이즈 크기보다 더 큰 사이즈를 미리 확보하는역할을합니다.

이 추가될 요소값을 염두하고 미리 확보한 전체 사이즈를 Capacity라 부릅니다

이 Capacity를 더 쉽게 이해하기 위해 예제 테스트 코드를 실습해보겠습니다

 

Capacity 예제코드

#include<iostream>
#include<vector>
using namespace std;


int main()
{

    vector<int> v;

    for(int i =0; i < 100; i++)
    {
        v.push_back(i);
        cout << "기존 라이브러리 벡터" << v[i] << " 기존 벡터 용량" << v.capacity() << endl;
    }
    
    return 0;
}

 

위 코드는 설명할게 딱히 없습니다 0~99의 값을 벡터에 추가하고

추가하는 즉시 벡터의 요소값과 벡터의 전체 용량을 호출하는 코드입니다.

벡터의 용량은 배열의 전체 사이즈보다 40%가량을 미리 사이즈를 확보하게 되어있습니다.

그럼 출력을 보겠습니다.

 

우리가 여기서 확인해야할것은 용량이 처음에는 배열의 Size과 큰 차이가 없는것을 볼수있습니다.

하지만 배열의 Size가 커질수록 Capacity도 보다 많은량을 차지하는것을 볼수있습니다.

이러한 특징이 벡터만이 가진 큰 특징이자 단점입니다 100개의 요소정도면 큰 문제가 되지않겠지만

1000개 10000만개의 데이터를 백터로 관리하게되면 그만큼을 동적으로 만들어내는 연산량, 불필요하게 미리 확보하는 사이즈

동적으로 만들어진 새 배열에 이전 배열 요소값을 Call by Value로 대입해야하는 등의 불필요한 일들이 속에서 벌어집니다

결국 많은 데이터를 동적으로 추가하는 자료구조를 사용할경우 백터는 쓰레기가 될것입니다.

 

위 글을 통해서 우리는 배열과 가변배열의 차이점을 알게되었습니다

각각의 차이점들을 정리해보겠습니다.

1. Capacity의 존재여부

2. 요소값이 많고 동적으로 추가해야하는 상황이 많으면 가변배열의 사용은 비효율적이고 피해야한다

3. 미리확보하는 Capacity량는 배열 전체 Size보다 40%를 더 차지한다.

 

위 글을 이해한 상태라면 무슨 블랙매직을 써서라도 우리는 동적배열 구현이 가능해집니다.

template<typename T>
class Vector
{

//생성자 오버로딩
public:
    Vector(/* args */)
    {
        size = 0;
        capacity = 0;
        data = nullptr;
    }

    ~Vector()
    {
        delete[] data;
    }

private:

//멤버 변수
public:
    int capacity;
    int size;
    T* data;
public: 
//멤버 함수
T Get(int index)
{
   return data[index];
}

//추가할 값을 배열에 집어 넣는다.
void push_back(const T& value)
{
    if(capacity > size)
    {
        data[size] = value;
        size++;
        return;
    }

    ResizeCapacity(value);   
}

void ResizeCapacity(const T& value)
{
    capacity = (int)((size) * 1.5f);
    T* newArray = new T[capacity];

    for(int i =0 ; i < size; i++)
    {
       newArray[i] = data[i];
    }
    newArray[size] = value;
    data = newArray;
    size++;
}
};

int main()
{

    vector<int> v;

    for(int i =0; i < 100; i++)
    {
        v.push_back(i);
        cout << "내 벡터" << v[i] << " 기존 벡터 용량" << v.capacity() << endl;
    }
    
    return 0;
}

 

코드가 매우 쉬워서 설명드릴 부분이 크게 없지만  템플릿과 Call by value , Call by reference의 이해가 없으시다면

ResizeCapacity을 여러차례 확인해보시는것을 추천드립니다.

 

저의 경우 c#에 익숙해져있어 오랜만에 사용해보는 C++의 포인터가 어색하여 조금 해매면서 만들었습니다. 

 

위 직접 제가 구현한 벡터는 여러분이 더욱 이해하기 쉬운 코드로 작성했습니다.

특히 Get의 경우 연산자 오버로딩 []을 이용하면 진짜 벡터와 똑같이 구현하실수있습니다.

 

만약 여러분이 지금까지의 설명은 이해를 했지만 위 코드는 이해가 안가신다면

직접 고민하시며 직접 벡터를 구현해보시는것을 추천드립니다. 충분히 구현하실수 있을거라 생각합니다.

 

참고로 저의 경우 쉬운 코드를 보여드리기 위해 명시적 캐스팅을 하여 실수값을 정수로 바꿧지만

위 코드보다 static_cast 를 사용하시는것을 권장드립니다

 

오는은 아주 쉬우면서도 중요한 동적배열 c++백터를 이해하고 코드를 짜보는 시간을 가졌습니다

예제는 언제든지 볼수있으니 여러분도 꼭 이해한것을 백지에서 직접 짜보시는것을 추천드립니다.

코드에 오류가 존재한다면 댓글 부탁드립니다 글 읽어주셔서 감사합니다.