알고리즘 + 데이터 구조 = 프로그램

Algorithms + Data Structures = Programs

— 니클라우스 비르트Niklaus Wirth (1976)

알고리즘에는 자기 자신을 다시 수행하는 재귀적인recurvie 알고리즘이 있습니다. 예를 들어, 피보나치 수Fibonacci number를 계산하는 문제를 생각해볼 수 있는데요. 피보나치 수란 다음과 같이 이전의 두 숫자를 더해 나열한 것들입니다.

1, 1, 2, 3, 5, 8, 13, 21, \dots

$n$ 번째 피보나치 수를 $f_n$ 이라고 한다면, 점화식recurrence relation으로도 정의할 수 있습니다.

f_n = \begin{cases} f_{n-1} + f_{n-2} &\textrm{($n \geq 3$)} \\ 1 &\textrm{($n = 1, 2$)} \end{cases}

재귀 케이스recursive case라고 불리는 $n \geq 3$ 의 경우를 따라 계산하면, 언젠간 베이스 케이스base case라고 불리는 두 번째 경우에 도달하기 때문에, 계산은 무한한 반복 없이 끝나게 됩니다.

피보나치 수를 구하는 알고리즘은 위 점화식을 다음 수도코드pseudocode로 그대로 옮겨서 만들 수 있습니다.

피보나치 수 ( $n$ ) // $n$ 번째 피보나치 수를 리턴

만약

n \geq 3

이면

리턴 피보나치 수( $n-1$ ) + 피보나치 수( $n-2$ )

아니면

리턴 $1$

그러면 이런 질문을 떠올릴 수 있습니다.

컴퓨터가 이런 재귀 알고리즘을 어떻게 수행할 수 있을까요?
재귀 알고리즘에서 재귀를 항상 없앨 수 있을까요?

컴퓨터는 재귀의 수행을 위해 스택stack이라고 하는 데이터 구조data structure를 암묵적으로 사용합니다. 따라서 이론적으로는, 그 스택을 직접 따라함으로써, 재귀 알고리즘을 재귀가 없는 알고리즘으로 항상 바꿀 수 있습니다.

데이터 구조란 관심있는 문제를 빠르게 해결하기 위해 데이터를 정리하는 방법입니다. 스택은 마지막에 넣은 데이터부터 꺼낼 수 있게 해주는 데이터 구조입니다. 스택은 쌓아둔 것이라는 그 이름대로, 책상 위에 차례로 올려둔 책처럼 데이터를 보관합니다.

컴퓨터가 스택을 사용하는 이유는, 베이스 케이스를 수행하고 나서 리턴 값을 계속 직전의 재귀 케이스로 전달해야 하기 때문입니다.

recursion diagram — 그림 2. 피보나치 수 알고리즘의 재귀 수행 다이어그램. 각 재귀 수행은 직전의 수행으로 돌아가야 할 필요가 있습니다.

한편, 재귀 수행을 관리하는 스택을 직접 따라하면, 어느 재귀 알고리즘이든 재귀 없이 반복문만 사용하는 반복 알고리즘iterative algorithm으로 바꿀 수 있습니다. 달리 말하면, 우리가 재귀 알고리즘을 편하게 사용할 수 있는 이유는 컴퓨터가 안 보이는 곳에서 대신 이런 스택을 관리해주기 때문입니다.

이런 재귀 스택을 직접 따라하는 일은 간단하지 않습니다. 하지만, 예시로 든 피보나치 수 알고리즘의 경우에는, 다음 재귀의 입력 값만 스택으로 기억해도 충분합니다.

예를 들어, 세 번째 피보나치 수 $f_3$ 을 구하는 경우를 봅시다. 처음에 주어지는 $n=3$ 부터 스택에 그대로 넣습니다. $n=3$ 으로 알고리즘이 시작되는 것을 따라하는 것입니다. 이제 스택에서 숫자 하나 꺼내서 이를 $m$ 이라고 하고 다음을 수행합니다.

$m \geq 3$ 이면, $m-1$ 과 $m-2$ 를 스택에 넣습니다. 이 두 숫자로 다음 재귀가 수행되는 것을 따라하는 것입니다.
그렇지 않고 $m < 2$ 이면, $\textit{fib}$ 을 하나 증가시킵니다. 이것은 베이스 케이스에서 리턴한 $1$ 이 재귀 케이스에서 더해진다는 것을 따라합니다.

처음에 꺼낸 숫자는 $3$ 이 되고, 첫 번째 경우를 따라 $1$ 과 $2$ 를 스택에 넣습니다. 나중에 이 숫자가 스택에서 나올 때, $\textit{fib}$ 을 $0$ 에서부터 하나씩 증가시킵니다. 그러면 결과적으로 $\textit{fib}=2$ 를 리턴하게 되고, 실제로 세 번째 피보나치 수 $f_3=2$ 를 얻게 됩니다.

stack for Fibonacci algorithm — 그림 3. 세 번째 피보나치 수를 구하는 과정의 스택. 각 단계는 재귀 수행을 따라합니다. 첫 재귀 수행은 입력 값이 3이므로 이를 스택에 넣습니다. 여기서 다음에 수행할 두 재귀의 입력 값인 1과 2를 스택에 넣습니다. 이후 재귀 수행은 `fib` 변수를 하나씩 증가시키는 결과를 가지므로 이를 반영합니다.

