자료구조는 어떻게 API가 될까? | ADT부터 Stack과 Resizing Array까지

지난 시간에는 알고리즘을 왜 공부하는지부터 시작해서 문제 해결 방법과 재귀 호출까지 살펴봤다.

이번 시간에는 추상 데이터 타입(Abstract Data Type, ADT)에 대해 배웠다.

처음 ADT라는 말을 들었을 때는 이름부터 조금 어렵게 느껴졌다.

Abstract Data Type
→ 추상 데이터 타입

그런데 수업을 듣다 보니 결국 중요한 질문은 생각보다 단순했다.

자료구조를 사용하는 사람이 그 자료구조가 내부에서 어떻게 구현되어 있는지까지 알아야 할까?

예를 들어 Stack을 사용한다고 해보자.

나는 Stack에 데이터를 넣고 싶다.

stack.push("A");

그리고 가장 마지막에 넣은 데이터를 꺼내고 싶다.

stack.pop();

그런데 Stack이 내부에서 배열로 만들어졌는지, 연결 리스트로 만들어졌는지까지 Stack을 사용하는 코드가 알아야 할까?

꼭 그럴 필요는 없다.

이번 시간에는 여기서 출발해서 ADT와 API가 어떤 관계를 가지는지, 그리고 같은 Stack을 Linked List와 Array로 구현했을 때 어떤 차이가 생기는지를 살펴봤다.

특히 Array로 Stack을 구현하면서

simple
→ doubling
→ amortized

방식으로 배열 크기를 조절하는 방법이 바뀌는 과정이 재미있었다.

단순히 Stack을 구현하는 문제가 아니라

같은 기능을 제공하면서 내부 구현을 어떻게 선택해야 할까?

라는 문제로 이어졌기 때문이다.

---

추상 데이터 타입, ADT란 무엇일까?

먼저 데이터 추상화(Data Abstraction)부터 시작해보자.

데이터 추상화는 새로운 데이터 타입을 정의하는 것이다.

Java에는 이미 여러 데이터 타입이 존재한다.

int
double
boolean

뿐만 아니라

String
Integer
Double
StringBuilder

같은 타입도 사용할 수 있다.

그런데 프로그램을 만들다 보면 언어에서 기본적으로 제공하는 타입만으로는 부족할 수 있다.

그래서 개발자가 자신이 해결하려는 문제에 맞는 새로운 데이터 타입을 정의할 수 있다.

그중 ADT(Abstract Data Type)의 중요한 특징은 데이터가 내부적으로 어떻게 표현되어 있는지를 사용자에게 숨긴다는 것이다.

예를 들어 Counter라는 데이터 타입을 만든다고 해보자.

Counter counter = new Counter("heads");

counter.increment();

System.out.println(counter.tally());

Counter를 사용하는 입장에서 필요한 것은

Counter를 어떻게 생성하는가?

값을 어떻게 증가시키는가?

현재 값을 어떻게 가져오는가?

이다.

내부에서 값을 어떤 변수에 저장하는지는 굳이 알 필요가 없다.

private String name;
private int cnt;

내부 구현은 Counter가 책임진다.

사용자는 공개된 동작만 이용하면 된다.

---

ADT를 배우면서 API가 왜 나오는 걸까?

여기서 처음에는 조금 의문이 들었다.

자료구조를 배우는데 왜 갑자기 API 이야기가 나오는 걸까?

그런데 ADT를 조금 다르게 보면 연결되는 부분이 있었다.

Stack을 예로 들어보자.

Stack이 제공해야 하는 기능을 먼저 정의할 수 있다.

Stack()

void push(Item item)

Item pop()

boolean isEmpty()

int size()

이것이 Stack을 사용하는 사람이 바라보는 인터페이스, 즉 API가 된다.

사용자는

stack.push(item);
stack.pop();
stack.size();

를 알고 있으면 된다.

그 뒤에서 Stack을 어떻게 구현할지는 별개의 문제다.

