[자료구조/알고리즘] - 배열/array

자료구조는 크게 메모리 공간 기반의 연속 방식과 포인터 기반의 연결 방식으로 나뉘게 되고, 배열은 대표적인 연속 방식의 자료형이다. 연결 방식의 대표적인 자료형은 연결리스트를 생각하면 된다. 

C언어를 기준으로, 배열은 크기를 지정하고 해당 크기 만큼의 연속된 메모리 공간을 할당 하는 자료형이라고 보면 된다. 이렇게 크기를 정하고 생성한 배열은 크기를 변경하는 것이 불가능 하다 

예를 들어서 int arr[5] = {4, 7, , 29, 0, 1}로 배열을 선언해주게 되면 정수형 int로 선언을 해주고 총 5칸을 배정해줬다고 보면 된다. 

배열의 장점은 어느 위치에나 O(1)로 조회가 가능하다는 점. 주소를 기준으로 해당 메모리에 배치되어 있는 값을 바로 조회가 가능하다. 

위에서 얘기하는 배열의 경우에는 고정된 크기 + 크기를 늘리는 것에 이슈가 있기 때문에 "미리 크기를 지정하지 않고 자동으로 조정하면 어떨까"라는 생각을 기반으로 동적 배열이 나오게 되었다. 

동적배열에는 ArrayList(JAVA), std::vector(C++), 리스트(파이썬) 등이 대표적으로 있다. 동적 배열의 원리는 간단하게 정리하면, 초깃값을 작게 잡아서 배열을 생성하고, 데이터가 추가되면 늘려주고 복사하는 방식으로, 일반적으로 더블링이라고 해서 2배씩 늘려주는 방식을 쓰곤 한다. 

파이썬의 경우에는 CPython 내부를 보게 되면 아래와 같이 적혀있는 것을 볼 수 있다. 

 * The growth pattern is:  0, 4, 8, 16, 24, 32, 40, 52, 64, 76, ...
     * Note: new_allocated won't overflow because the largest possible value
     *       is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
     */
    new_allocated = ((size_t)newsize + (newsize >> 3) + 6) & ~(size_t)3;

이전에 파이썬에서 리스트를 사용할 때는 그냥 동적 배열이구나 로만 알고 따로 코드를 열어보거나 하진 않았는데 막상 열어보니, 쭉 더블링이 아니라 초반에는 더블링을 해주다가 어느시점 부터 1.125배를 해주는 것을 알 수 있다. 이 할당 비율을 성장 인자(Growth Vector)라고 부른다. 위에서 얘기했듯이 단순 조회는 동일하게 O(1)의 시간이 소요 되지만 추가 공간이 필요해지면, 새로운 메모리 공간에 더 큰 크기의 배열을 할당해주고, 기존 데이터를 복사해주는 것이 필요하기 때문에 O(n)의 시간이 소요되게 된다. 

[참고자료]

참고 서적 : 파이썬 알고리즘 인터뷰

파이썬 알고리즘 인터뷰

https://github.com/python/cpython/blob/main/Objects/listobject.c

GitHub - python/cpython: The Python programming language