이 아이디어를 수도코드로 옮기면 이렇습니다. 피보나치 수를 구하는 재귀 알고리즘을 반복 알고리즘으로 바꾼 것입니다.

피보나치 수 ( $n$ ) // $n$ 번째 피보나치 수를 리턴 (반복 알고리즘)

스택에 $n$ 을 넣는다

$\textit{fib} \leftarrow 0$ // 피보나치 수 계산 결과

다음을 스택이 비어있지 않은 동안 반복

$m \leftarrow$ 스택에서 꺼낸 숫자

만약

m \geq 3

이면

스택에 $m-2$ , $m-1$ 을 차례로 넣는다

아니면

$\textit{fib} \leftarrow \textit{fib} + 1$

리턴 $\textit{fib}$

그러면 여기서 쓰이는 스택은 어떻게 구현할 수 있을까요? 여기서는 라이브러리와 같은 다른 도움 없이, 두 가지 방법으로 해보겠습니다.

스택 인터페이스

먼저 스택이라는 데이터 구조가 무엇을 할 지부터 결정해봅시다. 이렇게 구체적인 구현 없이 정의한 연산들을 추상 데이터 타입 또는 ADTabstract data type라고 불립니다.

스택은 마지막에 넣은 데이터부터 먼저 나오는, LIFOlast-in first-out 데이터 구조라고도 불립니다. 그리고 데이터를 넣는 연산은 푸시push, 꺼내는 것은 팝pop이라고 흔히 불립니다. 여기에 보조적인 연산을 추가해 스택의 ADT를 정해봅시다.

push(data): 스택에 데이터를 넣습니다.
pop(): 스택에서 데이터를 꺼냅니다. 데이터는 넣었던 순서의 반대로 나와야 합니다.
peek(): 스택에서 데이터를 가져오되 꺼내지는 않습니다. 다음에 팝할 데이터를 미리 알고 싶을 때 쓸 수 있습니다.
size(): 스택에 들어간 데이터의 개수를 구합니다.
isEmpty(): 스택이 비었는지 알아냅니다.

이렇게 데이터 타입이 할 수 있는 것을 먼저 정의함으로써, 구현을 분리할 수 있습니다. 그러면 스택을 사용하는 입장에서는 구현의 세부 사항을 신경쓰지 않아도 됩니다. 실제로 앞으로 두 가지 방법으로 스택을 구현하겠지만, 기능과 성능 상 별 차이가 없게끔 만들 수 있습니다.

구현에 사용할 프로그래밍 언어인 자바Java에 마련된 인터페이스interface를 통해 ADT를 정의합시다.

public interface Stack<T> {
  public void push(T data);
  public T pop();
  public T peek();
  public int size();
  public boolean isEmpty();
}

여기서는 다양한 타입을 지원하기 위해 제네릭generic 스택을 구현하겠습니다.

한편, 자바에서는 제네릭이 int 타입을 비롯한 프리미티브 타입primitive type을 포함하지 않습니다. 그렇지만 Integer 타입과 같은 레퍼런스 타입reference type이 있어서 이를 대신 쓸 수 있습니다. 그리고 자바에는 오토박싱autoboxing이라는 기능으로 이 두 타입 간의 변환을 도와주지만, int 타입을 그대로 쓰는 것보다 성능 상 불리한 점이 있습니다. 그 해결책으로, int 타입을 위한 StackInt 클래스를 별도로 둘 수도 있지만, 간단한 구현을 위해 프리미티브 타입은 신경쓰지 않겠습니다.

링크드 리스트로 구현하는 스택

스택은 배열로도 만들 수 있지만, 배열은 크기를 미리 정해야 합니다. 하지만 스택에 보관할 데이터의 개수는 미리 알기 힘들 수 있습니다. 따라서 데이터를 넣을 때마다 크기가 알아서 조절되는 스택을 만드는 것이 목표입니다. 여기서 배열 말고 다른 데이터 구조를 이용해볼 수 있습니다.

링크드 리스트로 벗어나는 크기 제약

배열과 달리, 필요할 때마다 메모리 크기를 늘리거나 줄일 수 있는 데이터 구조가 있습니다. 링크드 리스트linked list가 대표적인 예시인데요. 보관할 데이터와 다음 데이터의 위치, 이 두 가지를 담는 노드node라는 데이터 구조를 사용합니다. 그러면 데이터를 한 뱡향으로 연결할 수 있게 됩니다.

linked list node diagram — 그림 4. 링크드 리스트의 노드 다이어그램. 각 노드는 데이터를 가지며 그 다음 노드를 가리킵니다. 이때 마지막 노드는 다음 노드를 갖지 않습니다.

링크드 리스트는 각 데이터를 따로 떨어진 곳에 두기 때문에, 연속적인contiguous 메모리 공간을 사용하는 배열과는 차이가 있습니다. 연속적인 메모리 공간은, 데이터의 순번 만으로 빠르게 접근하는 랜덤 엑세스random access를 가능하게 해주는데요. 이를 포기한 링크드 리스트는 랜덤 엑세스 또한 할 수 없게 됩니다. 다시 말해, 크기의 제약에서 벗어난 것은 랜덤 엑세스를 희생한 결과입니다.