Client
   │
   │ push(), pop(), size()
   ▼
Interface / API
   │
   ▼
Implementation

즉 알고리즘이나 자료구조를

사용 방법

구현 방법

으로 분리할 수 있다.

수업 자료에서는 이를 Modular Programming의 관점에서도 설명한다.

Client
→ Interface에 정의된 연산을 사용하는 프로그램

Interface
→ 데이터 타입과 기본 연산에 대한 설명

Implementation
→ 실제 연산을 구현하는 코드

처음에는 API라고 하면 REST API처럼

GET /members
POST /members

같은 것만 떠올렸다.

그런데 조금 더 넓게 보면 API는 어떤 기능을 사용할 수 있고 어떻게 호출해야 하는지를 외부에 제공하는 접점이라고 볼 수 있었다.

Stack에서도 마찬가지다.

사용자는

push()
pop()
isEmpty()
size()

만 알면 된다.

그 안에서 배열을 쓰든 연결 리스트를 쓰든 사용자의 코드와 분리할 수 있다.

---

Stack과 Queue는 무엇이 다를까?

ADT의 대표적인 예로 Stack과 Queue가 있다.

둘의 가장 큰 차이는

어떤 데이터를 먼저 꺼내는가?

이다.

Stack은

Last In First Out
LIFO

구조다.

마지막으로 들어온 데이터가 가장 먼저 나온다.

push A
push B
push C

Stack

│ C │ ← 먼저 pop
│ B │
│ A │
└───┘

따라서

pop → C
pop → B
pop → A

순서가 된다.

반면 Queue는

First In First Out
FIFO

구조다.

먼저 들어온 데이터가 먼저 나온다.

A → B → C

dequeue → A

이번 시간에는 이 중 Stack을 직접 구현하면서 내부 구현 방식의 차이를 살펴봤다.

---

Stack은 어떻게 구현할까?

Stack이라는 ADT의 API는 이미 정했다.

push()
pop()
isEmpty()
size()

그런데 여기서 중요한 질문이 생긴다.

이 기능을 실제로 어떻게 구현할까?

대표적인 방법은 두 가지다.

Stack

├── Linked List
└── Array

흥미로운 점은 내부 구현은 완전히 다른데 외부에서 사용하는 API는 같게 만들 수 있다는 것이다.

stack.push("A");
stack.pop();

사용자는 Stack 내부가 무엇인지 몰라도 된다.

ADT가 왜 구현을 숨기는지 여기서 조금 더 명확하게 느껴졌다.

---

1. Linked List로 Stack 구현하기

먼저 Linked List를 사용할 수 있다.

각 Node가 다음 Node를 가리키는 구조다.

first
  ↓
[A | •] → [B | •] → [C | null]

Stack에서는 새로운 데이터를 넣거나 제거할 위치를 first로 잡을 수 있다.

새로운 데이터를 push한다고 해보자.

기존

first
  ↓
[A] → [B]

C를 push한다면

first
  ↓
[C] → [A] → [B]

가 된다.

반대로 pop하면 first가 가리키는 Node를 제거한다.

first
  ↓
[C] → [A] → [B]

pop()

first
  ↓
[A] → [B]

Linked List에서는 이런 연산을 위해 모든 배열 데이터를 복사할 필요가 없다.

연결 관계만 바꾸면 된다.

따라서 Stack의 주요 연산을 일정한 시간에 수행할 수 있다.

---

그런데 Linked List도 공짜는 아니다

처음에는 여기까지 보고

"그러면 그냥 Linked List를 쓰면 되는 것 아닌가?"

라는 생각이 들었다.

하지만 Linked List에도 비용이 있다.

Node 하나에는 실제 데이터만 저장되는 것이 아니다.

class Node {
    Item item;
    Node next;
}

처럼 다음 Node를 가리키기 위한 참조도 저장해야 한다.

즉

[item]

