Data Structure: Sequential Structures 순차적 자료구조

순차적 자료구조의 종류로는 array, stack, queue, dequeue가 있다.

Array

array(배열)는 데이터를 ‘연속적인’ 메모리 공간에 저장하고, 저장된 곳의 주소(address, reference)를 통해 매우 빠른 시간에 접근 할 수 있다. 이러한 이유 때문에 다양한 용도로 가장 많이 쓰이는 기본적인 자료구조이다.

C, C++, Java, Python 등의 프로그래밍 언어에서 모두 array 자료구조를 지원한다. 이 중 Python에서는 배열은 list, tuple, srt같은 Class로 표현된다.

C 언어에서의 array

예를 들어 C 언어에서 A라는 이름의 배열을 만들어보자. 본 글에서는 C 언어 문법을 설명하는게 목적이 아니기 때문에 C 언어에서의 배열에 대한 좀 더 자세한 설명은 책 <C 언어 코딩도장> 36.1 배열을 선언하고 요소에 접근하기에서 살펴보길 바란다.

int A[4] = {2,4,0,5}; // 정수 4개를 저장할 수 있도록 연속적인 메모리 할당

만약, k번째 셀(cell)에 저장된 값을 알고 싶다면, 그 셀의 시작 주소는 아래와 같이 계산 가능하다. A 배열 k번째 셀의 시작 주소 = A 배열의 시작 주소 + k * (값이 차지하는 byte 수) 이는 배열이 연속적으로 저장되어 있기 때문이다.

이처럼 배열에서 가장 중요한 사실은 결국 아래 3가지 정보만으로 값이 저장된 곳의 주소를 알 수 있다는 점이다.

  1. 배열의 시작 주소
  2. 저장된 값의 종류 (byte 개수)
    • data type에 따라 차지하는 byte의 개수(차지하는 메모리 크기)가 다 다르다.
  3. 몇 번째에 저장되어 있는지를 나타내는 index(인덱스)

메모리 주소가 주어지면 단위 시간에 값을 읽고(읽기연산) 저장(쓰기연산)할 수 있다. 읽기연산과 쓰기연산은 $O(1)$ 시간이다.

  • 읽기연산의 예: print(A[2]) A[2]의 값을 읽는 연산
  • 쓰기연산의 예: A[2] = 8 A[2]의 메모리에 값 8을 저장하는 연산

C 언어의 배열은 읽기/쓰기 연산만 제공하는 제한된 자료구조이다.

Python에서의 array

Python의 배열은 다른 언어의 배열보다 기본적으로 여러 종류의 유용한 연산을 제공한다.

C 언어 배열의 셀에는 실제 값(데이터)이 저장된 형식이지만, Python list의 셀에는 데이터가 아닌 데이터가 저장된 곳의 주소(address 또는 reference)가 저장된다.

항상 객체의 주소만 저장하기 때문에, 메모리 내 주소를 표현할 수 있는 4 byte 또는 8 byte로 리스트 셀의 크기를 고정하면 된다. 모든 셀의 크기가 같기 때문에 인덱스에 의해 $O(1)$ 시간에 접근 가능하다.

A = [10, "apple", 7, 3.1415, 21, -45]

image

A[2] = A[2] + 2

image

B = A[1:4]

image

B[2] = 2.4

image

C = [0] * 6
C[0] = 1

image

C 언어와의 차이점 1: 강력한 배열 기본연산