실제로 링크드 리스트는 중간의 데이터를 찾기 위해 다음 노드를 계속 방문해야 합니다. 수도코드에서 볼 수 있듯이, $n$ 번째 데이터를 찾는 연산은 $\Theta(n)$ 의 시간 복잡도를 가집니다.

데이터 찾기 ( $n$ ) // $n$ 번째 데이터를 리턴

$\textit{node} \leftarrow$ 링크드 리스트의 첫 노드 (헤드 노드)

다음을

n > 0

인 동안 반복

$n \leftarrow n-1$

$\textit{node} \leftarrow$ $\textit{node}$ 의 다음 노드

리턴

\textit{node}

의 데이터

같은 연산을 배열은 $\Theta(1)$ 에 해내므로 비교적 불리한 특징입니다.

링크드 리스트는 헤드head 노드라고 불리는 맨 앞의 노드만 기억합니다. 나머지 노드는 다음 노드를 따라가다보면 찾을 수 있기 때문입니다. 이런 식으로 한 방향으로 연결된 것을, 이를 단방향 링크드 리스트singly linked list라고도 부릅니다.

그러면 링크드 리스트가 효율적으로 해낼 수 있는 작업을 ADT로 정리해봅시다. 여기서 사용자가 데이터에만 집중할 수 있도록 노드의 존재를 감춥시다.

prepend(data): 맨 앞에 데이터를 추가합니다.
remove(): 맨 앞의 데이터를 지웁니다.
getFirst(): 맨 앞의 데이터를 가져옵니다.
getSize(): 데이터의 개수를 구합니다.
isEmpty(): 리스트가 비었는지 알아냅니다.

예를 들어, prepend() 연산은 다음 수도코드를 떠올려볼 수 있는데요. 새 노드를 만들어 기존 헤드 노드를 그 다음 노드로 연결합니다.

prepend diagram — 그림 5. `prepend()` 연산 다이어그램. 새 노드를 만들고 이를 새로운 헤드 노드로 업데이트합니다.

prepend ( $\textit{data}$ )

$\textit{head} \leftarrow$ 헤드 노드

$\textit{node} \leftarrow$ 다음 노드가 $\textit{head}$ 이고 데이터가 $\textit{data}$ 인 새 노드

$\textit{head} \leftarrow \textit{node}$ // 새 노드를 새 헤드 노드로 업데이트

이렇게 맨 앞에 둔 데이터는 getFirst() 연산으로 찾을 때 가져옵니다.

getFirst ()

$\textit{head} \leftarrow$ 헤드 노드

리턴

\textit{head}

의 데이터

이런 식으로 마지막에 넣었던 데이터를 가장 먼저 찾게 되므로 LIFO 순서를 따릅니다.

반대로 헤드 노드를 지우는 remove() 연산은 다음과 같이 만들어볼 수 있습니다.

remove ()

만약 링크드 리스트가 빈 상태이면

오류 던짐

$\textit{head} \leftarrow$ $\textit{head}$ 의 다음 노드 // 기존 헤드 노드를 버림

이런 연산의 소요 시간을 간단히 예상해볼 수 있습니다. 새 노드를 만드는 연산을 $\Theta(1)$ 이라고 가정하면, 각 메소드는 노드의 개수에 상관 없이 $\Theta(1)$ 의 시간 복잡도로 정리할 수 있습니다. 과연 실제로도 그럴지는 구현 후 확인해보겠습니다.

링크드 리스트 구현하기

링크드 리스트의 구성 요소인 노드 클래스가 먼저 필요합니다. 이 클래스는 데이터와 다음 노드를 기억해야 합니다. 여기선 인스턴스를 만들 때 인자 값을 생략해도 되게끔 생성자를 만들어두었습니다.

public class LinkedNode<T> {
  private T data;
  private LinkedNode<T> next;

  public LinkedNode(T data, LinkedNode<T> next) {
    this.data = data;
    this.next = next;
  }

  public LinkedNode() {
    this(null, null);
  }

  // ...
}

그리고 이어서 필드 접근을 위한 메소드를 만듭니다.

  public T getData() {
    return this.data;
  }

  public LinkedNode<T> getNext() {
    return this.next;
  }

  public void setData(T data) {
    this.data = data;
  }

  public void setNext(LinkedNode<T> next) {
    this.next = next;
  }

위 노드 클래스를 이용해 링크드 리스트를 만들어 봅시다. 먼저 생성자는 헤드 노드와 사이즈를 초기화하도록 만듭시다.

public class LifoLinkedList<T> {
  private LinkedNode<T> head;
  private int size;

  public LifoLinkedList() {
    this.head = new LinkedNode<>(); // sentinel
    this.size = 0;
  }
}

인스턴스 생성시 기본적으로 빈 노드를 하나 가지도록 만들었습니다. 센티넬sentinel이라고도 불리는 이 더미dummy 데이터는 메모리를 더 쓰는 대신, 곧 볼 것처럼 코드를 단순하게 만들 것입니다.

prepend() 메소드는 기존 수도코드를 따라 그대로 코드로 만듭니다.

  public void prepend(T data) {
    LinkedNode<T> node = new LinkedNode<>(data, head);
    this.head = node;

    this.size++;
  }