만 필요한 것이 아니라

[item | next]

가 필요하다.

데이터가 많아질수록 이 next를 위한 추가 공간도 계속 필요해진다.

그래서 Linked List는 연산 시간이 일정하다는 장점이 있지만 링크를 유지하기 위한 추가 공간이 필요하다.

---

2. Array로 Stack 구현하기

두 번째 방법은 Array다.

배열을 하나 만들고 N을 현재 Stack의 크기로 사용한다.

index

 0   1   2   3   4
┌───┬───┬───┬───┬───┐
│ A │ B │ C │   │   │
└───┴───┴───┴───┴───┘
            ↑
            N = 3

push는

a[N++] = item;

처럼 구현할 수 있다.

pop은

return a[--N];

처럼 마지막 데이터를 꺼낼 수 있다.

처음 보면 Linked List보다 훨씬 단순해 보인다.

그런데 Array에는 다른 문제가 있다.

---

Stack이 얼마나 커질지 어떻게 알지?

배열은 생성할 때 크기를 정해야 한다.

String[] a = new String[10];

그러면 최대 10개의 데이터를 넣을 수 있다.

하지만 Stack을 사용하는 Client가 데이터를 몇 개 넣을지는 미리 알기 어렵다.

10개?

100개?

10,000개?

처음부터 너무 큰 배열을 만들면 메모리가 낭비된다.

반대로 너무 작게 만들면 Stack이 가득 찬다.

그래서 필요한 것이 Resizing Array다.

Stack의 크기에 따라 배열 자체의 크기를 동적으로 조절하자.

---

resize()는 어떻게 동작할까?

배열은 생성한 뒤 그 자체의 크기를 변경할 수 없다.

따라서 크기를 변경한다는 것은 실제로 기존 배열의 크기를 바꾸는 것이 아니다.

새로운 배열을 만든 뒤 기존 데이터를 복사해야 한다.

예를 들어

기존 배열

[A][B][C][D]

가 가득 찼다고 해보자.

더 큰 배열을 만든다.

새로운 배열

[ ][ ][ ][ ][ ][ ][ ][ ]

그리고 기존 데이터를 전부 복사한다.

[A][B][C][D]
 ↓  ↓  ↓  ↓
[A][B][C][D][ ][ ][ ][ ]

코드로는 다음과 같은 형태가 된다.

private void resize(int max) {

    Item[] temp = (Item[]) new Object[max];

    for (int i = 0; i < N; i++) {
        temp[i] = a[i];
    }

    a = temp;
}

여기서 중요한 부분은

for (int i = 0; i < N; i++)

이다.

현재 데이터가 N개라면 N개의 데이터를 새로운 배열로 복사해야 한다.

즉 resize() 자체에는 N에 비례하는 복사 비용이 발생한다.

그래서 Array 기반 Stack을 분석할 때는 단순히

push → 배열 한 칸에 저장 → O(1)

이라고만 볼 수 없다.

resize가 언제, 얼마나 자주 발생하는지도 같이 봐야 한다.

---

가장 단순하게 resize하면 안 될까?

가장 먼저 생각할 수 있는 방법은 simple 방식이다.

데이터가 하나 늘어날 때마다 배열도 정확히 하나씩 늘리는 것이다.

예를 들어 현재 배열의 크기가 4라고 해보자.

[A][B][C][D]

새로운 E를 넣어야 한다.

그러면 크기가 5인 배열을 만든다.

[A][B][C][D][E]

다음 F가 들어온다.

다시 크기가 6인 배열을 만든다.

[A][B][C][D][E][F]

계속 반복된다.

push E
4 → 5

push F
5 → 6

push G
6 → 7

push H
7 → 8

문제는 배열 크기만 바뀌는 것이 아니라 매번 기존 데이터를 전부 복사해야 한다는 것이다.

예를 들어 5개의 데이터를 순서대로 추가한다고 생각해보자.