파이썬의 리스트는 읽기/쓰기연산 이외에 훨씬 더 유연하고 강력한 연산을 지원한다. C 언어에서는 이러한 연산을 기본제공하지 않기 때문에 따로 함수를 만들어야한다.

  • A.append(value): 맨 오른쪽(뒤)에 새로운 값(value)를 삽입
  • A.pop(i): A[i] 값을 지운 후 return (i번째 오른쪽 값들은 왼쪽으로 한 칸씩 당겨져, 셀의 수가 하나 감소)
  • A.insert(i, value): A[i] = value 연산 (단, A[i], A[i+1], … 값들은 오른쪽으로 한 칸씩 이동해 A[i]를 비운 후 값(value)를 저장
  • A.remove(value): 값(value)을 찾아 제거 (value 오른쪽의 값들은 왼쪽으로 한 칸씩 이동해 빈 공간을 메꿈)
  • A.index(value): 값(value)이 처음으로 등장하는 index를 return
  • A.count(value): 값(value)이 몇 번 등장하는 지 횟수를 세어 return
  • A[i:j]: A[i], …, A[j-1]까지를 복사해 새로운 리스트를 생성하여 return (slicing연산)
  • value in A: 멤버십 연산자 - A에 value가 있으면 True, 없으면 False를 return

C 언어와의 차이점 2: 동적배열

Python의 리스트는 동적배열(dynamic array)이다. 다시 말해 리스트의 크기(셀의 개수)가 필요에 따라 자동으로 증가 또는 감소한다. C 언어에서의 배열은 동적 배열이 아니므로 사용자가 직접 상황에 맞게 처리해야한다.

C 언어에서는 ..

>>> int A[4] = {2,4,0,5};
>>> A[4] = 10; // 이러면 에러난다.
>>> A = (int*)malloc(6*4); // 메모리를 수동으로 추가 할당시켜야 에러가 안난다.

하지만, Python에서는 ..

>>> A = []
>>> sys.getsizeof(A)
64 # 빈 리스트도 64 byte 할당
>>> A.append("Python")
>>> sys.getsizeof(A)
96 # append 후 96 byte로 재할당

이 때문에 삽입연산인 append 또는 insert연산을 위한 공간(메모리)이 부족하면 더 큰 메모리를 할당받아 새로운 리스트를 만들고, 이전 리스트의 값을 모두 이동한다. 반대로 삭제연산인 pop연산을 하면 실제 저장된 값의 개수가 리스트 크기에 비해 충분히 작다면더 작은 크기의 리스트를 만들고 모두 이동한다.

Python의 리스트는 메모리 인심이 좋아서 메모리 낭비가 크다. 하지만, 동적배열인 덕분에 사용자는 배열의 크기를 전혀 신경쓰지 않아도 된다. => 메모리 자동관리

동적 배열인 리스트를 위해서는 Python 내부적으로 현재 리스트의 크기(capacity)와 리스트에 저장된 실제 값의 개수(n)를 항상 알고 있어야 한다. 이를 위한 내부 변수가 필요하다. 이런 추가 정보를 위한 메모리가 필요하므로 빈 리스트 A는 항상 0 byte보다 크다.

참고로 Python의 리스트는 실제로 Class 형태이다. 즉, 리스트를 선언하면 list라는 자료구조 클래스를 호출하는 셈이다.

추가 메모리뿐만 아니라 연산시간도 문제가 생긴다. 특정 append 연산에서 메모리를 늘려야 한다면 아래와 같이 이전 리스트의 값을 새로운 리스트로 일일이 이동해야 한다.

capacity가 용량(슬롯의 개수)이고 n가 현재 리스트에 저장된 값의 개수라고 하자. 디폴트값이 capacity=1이고, n=0이다.

def append(A,value):
  if A.capacity == A.n: # 1단계: resize 필요(capacity만큼 용량이 다 차있다는 뜻)
    allocate a new list B with larger memory and update B.capacity and B.n

    for i in range(A.n): # A에 있는 값들을 B로 옮기기. 이 부분의 이사비용이 크다. 이사비용이 O(n)만큼 소요.
      B[i] = A
    dispose A
    A = B # 기존 A를 늘린 꼴인 B를 A라고 이름을 바꿔준다.

  A[n] = value # 2단계: 사이즈가 커졌으므로 A[n]에 값을 저장

  A.n += 1 # 3단계: A.n의 정보를 n+1로 업데이트

1단계의 for문에서 A에 저장된 값의 개수만큼, 즉 n만큼의 시간이 걸린다. $O(n)$ 결론적으로 append연산은 resize가 일어나면 $O(n)$, 일어나지 않으면 $O(1)$ 시간이 걸린다.

하지만, resize가 append할 때마다 발생하는 것이 아니라 가끔 발생(크기가 $2^1, 2^2, 2^3 \cdots$일 때만 발생)하기 때문에 평균시간을 계산해보면 $O(n)$보다는 훨씬 작다.

크기를 2배씩 증가하거나 절반으로 감소하는 경우 append, pop연산 시간은 평균적으로 $O(1)$임을 증명할 수 있다. (hash table 자료구조에서 자세히 언급)

배열의 여러 연산 수행시간

  • A[i] = A[j] + 1
    • A[j]값을 읽은 후 (단위시간) 1을 더하고 (단위시간) A[i]에 쓴다(단위시간)
    • 읽기/쓰기는 $O(1)$ 시간
  • A.append(5)
    • 맨 오른쪽(뒤)에 새로운 값(value)를 삽입
    • 평균적으로 $O(1)$ 시간
    • 최악의 경우 $O(n)$ 시간
      • why? 들어가 있는 데이터에 따라 $2^k%만큼 사이즈가 커지기 때문이다.
  • A.pop()
    • 맨 오른쪽 값을 삭제 후 리턴
    • 평균적으로 $O(1)$ 시간
  • A.pop(3)
    • A[4], …, A[len(A)-1] 값이 모두 왼쪽으로 한 칸씩 이동하는 시간 필요
    • 최악의 경우 A.pop(0)일 때 $O(len(A))$ 시간
  • A.insert(0, 10)
    • A[0], …, A[len(A)-1]을 모두 오른쪽으로 이동하므로 A의 크기만큼 시간 필요
    • 최악의 경우 $O(len(A))$ 시간
  • A.remove(9)
    • 처음으로 등장하는 9를 찾아 제거
    • 최악의 경우 $O(n)$ 시간
  • A.index(9), A.count(9)
    • 9가 처음으로 등장하는 index와 총 횟수를 계산
    • 최악의 경우 $O(len(A))$ 시간

효율적인 리스트

Python에서 메모리를 낭비하지 않고 효율적으로 사용하고 싶다면 array 모듈에서 제공하는 compact array type을 사용하자.

또한 numpy 모듈에서 제공하는 array 자료구조도 있다. 대용량 데이터 처리에 효율적이라 데이터 사이언스, 머신러닝 코딩에 적합하다.

numpy의 array의 특징

  1. A[k]: k번째 원소 값을 인덱스로 $O(1)$ 시간에 접근 (리스트와 공통점)
  2. mutable (리스트와 공통점)
  3. 한 종류의 data type만 저장 가능 (리스트와 차이점)
    • ex 1. 정수만 있는 numpy array에 실수값을 저장하려고 하면, 정수로 변환되어 저장
    • ex 2. 정수만 있는 numpy array에 문자열을 저장하려고 하면, ValueError가 뜬다.
  4. 메모리를 리스트보다 적게 사용 (장점)
    • Python의 리스트는 값의 reference를 저장
    • numpy의 array는 값을 직접 저장. 모두 같은 data type이므로 $O(1)$ 시간 접근 가능
  5. 배열 단위의 연산이 매우 빠름 (장점)
    • 2차원 array, 즉 matrix에 대한 연산 등 linear algebra 연산에 최적화되어 설계
    • 이것때문에 머신러닝 데이터 분석에 적합하다.

numpy의 array의 생성 및 기본 연산

1.arange(start, stop, step) 사용법

>>> import numpy as np
>>> A = np.arange(0, 12, 2) # range(start, stop, step)과 유사
>>> A
array([0, 2, 4, 6, 8, 10])
>>> print(A)
[0, 2, 4, 6, 8, 10]
>>> A.shape # A의 차원: 여기에서는 원소 6개의 1차원
(6,)
>>> A.reshape(2,3) # 2x3 2차원 배열로 변환
>>> A
array([[0, 2, 4],
       [6, 8, 10]])
>>> A.shape
(2, 3)
>>> A[1][3] = 2*A[3,1] # A[i][j] 또는 A[i,j] 둘 다 가능
>>> A
array([[0, 2, 20],
       [6, 8, 10]])

2.리스트 활용

>>> A = np.array([1, 2, 3, 4, 5, 6])
>>> A
array([1, 2, 3, 4, 5, 6])

3.Python 기본제공함수 활용

>>> A = np.zeros((3,5)) # 0.0 으로 초기화된 3x5 배열
>>> A
array([0., 0., 0., 0., 0.],
      [0., 0., 0., 0., 0.],
      [0., 0., 0., 0., 0.]])