사이즈를 기억할 필요가 있기 때문에, 늘어난 노드의 개수를 반영합니다.

이제 getFirst() 메소드가 데이터를 구하도록 만들고, 데이터가 없는 경우 에러를 던지도록 합시다.

  public T getFirst() {
    this.throwIfEmpty();

    return this.head.getData();
  }

  private void throwIfEmpty() {
    if (this.size == 0) {
      throw new NoSuchElementException();
    }
  }

remove() 메소드 또한 기존 수도코드를 따라 만들 수 있습니다. 이 때에도 데이터가 없는 경우를 예외로 처리합니다.

단순히 다음 노드로 헤드 노드를 업데이트 할 수 있는 이유는, 더미 노드 때문에 다음 노드가 적어도 하나 있기 때문입니다. 만약 이런 센티넬이 없었다면, 링크드 리스트에 노드가 하나도 없는 경우를 특별히 처리해야 했을 것입니다.

기존 헤드 노드는 자바의 가비지 컬렉션garbage collection 대상이 되어 곧 사라집니다.

  public void remove() {
    this.throwIfEmpty();

    this.head = this.head.getNext();

    this.size--;
  }

사이즈와 관련된 메소드는 다음과 같이 간단히 구현합니다. 이로써 사이즈는 읽기만 가능한read-only 속성이 됩니다.

  public int getSize() {
    return this.size;
  }

  public boolean isEmpty() {
    return this.size == 0;
  }

소요시간 측정

위에서 모든 메소드가 $\Theta(1)$ 의 시간 복잡도로 분석한 것이 실제로 적절할까요? 비교적 길이가 있는 두 메소드 prepend()와 remove()에 대해 소요 시간을 측정하면 다음과 같습니다. 벤치마킹 시나리오는 prepend()만 할 때와, 그것과 remove()를 같은 횟수만큼 할 때입니다.

elapsed time for prepend and remove — 그림 7. 각 시나리오에 따른 소요 시간. 직선은 회귀선.

노드의 개수 $n$ 과 $n$ 번 연산에 드는 소요 시간 사이에 선형적인 관계가 나타나는데요. 즉 노드의 개수 $n$ 에 상관 없이 각 연산은 소요 시간을 일정하게 증가시킴을 확인할 수 있습니다.

링크드 리스트로 스택 구현하기

위에서 만든 링크드 리스트를 이용해 스택을 만들 수 있는데요. 기존의 링크드 리스트 연산을 대부분 그대로 이용해 만들 수 있습니다. 예를 들어, 푸시 연산은 단순히 링크드 리스트에 헤드 노드를 추가하는 일이 됩니다.

push ( $\textit{data}$ )

$\textit{list} \leftarrow$ 링크드 리스트

$\textit{list}$ .prepend( $\textit{data}$ )

반대로 팝 연산은 헤드 노드의 데이터를 가져온 뒤, 이를 제거하는 일이 됩니다.

pop ()

$\textit{list} \leftarrow$ 링크드 리스트

$\textit{data} \leftarrow$ $\textit{list}$ .getFirst()

$\textit{list}$ .remove()

리턴

\textit{data}

이제 실제로 스택을 구현해봅시다. 먼저, 생성자는 단순히 링크드 리스트를 초기화하는 일이 됩니다.

public class ListStack<T> implements Stack<T> {
  private LifoLinkedList<T> list;

  public ListStack() {
    this.list = new LifoLinkedList<>();
  }
}

푸시와 팝은 앞서 보인 수도코드대로 옮길 수 있습니다.

  public void push(T data) {
    this.list.prepend(data);
  }

  public T pop() {
    T data = this.list.getFirst();
    this.list.remove();

    return data;
  }

나머지 메소드는 링크드 리스트 메소드에 할 일을 위임함으로써 간단히 만들 수 있습니다.

  public T peek() {
    return this.list.getFirst();
  }

  public int getSize() {
    return this.list.getSize();
  }

  public boolean isEmpty() {
    return this.list.isEmpty();
  }

이제 유닛 테스트를 통해 잘 동작하는지 확인해봅시다. 여기서는 JUnit 5 프레임워크를 사용합니다. 아래와 같이 성공 케이스는 마지막에 푸시한 것을 팝하는지, 실패 케이스는 빈 스택에서 팝할 때 에러를 던지는지 확인합니다.

  @Test
  public void testPushAndPop() {
    ListStack<Integer> stack = new ListStack<>();
    stack.push(42);
    stack.push(43);

    assertEquals(43, stack.pop());
  }

  @Test
  public void testPopForEmptyStack() {
    ListStack<Integer> stack = new ListStack<>();

    assertThrows(NoSuchElementException.class, () -> stack.pop());
  }

이는 모두 잘 통과하는 테스트가 됩니다.

정리하면 링크드 리스트를 이용해 푸시와 팝 연산을 $\Theta(1)$ 의 시간 복잡도로 할 수 있는 스택을 만들었습니다.

배열로 구현하는 스택

배열은 자바를 비롯해 많은 프로그래밍 언어에 내장된 데이터 구조입니다. 스택의 크기에 제약을 두고 싶지 않다면, 배열은 스택 구현에 적합하지 않을 수 있습니다.