1번째 resize → 1개 복사
2번째 resize → 2개 복사
3번째 resize → 3개 복사
4번째 resize → 4개 복사
5번째 resize → 5개 복사

결국

1 + 2 + 3 + 4 + ... + N

만큼의 복사가 필요하다.

즉 전체 비용이 빠르게 커진다.

메모리를 딱 필요한 만큼만 사용한다는 점은 좋아 보이지만, 시간을 너무 많이 사용한다.

---

그러면 한 번에 2배로 늘려보자

여기서 doubling 방식이 나온다.

배열이 가득 찼을 때 하나만 늘리는 것이 아니라 배열 크기를 2배로 늘린다.

예를 들어

capacity = 4

[A][B][C][D]

상태에서 새로운 데이터가 들어오면

capacity = 8

[A][B][C][D][ ][ ][ ][ ]

로 확장한다.

그 뒤에는 데이터가 몇 개 더 들어와도 resize가 필요 없다.

[A][B][C][D][E][F][ ][ ]

다시 배열이 가득 찼을 때

8 → 16

으로 늘린다.

그러면 배열 크기는

1
2
4
8
16
32
64
...

처럼 증가한다.

이제 resize()가 매번 실행되지 않는다.

N개의 데이터를 넣어도 resize가 발생하는 횟수는 대략

log₂N

번이다.

수업 마지막 퀴즈에서

빈 Stack에서 N번 push하면 resize()는 몇 번 호출될까?

라는 문제가 나온 이유도 여기와 연결된다.

배열 크기가

1 → 2 → 4 → 8 → 16 → ...

으로 증가하기 때문에 resize 횟수는 logarithmic하게 증가한다.

---

그런데 Doubling에도 문제가 있다

여기까지 들었을 때는

"그러면 2배씩 늘리면 끝 아닌가?"

라는 생각이 들었다.

하지만 이번에는 배열을 줄일 때 문제가 생긴다.

단순하게

배열이 절반 이하로 사용되면
→ 배열 크기도 절반으로 줄인다.

라고 해보자.

현재 배열 크기가 8이고 데이터가 4개 있다고 하자.

capacity = 8
N = 4

[A][B][C][D][ ][ ][ ][ ]

조건에 따라 배열을 4로 줄인다.

capacity = 4

[A][B][C][D]

그런데 바로 하나를 push하면?

E push

배열이 가득 차 있으므로 다시 8로 늘려야 한다.

4 → 8

그리고 다시 pop하면?

N = 4

다시 절반 조건에 걸려

8 → 4

로 줄어든다.

이 상황이 반복되면

push
4 → 8

pop
8 → 4

push
4 → 8

pop
8 → 4

처럼 배열을 계속 늘렸다 줄였다 하게 된다.

매번 배열 전체를 복사해야 하므로 굉장히 비효율적이다.

이런 현상을 Thrashing이라고 볼 수 있다.

---

그래서 Amortized 방식이 등장한다

해결 방법은 배열을 늘리는 기준과 줄이는 기준 사이에 여유를 두는 것이다.

수업에서는 다음과 같은 방식을 사용한다.

push

배열이 가득 차면
→ capacity × 2

반면 pop에서는

배열 사용량이 1/4 이하가 되면
→ capacity / 2

로 줄인다.

예를 들어 capacity가 8이라고 해보자.

capacity = 8

데이터가 4개가 되었다고 바로 줄이지 않는다.

[A][B][C][D][ ][ ][ ][ ]

N = 4
capacity = 8

아직 그대로 둔다.

데이터가 더 줄어

N = 2

가 되었을 때

N <= capacity / 4

조건을 만족한다.

그때 배열을 절반으로 줄인다.

capacity

8 → 4

이렇게 하면 경계 근처에서 push와 pop이 반복되어도 배열 크기가 계속 바뀌는 현상을 줄일 수 있다.

---

Amortized라는 말은 무슨 뜻일까?