>>> A = np.ones((2,3)) # 1.0 으로 초기화된 2x3 배열
>>> A
array([1., 1., 1.],
      [1., 1., 1.])
>>> A = np.eye(3,3) # 3x3 identity 배열 생성
>>> A
array([1., 0., 0.],
      [0., 1., 0.],
      [0., 0., 0.]])

4.linspacerandom 함수 활용

>>> A = np.linspace(0, 10, 4) # [0,10] 구간을 4등분
>>> A
array([0., 3.33333333, 6.66666666, 10.])
>>> A = np.random.random((2,3)) # 2x2 원소 값을 [0,1) 구간에서 랜덤하게 생성해 초기화
array([0.234523451, 0.423583742],
      [0.348590345, 0.023423198]])

Stack

Stack은 특수한 일차원의 선형(linear) 자료구조이다. 즉, LIFO(Last In First Out)라는 매우 제한적인 규칙을 따른다. 가장 최근에 저장된 값 다음에 새로운 값이 저장되며, 가장 최근에 저장된 값이 먼저 삭제된다.

Python에서 구현할 경우, 별도로 Stack이라는 Class를 만들어 볼 수 있다. 이때, Python에서 append, pop 함수가 제공됨으로 데이터는 리스트에 저장한다.

Q. Python에 리스트가 이미 있어서 Stack 역할을 할 수 있는데, 굳이 Stack이라는 Class를 만들 필요가 있을까?