그런데 (바람직하지는 않지만) 배열을 엄청나게 크게 만들었다고 해봅시다. 그러면 배열로도 스택을 구현할 수 있습니다. 스택은 최근에 추가한 데이터에 관심이 있기 때문에, 그런 데이터의 인덱스를 기억하면 되기 때문입니다.

push operation with array — 그림 8. 배열로 구현하는 푸시 연산 다이어그램. $n+1$ 위치에 데이터가 들어오면, 그 위치를 갖던 기존 `i`는 다음 위치인 $n+2$ 로 업데이트합니다.

예를 들어, 배열에 $n$ 개의 데이터가 있다고 해봅시다. 다음 푸시 연산은 $n+1$ 번째 원소로 할당할 차례인데요. 이 인덱스를 특별히 변수 i로 기억해둡니다.

푸시 연산이 수행되면, 배열에서 i 위치에 데이터를 할당하고, i의 값을 하나 증가시킵니다. 그러면 i는 항상 다음 푸시 연산의 인덱스를 가리키므로, 이 과정을 반복할 수 있게 됩니다.

랜덤 엑세스

푸시 연산을 빠르게 할 수 있는 이유는, 배열은 랜덤 엑세스, 즉 $n$ 번째 데이터에 빠르게 접근할 수 있기 때문입니다. 그리고 그런 랜덤 엑세스가 가능한 이유는, 그것이 사칙 연산에 불과하기 때문입니다.

배열 변수가 첫 원소의 메모리 주소를 가진다고 해봅시다. 그러면 각 원소의 접근은 주소 값의 사칙 연산으로 구현할 수 있습니다.

예를 들어, arr[10]라는 표현은 배열 arr의 10번째 원소에 접근하겠다는 뜻이지만, 결국 주소를 더하는 연산이 됩니다. 변수 arr은 첫 번째 원소의 메모리 주소이고, 10은 얼마나 떨어져 있는지 나타내는 오프셋offset이므로, 이를 더해 원하는 주소를 얻게 됩니다.

이 점에 비추어 볼때, 배열의 인덱스가 0부터 시작하는 이유를 알 수 있습니다. 왜냐면 첫 번째 원소에서 0 만큼 떨어진 곳이 바로 첫 번째 원소이기 때문입니다.

그리고 이런 식으로 랜덤 엑세스를 구현하는 한, 반드시 어딘가에는 주소 값을 기억해두어야 합니다. C나 C++ 같은 프로그래밍 언어에서는 주소 값을 데이터 타입으로서 다루고 이를 포인터pointer라고 부릅니다. 반면 이런 기능이 없는 언어인 경우에도, 내부적으로는 주소 값을 다룰 수밖에 없게 됩니다.

다이나믹 배열

크기의 제약이 없다면 배열로도 스택을 구현할 수 있을텐데요. 크기를 알아서 조절하는 배열을 데이터 구조로 만들 수 있고, 여기엔 다이나믹 배열dynamic array, 또는 그로잉 배열growing array, 리사이징 배열resizing array 등 여러 이름을 갖고 있습니다. 파이썬Python과 같은 프로그래밍 언어에서는 배열이 기본적으로 그렇게 구현되어 있기도 합니다.

이 데이터 구조의 ADT를 만들어봅시다. 맨 끝의 데이터에 관심이 있기 때문에, 이를 추가하고 삭제하는 append()와 remove() 연산을 만듭시다. 그리고 배열은 랜덤 엑세스가 가능해야 하므로, 이를 위한 get()과 set() 연산도 더합시다.

append(data): 데이터를 맨 끝에 추가합니다.
remove(): 맨 끝의 데이터를 삭제합니다.
get(index): index번째 데이터를 가져옵니다. 즉 랜덤 엑세스 구현입니다.
set(index, data): index번째 데이터를 수정합니다. 이 또한 랜덤 엑세스 구현입니다.
getSize(): 데이터의 개수를 구합니다.

크기를 조절하는 방식은 구현하기 나름입니다. 예를 들어, 배열이 전부 다 찼을 때 기존 $n$ 개의 크기에서 $2n$ 으로 늘릴 수 있습니다. 이렇게 늘리는 비율을 그로스 팩터growth factor라고 합니다. 두 배씩 늘리는 경우, 이 값을 $2$ 로 나타냅니다.

크기가 큰 배열을 새로 할당하면, 기존 배열의 데이터를 그곳으로 옮기는 작업이 필요합니다. 이는 비교적 시간이 걸리는 일입니다. 만약, 그로스 팩터가 $4$ 라면, 늘리는 일은 덜 일어나겠지만, 그 직후에 실제로 사용하는 메모리는 25%에 불과하므로, 나머지 75%를 낭비로 볼 수 있습니다. 이렇게 크기 대비 실제 사용하는 개수의 비율을 로드 팩터load factor라고 부르고, 이 경우 $0.25$ 가 됩니다.

반대로 그로스 팩터를 작게하면, 낭비는 줄고 로드 팩터는 올라가겠지만, 크기를 늘리는 작업이 더 빈번해집니다. 이처럼 시간과 메모리 공간 사이의 트레이드 오프trade-off, 즉 한 쪽을 얻기 위해 다른 쪽을 희생하는 일은 데이터 구조와 알고리즘을 디자인할 때 자주 나타나는 현상입니다. 여기서는 그로스 팩터를 $2$ 로 하겠습니다.