여기서 amortized라는 표현이 처음에는 조금 낯설었다.

resize가 발생하는 순간만 보면 분명 빠르지 않다.

N개의 데이터를 복사해야 하므로 시간이 필요하다.

resize 발생

[A][B][C][D]

↓

[A][B][C][D][ ][ ][ ][ ]

이 순간의 비용은 크다.

하지만 resize는 매번 발생하지 않는다.

대부분의 push는 단순하다.

a[N++] = item;

즉 거의 모든 연산은 빠르고, 가끔 비싼 resize가 발생한다.

그래서 하나의 연산만 보는 것이 아니라 여러 연산의 전체 비용을 나눠서 생각한다.

예를 들어 8번 push한다고 해보자.

push 1 → resize
push 2 → resize
push 3
push 4 → resize
push 5
push 6
push 7
push 8 → resize

resize가 발생할 때는 비싸지만 매 push마다 발생하는 것은 아니다.

그래서 여러 연산 전체를 놓고 평균적으로 비용을 나눠보면 push와 pop을 amortized constant time으로 처리할 수 있다.

즉

어떤 한 번의 연산은 느릴 수 있지만, 연속된 많은 연산의 전체 비용을 보면 연산 하나당 평균 비용은 일정하게 유지된다.

라고 이해했다.

---

Linked List와 Resizing Array 중 무엇이 더 좋을까?

이제 두 구현을 다시 비교해볼 수 있다.

Linked List

장점

push / pop이 항상 일정한 시간
resize가 필요 없음

단점

각 Node마다 next 참조 필요
추가적인 메모리 사용

Resizing Array

장점

링크를 저장할 필요가 없음
상대적으로 낭비되는 공간이 적음
대부분의 연산이 빠름

단점

가끔 resize가 발생
resize 시 기존 데이터를 복사해야 함

수업 자료에서는 이를 다음과 같은 관점으로 비교한다.

Linked List
→ 모든 연산이 worst case에서도 constant time

Resizing Array
→ 모든 연산이 amortized constant time

즉 Linked List는 각 연산의 처리 시간을 일정하게 보장하고 싶을 때 장점이 있다.

반면 Resizing Array는 가끔 복사 비용이 발생하지만 전체 수행 시간과 공간 효율을 중요하게 생각할 때 유리할 수 있다.

처음에는 단순히

"둘 다 Stack을 만들 수 있는데 왜 두 가지나 배우지?"

라는 생각이 들었다.

그런데 구현 방법에 따라

시간

공간

최악의 경우

평균적인 전체 수행 비용

이 달라진다는 것을 비교하기 위한 것이었다.

---

Array에서 pop할 때 null을 넣는 이유는?

Array 기반 Stack 구현에는 처음 보면 이상해 보이는 코드가 하나 있다.

Item item = a[--N];
a[N] = null;

return item;

어차피 N을 줄였는데 왜 굳이

a[N] = null;

을 다시 넣는 걸까?

이것은 Loitering 문제 때문이다.

Stack에서는 해당 객체를 제거했다고 생각하지만 배열에는 여전히 객체를 가리키는 참조가 남아 있을 수 있다.

Stack에서는 제거됨

하지만

Array
↓
Object에 대한 Reference는 남아 있음

그러면 Java의 Garbage Collector 입장에서는

"아직 이 객체를 참조하고 있네?"

라고 판단할 수 있다.

그래서 더 이상 필요하지 않은 참조를 명시적으로 끊어준다.

a[N] = null;

그러면 객체에 대한 다른 참조가 없다면 Garbage Collector가 해당 객체를 정리할 수 있다.

---

여기서 다시 본 Java의 얕은 복사와 깊은 복사

수업 중 배열을 새로 만들고 기존 데이터를 옮기는 부분을 보면서 Java의 객체 복사도 다시 생각해봤다.

예를 들어 다음 배열이 있다고 해보자.

Person[] a = new Person[3];