A. 리스트는 매우 다양한 기능을 가지고 있다. 반면에 Stack은 딱 두 가지 연산(push, pop)으로만 내부 값을 변경할 수 있다. 리스트를 쓰다보면 실수로 다른 함수를 사용해 내부값을 참고하거나 변경할 수 있다. 이러한 실수를 줄이기 위해 애초에 제공되는 연산을 별도의 클래스로 지정을해서 그 연산으로만 내부 값을 바꾸기 위함이다. 즉, 간접적으로 리스트를 이용해 클래스를 구현한다고 보면 된다.

Stack의 기본연산은 5개(push, pop, top, isEmpty, size(len))이다. Python으로 이 5가지 연산을 구현해본다.

class Stack:
  def __init__(self):
    self.items = [] # 데이터 저장을 위한 리스트 준비

  def push(self, val): # 삽입 연산
    self. items.append(val)

  def pop(self): # 삭제 연산
    try:
      return self.items.pop()
    except IndexError: # pop할 아이템이 없으면 indexError 발생
      print("Stack is empty")

  def top(self):
    try: # Stack에 가장 최근에 들어온 값을 return
      return self.items[-1]
    except IndexError:
      print("Stack is empty")

  def isEmpty(self):
    return len(self) == 0

  def __len__(self): # len()로 호출하면 stack의 item 수를 return
    return len(self.items)

이 5가지 기본연산은 모두 $O(1)$ 시간이다.

Queue

Queue도 Stack과 마찬가지로 특수한 일차원의 선형(linear) 자료구조이다. FIFO(First In First Out)라는 매우 제한적인 규칙을 따른다. 가장 최근에 저장된 값 다음에 새로운 값이 저장지만(Stack과 동일), 가장 오래 전 저장된 값이 먼저 삭제된다.

Queue의 기본연산은 5개(enqueue, dequeue, front, isEmpty, len)이다. Python으로 이 5가지 연산을 구현해본다.

class Queue:
  def __init__(self):
    self.items = [] # 데이터 저장을 위한 리스트 준비
    self.front_index = 0 # 다음 dequeue될 값의 인덱스 기억

  def enqueue(self, val): # 삽입 연산. value를 queue의 오른쪽(rear)에 삽입
    self.items.append(val)

  def dequeue(self): # 삭제 연산. 가장 왼쪽에 저장된 값을 삭제 후 return
    if len(self.items) == 0 or self.front_index == len(self.items):
      print("Queue is empty")
    else:
      x = self.items[self.front_index] # x는 빼낼 값
      self.front_index += 1
      return x

  def front(self): # 가장 왼쪽에 저장된 값을 (삭제하지 않고) return
    if len(self.items) == 0 or self.front_index == len(self.items):
      print("Queue is empty")
    else:
      return self.items[self.front_index]

  def isEmpty(self):
    return len(self) == 0

  def __len__(self): # len()로 호출하면 queue의 item 수를 return
    return len(self.items)-self.front_index

이 5가지 기본연산은 모두 $O(1)$ 시간이다.

이때, dequeue연산을 상수시간에 실행하기 위해서는, dequeue가 될 값의 index를 저장하고 관리해야한다. 그래서 Stack과 달리 위 코드에서 front_index가 생겼다. 이를 활용해, dequeue가 되면 index값이 하나 증가하여 다음 dequeue될 예정인 값의 index를 가리키도록 관리한다. 따라서, dequeue는 사실 값을 아예 삭제하는 것이 아니라 삭제하는 것처럼 보이게 만들어준다. (인덱스만 바꾸고 값 자체는 그대로 있다)

Dequeue

Dequeue는 Stack과 Queue를 합친 자료구조이다. 왼쪽과 오른쪽에도 모두 삽입과 삭제가 가능하다. 왼쪽 오른쪽 두 가지 버전의 push와 pop 연산을 구현하면 되고, 나머지 연산은 Stack, Queue 클래스와 유사하게 구현한다.

Python에서는 collections라는 모듈에 deque라는 클래스로 이미 dequeue가 구현되어 있다.

업데이트:

댓글남기기