한편, 여러 언어가 이런 다이나믹 배열을 구현하고 있는데요. 그 만큼 다양한 그로스 팩터가 있습니다. 예를 들어, 자바의 ArrayList (OpenJDK) 구현은 $1.5$ , 파이썬(CPython)의 배열은 약 $1.125$ , C++ (Clang)의 vector는 여기서와 같이 $2$ 인 것으로 알려져 있습니다. 이런 선택은 각 언어가 트레이드 오프 문제를 어떻게 타협했는지 보여주기도 합니다.

배열의 크기 조절하기

앞서 보았듯, 데이터를 추가하다보면 크기 늘리는 일이 필요하게 됩니다. 이를 수도코드로 이렇게 만들어 볼 수 있습니다.

append ( $\textit{data}$ ) // 끝에 데이터를 추가

$a \leftarrow$ 배열

$i \leftarrow$ 데이터를 추가할 다음 인덱스

만약 배열이 전부 찬 상태이면

$a \leftarrow$ 두 배로 늘린 새 배열

$a$ [ $i$ ] $\leftarrow$ $\textit{data}$

$i \leftarrow i + 1$ // 다음에 추가할 인덱스 업데이트

이 연산은 배열을 두 배로 늘리는 일의 시간 복잡도가 문제가 됩니다. 배열의 원소가 $n$ 개일 때, 늘린 배열에 기존 배열을 복사하는 작업은 $\Theta(n)$ 이 된다고 합시다. 왜냐면 원소에 하나하나 접근하면서 복사할 테니까요. 이 어쩌다 한번 일어나는 이 작업을 고려했을 때, 원소를 추가하는 이 연산은 $O(n)$ 의 시간 복잡도라고 할 수 있습니다.

그런데 더 나은 추측을 해볼 수 있습니다. 예를 들어, 크기가 $n$ 개인 배열이 다 찼다고 해봅시다. 여기에 데이터를 하나 더 추가하면, 그로스 팩터가 $\alpha$ 일 때, 크기를 $\alpha n$ 개로 늘려야 합니다. 이후 이 배열을 가득 채울 때까지 데이터를 추가한다고 해봅시다. 이는 배열이 한차례 늘어난다음 또 한번 늘어나기 직전까지의 상황입니다.

시간 복잡도를 구해봅시다. append() 연산은 배열을 늘리는 작업이 없을 때 $\Theta(1)$ 의 시간 복잡도를 갖는다고 할 수 있습니다. 데이터가 $n$ 개에서 $\alpha n$ 개가 될 때까지 append() 연산을 수행한다면, 이 연산은 총 $(\alpha-1)n$ 번 일어나고, 배열은 한 번 늘어나서 $n$ 개의 원소를 옮깁니다. 따라서 시간 복잡도는 전체적으로 $\Theta(\alpha n)$ 라고 할 수 있습니다. 이를 연산의 총 횟수 $(\alpha-1)n$ 으로 나누면, 한 번의 append() 연산이 갖는 시간 복잡도를 이렇게 구할 수 있습니다.

\Theta\left(\frac{\alpha}{\alpha - 1}\right) \rightarrow \begin{cases} \Theta(1) \quad &\textrm{as $\alpha \rightarrow \infty$} \\ \Theta(\infty) \quad &\textrm{as $\alpha \rightarrow 1$} \end{cases}

이를 통해 그로스 팩터가 시간 복잡도에 미치는 영향을 알 수 있습니다. 그로스 팩터 $\alpha$ 가 큰 경우, 평균적인 시간 복잡도는 낮아집니다. 다만 로드 팩터가 낮아져 메모리 낭비가 더 커질 것입니다. 반대로 $1$ 에 가까운 경우엔 시간 복잡도는 한없이 커집니다.

여기서 선택한 그로스 팩터 $\alpha = 2$ 는 충분히 괜찮은 상수 시간 $\Theta(1)$ 를 가진다고 할 수 있습니다. 이렇게 일종의 평균적인 시간 복잡도를 구하는 분석을 아모타이즈드amortized 분석이라고 합니다. 이에 따라 append() 연산의 시간 복잡도는 아모타이즈드 $\Theta(1)$ 이라고 합니다.

반대로 데이터를 제거할 때를 봅시다. 여러 차례 데이터를 지워 로드 팩터가 낮아진 상태라면, 메모리 낭비를 줄이기 위해 배열의 크기를 줄일 수 있습니다. 여기서는 그 기준을 로드 팩터가 $0.25$ 이하가 되면, 크기를 절반으로 줄이겠습니다. 이러한 제거 연산을 수도코드로 만들어봅시다.

remove () // 끝에 있는 데이터를 제거

$a \leftarrow$ 배열

$i \leftarrow$ 데이터를 추가할 다음 인덱스

만약 로드 팩터

\leq 0.25

이면

$a \leftarrow$ 반으로 줄인 새 배열

$i \leftarrow i - 1$ // 다음에 추가할 인덱스 업데이트

$a$ [ $i$ ] $\leftarrow$ $\textit{data}$

이 경우 또한 아모타이즈드 $\Theta(1)$ 의 시간 복잡도를 계산할 수 있는데요. 이는 비슷한 내용이기 때문에 직접 해보는 문제로 남기고 생략하겠습니다.