그리고 새로운 배열을 만든다.

Person[] temp = new Person[6];

기존 데이터를 옮긴다.

for (int i = 0; i < a.length; i++) {
    temp[i] = a[i];
}

여기서 실제 Person 객체 자체를 새롭게 복제한 것은 아니다.

배열 안에 들어 있는 객체를 가리키는 참조값을 복사한 것이다.

a[0] ──────┐
            ▼
         Person A
            ▲
temp[0] ────┘

두 배열의 원소가 같은 Person 객체를 바라본다.

이런 형태를 얕은 복사(Shallow Copy)라고 볼 수 있다.

반면 깊은 복사(Deep Copy)는 객체 자체도 별도로 만들어준다.

a[0]
 ↓
Person A


temp[0]
 ↓
Person A'

따라서 한 객체의 내부 상태를 변경해도 다른 객체에는 영향을 주지 않는다.

Resizing Array의 resize()에서 우리가 원하는 것은 일반적으로 객체 자체를 복제하는 것이 아니다.

새로운 배열을 만들고 기존 Stack이 가지고 있던 객체의 참조를 새로운 배열로 옮기는 것이다.

그래서 배열의 크기를 조정할 때 객체를 전부 새로 생성할 필요는 없다.

---

Generic Array는 왜 바로 만들 수 없을까?

Stack을 특정 타입에만 사용할 필요는 없다.

Stack<String>
Stack<Integer>
Stack<Person>

처럼 다양한 타입을 저장하고 싶다.

그래서 Generic을 사용할 수 있다.

