Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬(Python) 동적 배열 구현하기 – 원리부터 코드 예제까지

동적 배열(Dynamic Array)이란?

파이썬에서 리스트(list), 셋(set), 딕셔너리(dictionary)는 가변(mutable) 객체입니다. 반면 숫자(number), 문자열(string), 튜플(tuple)은 불변(immutable) 객체입니다. 가변 객체란 생성된 이후에도 요소를 자유롭게 추가하거나 삭제할 수 있는 객체를 의미하며, 튜플이나 문자열처럼 한 번 생성되면 내용을 변경할 수 없는 객체를 불변 객체라고 부릅니다.

파이썬에서 리스트는 대표적인 동적 배열(dynamic array)입니다. 실제로 빈 리스트를 만든 뒤 요소를 추가하고 삭제하면서 크기가 유동적으로 변하는 것을 확인할 수 있습니다.

먼저 빈 리스트를 생성해 보겠습니다.

>>> # 빈 리스트 생성
>>> list1 = []
>>> type(list1)
<class 'list'>

이제 생성한 빈 리스트에 요소를 추가해 보겠습니다.

>>> # 요소 추가
>>> list1 = [2, 4, 6]
>>> list1
[2, 4, 6]
>>> # append() 메서드로 요소 추가
>>> list1.append('Tutorialspoint')
>>> list1
[2, 4, 6, 'Tutorialspoint']

다음은 리스트에서 요소를 삭제하는 예제입니다.

>>> # 리스트에서 요소 삭제
>>> list1.pop()
'Tutorialspoint'
>>> list1
[2, 4, 6]

위 예제에서 확인할 수 있듯이 리스트는 사실상 배열의 확장형으로, 크기를 자유롭게 늘리거나 줄일 수 있습니다. 크기가 "0"인 상태에서 시작해 요소를 계속 추가하면서 리스트의 크기가 자동으로 조정되는 것을 볼 수 있습니다.

동적 배열 구현의 기본 원리

배열이 가득 찬 상태에서 새로운 요소를 추가(append)해야 하는 상황을 생각해 봅시다. 고정 크기 배열이라면 더 이상 요소를 담을 수 없지만, 동적 배열은 다음과 같은 절차를 통해 크기 제한 문제를 해결합니다.

  • 더 큰 용량(capacity)을 가진 새로운 배열 list2를 할당합니다.
  • i = 0, 1, …, n-1에 대해 list2[i] = list1[i]로 기존 요소를 복사합니다. (n은 현재 저장된 요소의 개수)
  • list1 = list2로 참조를 변경하여 새 배열을 사용합니다.
  • 마지막으로 새로운 요소를 list1에 삽입(append)합니다.

이제 파이썬으로 동적 배열 개념을 직접 구현하는 코드를 만들어 보겠습니다. 파이썬 내장 라이브러리인 ctypes 모듈을 활용하면 C 언어 수준의 로우(raw) 배열을 다룰 수 있으며, 이를 바탕으로 우리만의 동적 배열 클래스를 작성할 수 있습니다.

동적 배열 클래스 구현 – dynamicArray.py

import ctypes

class DynamicArray(object):
    # 초기화
    def __init__(self):
        # 세 가지 속성을 가집니다
        self.n = 0                       # 현재 요소 개수 (기본값)
        self.capacity = 1               # 배열 용량 (기본값)
        self.A = self.make_array(self.capacity)  # make_array는 아래에서 정의

    # 길이 반환 메서드
    def __len__(self):
        # 배열에 저장된 요소의 개수를 반환
        return self.n

    def __getitem__(self, k):
        # 인덱스 k에 해당하는 요소 반환
        if not 0 <= k < self.n:
            return IndexError('k is out of bounds')
        return self.A[k]

    def append(self, element):
        # 용량 확인
        if self.n == self.capacity:
            # 새 배열을 위해 용량을 두 배로 증가
            self._resize(2 * self.capacity)  # _resize는 아래에서 정의
        # 배열 A의 n번 인덱스에 요소 저장
        self.A[self.n] = element
        self.n += 1

    def _resize(self, new_cap):  # new_cap은 새로운 용량
        # 배열 B 선언
        B = self.make_array(new_cap)
        for k in range(self.n):
            B[k] = self.A[k]  # 배열 A의 요소를 B로 복사
        self.A = B            # A는 이제 배열 B를 참조
        self.capacity = new_cap  # 용량 재설정

    # ctypes를 이용한 make_array 메서드
    def make_array(self, new_cap):
        return (new_cap * ctypes.py_object)()

arr = DynamicArray()

동적 배열 클래스가 준비되었으니 실제로 사용해 보겠습니다.

>>> len(arr)
0
>>> arr.append(1)
>>> # 첫 번째 요소 입력
>>> len(arr)
1
>>> arr.append('Tutorialspoint')
>>> # 두 번째 요소 입력
>>> len(arr)
2
>>> arr[1]
'Tutorialspoint'

이것으로 끝입니다! 우리는 직접 동적 배열을 만들었고, 파이썬의 리스트처럼 필요에 따라 배열의 크기를 동적으로 조정할 수 있게 되었습니다. 이러한 원리를 이해하면 파이썬 리스트가 내부적으로 어떻게 동작하는지, 그리고 append 연산이 분할 상환(amortized) 관점에서 평균 O(1)의 시간 복잡도를 가지는 이유까지 명확하게 파악할 수 있습니다.