그러면 이 수도코드를 바탕으로 다이나믹 배열을 구현해보겠습니다.

다이나믹 배열 구현하기

사실 다이나믹 배열에는 두 가지의 크기 개념이 존재합니다. 하나는 데이터 구조의 사용자 입장의 크기로, 이 배열이 가진 데이터의 개수입니다. 여기서는 사이즈라고 부르겠습니다.

또 다른 하나는 이 데이터 구조가 내부적으로 유지하고 있는 크기입니다. 즉 배열이 실제로 차지하고 있는 메모리 크기입니다. 따라서 위 연산에서 늘리는 크기란 이 크기를 말한 것입니다. 이를 여기서는 커패시티capacity라고 부르겠습니다.

이제 자바 코드로 ADT를 구현해봅시다. 먼저 생성자는 내부 배열과 사이즈, 커패시티를 초기화합니다. 여기서 쓰이는 숫자들은 매직 넘버magic number로 쓰는 대신 상수로 만들었습니다.

public class DynamicArray<T> {
  final static private int INIT_CAPACITY = 4;
  final static private double GROWTH_FACTOR = 2.0;

  private T[] arr;
  private int size;
  private int capacity;

  public DynamicArray() {
    @SuppressWarnings("unchecked")
    T[] initArr = (T[]) new Object[INIT_CAPACITY];

    this.arr = initArr;
    this.size = 0;
    this.capacity = INIT_CAPACITY;
  }
}

자바는 제너릭 배열의 생성을 허용하지 않기 때문에, 이런 다소 우회적인 코드를 썼습니다. 여기서 나타나는 경고는 SuppressWarnings 어노테이션으로 무시하기로 합시다.

이렇게 초기화하면 자연스럽게 size 변수 값은 데이터를 추가할 다음 인덱스가 됩니다. 따라서 수도코드를 따라 append() 메소드를 다음과 같이 구현할 수 있습니다.

  public void append(T data) {
    if (this.isOutOfCapacity(this.size)) {
      int newCapacity = (int)(GROWTH_FACTOR * this.capacity);
      this.resizeCapacity(newCapacity);
    }

    this.arr[this.size++] = data;
  }

비교적 저수준인 작업은 이렇게 프라이빗private 메소드에 맡겼습니다.

  private boolean isOutOfCapacity(int index) {
    return index < 0 || index >= this.capacity;
  }

  private void resizeCapacity(int newCapacity) {
    this.arr = Arrays.copyOf(this.arr, newCapacity);
    this.capacity = newCapacity;
  }

remove() 메소드 또한 수도코드를 따라 그대로 옮깁니다. 로드 팩터가 너무 작으면 배열을 줄입니다. 제거할 원소에는 null을 대입해 가비지 컬렉션 대상이 되도록 만듭니다.

  public void remove() {
    if (this.isTooFewLoaded()) {
      int newCapacity = (int)(this.capacity / GROWTH_FACTOR);
      this.resizeCapacity(newCapacity);
    }

    this.arr[--this.size] = null; // avoid memory leak
  }

여기서도 저수준 작업은 프라이빗 메소드에 맡깁니다. 로드 팩터가 ‘너무 작다’는 기준은 여기선 $0.25$ 이하입니다. 이 숫자를 최소 로드 팩터라고 하고, 상수 minLoadFactor의 값으로 둡시다.

  final static private double MIN_LOAD_FACTOR = 0.25;

  private boolean isTooFewLoaded() {
    if (this.capacity <= INIT_CAPACITY) {
      return false;
    }

    double loadFactor = (double)this.size / (double)this.capacity;
    return loadFactor <= MIN_LOAD_FACTOR;
  }

랜덤 엑세스 구현을 위한 get(), set() 메소드는 인덱스가 범위가 크기를 벗어날 때를 예외로 처리합니다.

  public T get(int index) {
    throwIfOutOfSize(index);

    return this.arr[index];
  }

  public void set(int index, T data) {
    throwIfOutOfSize(index);

    this.arr[index] = data;
  }

  private void throwIfOutOfSize(int index) {
    if (this.isOutOfSize(index)) {
      throw new IndexOutOfBoundsException();
    }
  }

  private boolean isOutOfSize(int index) {
    return index < 0 || index >= this.size;
  }

사이즈를 구하는 메소드 getSize()는 그저 현재 데이터의 개수를 리턴합니다.

  public int getSize() {
    return this.size;
  }

소요 시간 측정

링크드 리스트 때와 마찬가지로, 소요 시간을 측정해봅시다. 데이터 추가와 삭제 메소드를 아모타이즈드 $\Theta(1)$ 으로 분석했는데요. 데이터 추가만 할 때와, 그것과 데이터 삭제를 같은 횟수로 하는 시나리오로 벤치마킹을 한 결과는 각각 이렇습니다.

elapsed time for append and remove — 그림 12. 각 시나리오에 따른 소요 시간. 직선은 회귀선.