public class ResizingArrayStack<Item> {

그런데 Java에서는 다음과 같이 Generic Array를 직접 생성할 수 없다.

new Item[10];

그래서 수업 코드에서는 Object 배열을 만든 뒤 형변환한다.

Item[] a = (Item[]) new Object[1];

Stack의 구현은 Generic을 사용하고, Client는 원하는 타입을 지정할 수 있다.

ResizingArrayStack<String> stack
        = new ResizingArrayStack<>();

이렇게 하면 같은 Stack 구현을 여러 타입에서 재사용할 수 있다.

---

Iterator는 왜 직접 구현해야 할까?

Stack에 데이터가 다음처럼 들어 있다고 해보자.

push A
push B
push C

배열 내부에서는

index

0   1   2
A   B   C

처럼 저장되어 있다.

그런데 Stack은 LIFO 구조다.

따라서 순회한다면

C → B → A

순서가 자연스럽다.

배열의 기본적인 앞에서 뒤 방향 순회와 반대다.

그래서 Stack의 의미에 맞는 Iterator를 직접 구현한다.

public Iterator<Item> iterator() {
    return new ReverseArrayIterator();
}

그리고 Iterator 내부에서는

private int i = N;

public boolean hasNext() {
    return i > 0;
}

public Item next() {
    return a[--i];
}

처럼 뒤에서 앞으로 이동한다.

Array

A → B → C

Stack Iterator

C → B → A

처음에는

"그냥 for문 돌리면 되는 것 아닌가?"

라고 생각했다.

그런데 Iterator를 구현하면 Client는 Stack 내부가 Array인지 Linked List인지 알 필요 없이 동일한 방식으로 데이터를 순회할 수 있다.

for (String item : stack) {
    System.out.println(item);
}

여기서 다시 ADT의 처음 이야기로 돌아온다.

Client에게는 어떻게 구현했는지를 숨기고, 어떻게 사용할지만 제공한다.

Iterator 역시 그 추상화를 유지하기 위한 방법 중 하나였다.

---

resize()의 시간 복잡도를 다시 생각해보자

마지막으로 이번 시간에서 가장 중요했던 부분 중 하나가 시간 복잡도였다.

처음 Array Stack의 push를 보면

a[N++] = item;

뿐이다.

그래서

push = O(1)

이라고 생각하기 쉽다.

하지만 배열이 가득 차면

resize()

가 실행된다.

resize에서는 N개의 데이터를 복사한다.

for (int i = 0; i < N; i++) {
    temp[i] = a[i];
}

따라서 resize 한 번 자체는

O(N)

의 시간이 필요하다.

그런데 Doubling 방식에서는 매 push마다 resize하지 않는다.

배열 크기는

1 → 2 → 4 → 8 → 16 → 32 → ...

로 증가한다.

N개의 데이터를 push할 때 resize가 발생하는 횟수는 대략

log₂N

번이다.

그리고 지금까지 복사한 전체 데이터 수를 생각하면

1 + 2 + 4 + 8 + ... + N

형태가 된다.

이 합은 N에 비례하는 수준으로 증가한다.

그래서 N번의 push 전체 비용을 N개의 연산에 나눠 생각하면 하나의 push가 평균적으로 상수 시간에 가까운 비용을 가진다고 분석할 수 있다.

이것이 Resizing Array에서 말하는

amortized O(1)

이다.

여기서 하나를 구분해야 한다.

resize() 자체
→ O(N)

push()의 amortized cost
→ O(1)

둘은 같은 이야기가 아니다.

---

정리

이번 시간에는 ADT부터 시작해서 Stack을 실제로 어떻게 구현하는지까지 살펴봤다.

처음에는 ADT를 단순히

추상 데이터 타입

이라는 정의로 외우려고 했다.

그런데 Stack을 두 가지 방법으로 구현해보니 왜 추상화가 필요한지가 조금 더 명확해졌다.

사용자가 원하는 것은

push()
pop()
isEmpty()
size()

이다.

그 내부가

Linked List인지

Array인지

Resizing Array인지

는 구현의 문제다.

즉

Client
    ↓
API
    ↓
Implementation

으로 분리할 수 있다.

그리고 같은 Stack이라도 구현 방식에 따라 서로 다른 비용이 발생했다.

Linked List

연산 시간은 일정
하지만 링크를 위한 추가 공간 필요

반면

Resizing Array

공간 활용은 좋음
하지만 resize 시 복사 비용 발생

Array의 크기를 조절하는 방법도 처음부터 완성된 것은 아니었다.

Simple

필요할 때마다 +1
→ 메모리는 아끼지만 복사를 너무 자주 함

↓

Doubling

가득 차면 ×2
→ resize 횟수를 크게 줄임

↓

Amortized

가득 차면 ×2
1/4 이하가 되면 ÷2
→ push/pop 경계에서 반복되는 resize까지 방지

이 흐름을 보고 나니 자료구조를 공부한다는 것이 단순히

"Stack은 LIFO다."

를 외우는 것만은 아니라는 생각이 들었다.

같은 기능을 제공하더라도

어떤 자료구조를 사용할지

시간을 얼마나 사용할지

공간을 얼마나 사용할지

최악의 한 번을 중요하게 볼지

전체 수행 시간을 중요하게 볼지

에 따라 구현 방법이 달라진다.

특히 이번 시간에는 resize()가 인상적이었다.

코드만 보면 단순히 배열을 새로 만들고 복사하는 함수다.

하지만 이 함수가 언제 호출되도록 설계하느냐에 따라 전체 알고리즘의 성능이 크게 달라졌다.

resize() 한 번
→ O(N)

하지만 resize를 드물게 발생시키면

push() 전체
→ amortized O(1)

결국 이번 시간에 배운 ADT와 Stack도 하나의 흐름으로 연결되는 것 같다.

사용자에게는 필요한 동작만 API로 보여주고, 그 내부에서는 시간과 공간의 Trade-off를 고려해 적절한 자료구조와 알고리즘을 선택한다.

ADT라는 개념이 단순히 자료형 하나를 정의하는 이야기가 아니라, 앞으로 프로그램을 설계할 때 구현과 사용을 어떻게 분리할 것인지에 대한 이야기이기도 한 것 같다.