여기서도 노드의 개수 $n$ 과 $n$ 번 연산에 걸리는 소요 시간 사이에 선형적인 관계가 나타납니다. 한편, 마지막 $n = 2^{17}$ 의 경우, 두 시나리오에서 회귀선을 다소 벗어나는 경향을 보이는데요. 시간 복잡도를 구할 때는 배열 할당이 $\Theta(1)$ 이라고 가정했지만, 배열의 크기가 크면 다소 시간이 걸려 실제로는 그렇지 않기 때문입니다. 그렇지만 이러한 오차를 포함하더라도 소요 시간은 각각 $\Theta(n^{1.02})$ , $\Theta(n^{1.00})$ 으로, 분석했던 이론적인 시간 복잡도를 크게 벗어나지 않는 것을 확인할 수 있습니다.

배열로 구현하는 스택

링크드 리스트 때와 마찬가지로 같은 스택 인터페이스를 구현해봅시다. 이번에도 많은 부분을 배열 메소드에 위임합니다.

먼저 생성자는 내부의 다이나믹 배열을 초기화 합니다.

public class ArrayStack<T> implements Stack<T> {
  private DynamicArray<T> arr;

  public ArrayStack() {
    this.arr = new DynamicArray<>();
  }
}

푸시는 간단히 배열에 데이터를 추가하는 것으로 만듭니다.

  public void push(T data) {
    this.arr.append(data);
  }

팝은 마지막 위치의 데이터를 가져오기를 시도합니다. 이 작업은 getLast()라는 프라이빗 메소드에 맡겼습니다. 다이나믹 배열이 빈 경우, 잘못된 인덱스 접근이라는 에러가 던져집니다. 이때, 링크드 리스트의 경우처럼, 의미 상 원소를 찾지 못한 것으로 바꿔 다시 에러를 던집시다. 그러면 사용자는 구현의 디테일에 상관없이 일관된 인터페이스를 가집니다.

  public T pop() {
    T data = this.getLast();
    this.arr.remove();

    return data;
  }

  private T getLast() {
    try {
      return this.arr.get(this.arr.getSize()-1);
    } catch (IndexOutOfBoundsException e) {
      throw new NoSuchElementException();
    } catch (RuntimeException e) {
      throw e;
    }
  }

나머지 메소드는 간단히 배열의 메소드에 위임합니다.

  public T peek() {
    return this.getLast();
  }

  public int getSize() {
    return this.arr.getSize();
  }

  public boolean isEmpty() {
    return this.arr.getSize() == 0;
  }

이렇게 만든 스택은, 링크드 리스트 때와 같은 유닛 테스트를 통과합니다.

  @Test
  public void testPushAndPop() {
    ArrayStack<Integer> stack = new ArrayStack<>();
    stack.push(42);
    stack.push(43);

    assertEquals(43, stack.pop());
  }

  @Test
  public void testPopForEmptyStack() {
    ArrayStack<Integer> stack = new ArrayStack<>();

    assertThrows(NoSuchElementException.class, () -> stack.pop());
  }

정리하면, 배열로도 각 연산이 $\Theta(1)$ 의 시간 복잡도를 가지는 스택을 만들었습니다.

여기까지 오셨다면, 처음에 소개했던 피보나치 수를 구하는 반복 알고리즘을 스택으로 만들어보세요. Stack 인터페이스를 이용하면, 알고리즘이 구체적인 스택 클래스를 알지 않아도 되도록 구현할 수 있습니다. 즉, 만들었던 두 스택 클래스에 상관없이 똑같은 알고리즘으로 피보나치 수를 구할 수 있습니다.

마치며

스택은 넣은 순서의 반대로 데이터를 꺼낼 수 있는 데이터 구조입니다. 이는 재귀 수행에 필요한 것이었는데요. 반대로 스택을 직접 사용함으로써 재귀 알고리즘을 반복 알고리즘으로 바꿀 수도 있었습니다.

한편, 이 스택은 여러 기초적인 데이터 구조로 구현할 수 있었습니다. 여기서는 두 가지를 이용해 구현했는데요. 하나는 링크드 리스트, 또 다른 하나는 다이나믹 배열이었습니다. 이 중에 다이나믹 배열은 크기를 조절하기 위해 복사가 필요하므로 비교적 불리한 시간 복잡도를 가질 것 같지만, 아모타이즈드 분석으로 사실상 링크드 리스트와 같은 시간 복잡도를 계산할 수 있었습니다. 그리고 이는 실제 소요 시간 측정으로 확인해봤습니다.

정리하면, 같은 데이터 구조라도 다른 방법으로 만들 수 있었습니다.

본문의 자바 코드는 깃허브GitHub에서도 확인할 수 있습니다.

레퍼런스

Introduction to Algorithms (3rd ed., Thomas Cormen et al., 2009)
Algorithms (4th ed., Robert Sedgewick, 2011), 또는 알고리즘 (길벗, 2018)
Computer Organization and Design (5th ed., David Patterson, John Hennessy, 2014), 또는 컴퓨터 구조 및 설계 (2015): 재귀 수행 스택, 저수준 관점에서의 배열 소개.
The Practice of Programming (Brian Kernighan, Rob Pike, 1999), 또는 프로그래밍 수련법 (인사이트, 2008): 다이나믹 배열 소개.
Dynamic Array (Wikipedia): 언어별 그로스 팩터.
Java Microbenchmark Harness (JMH): 자바 코드의 소요 시간 측정에 사용한 도구.