CodeMia 2025. 5. 30. 16:01

Lecture 2: Data Structures

1. Data Structure Interfaces

1-1. data structure?

A data structure is a way to store data, with algorithms that support operations on the data

데이터 구조는 데이터를 저장하는 방법이다. 그리고 저장된 데이터를 다루는 알고리즘을 함께 제공한다 

배열, 연결 리스트, 해시맵 → 단순히 값만 저장하는 게 아니라 값을 넣기, 찾기, 꺼내기 같은 연산을 어떻게 할지까지 포함한다. 

1-2. interface?

Collection of supported operations is called an interface (also API or ADT)
데이터 구조가 제공하는 연산들을 인터페이스라고 부른다. 
다른 말로 API(Application Programming Interface), ADT(Abstract Data Type)라고도 한다. 

 

1-3. interface vs Data Structure 

Interface is a specification: what operations are supported (the problem!)
다시 말해, 인터페이스는 데이터 구조가 어떤 연산을 제공하는지 알려주는 목록 같은 것이다

Data structure is a representation: how operations are supported (the solution!)
반면 데이터 구조는 이 인터페이스를 어떻게 구현할지에 대한 방법이다. 
같은 인터페이스를 여러 방식으로 구현할 수 있다. 

예: 나중에 살펴보겠지만 get(i)가 있는 Sequence 인터페이스를 배열로 구현할 수도, 연결 리스트로 구현할 수도 있다. 

 

Interface (API/ADT) Data Structure
메뉴판 그 메뉴를 요리하는 방식 
같은 김치여도 젓갈을 안넣고 만드는 가게도 있고 젓갈을 듬북 넣고 만드는 가게도 있다. 어떻게 만들었는지는 가게가 알아서 처리하듯이 그 내부 사정이 data Structure이다. 
Specification 어떤 연산을 지원하는지 명세 representation 그 연산을 어떤 알고리즘으로 실행할 지 결정
what data can store 무슨 데이터를 다루는지 정의  how to store data 그 연산들을 어떻게 메모리에 저장할 지 설계
what operations are supported & what they mean algorithms to support Operations
Problem 문제  Solution 해결 방법 
데이터의 종류와 지원하는 연산만 설명하고,
그걸 어떻게 구현할지는 말하지 않는다.

a way to store data, with algorithms that support operations on the data. 

이 인터페이스를 실제로 어떻게 구현할지에 대한 방법 
→ 메모리에 어떤 방식으로 데이터를 저장할지, 
연산은 어떤 알고리즘으로 처리할지를 결정한다. 
예: Sequence, Set, Map 등 예: Array, LinkedList, Hashset, TreeMap 등
예시: Sequence interface
  • 데이터: 순서 있는 값들
  • 연산:
    • get(i) → i번째 값 가져오기
    • set(i, x) → i번째 값 x로 바꾸기
예시: Sequence 인터페이스를 구현할 때
  • 배열(Array)로 구현 → 인덱스 접근 O(1), 삽입 O(n)
  • 연결 리스트(LinkedList)로 구현 → 인덱스 접근 O(n), 앞뒤 삽입 O(1)
둘 다 같은 기능을 제공하지만 구현 방식과 성능이 다르다.

 

 

1-4. Sequence Interface  vs Set Interface

시퀀스와 셋 인터페이스

In this class, two main interfaces: Sequence and Set

  • Sequence (순서 있는 집합) 
  • Set (순서 없는 집합, 키 기반) 
  Set Interface Sequence Interface
특징 순서 없음 순서 있음
설명 보통 key-value  원하는 순서대로 저장하고 꺼낼 수 있는 구조
중복 허용 중복 허용 안 함 (Set의 특성) 중복 허용됨 (List는 같은 값 여러 개 가능)
주요 사용 예 HashSet, Map, Dictionary Array, List, Linked List, Stack(LIFO 순서중요), Queue(FIFO 순서중요)
  Set은 고유성 유지가 핵심 Sequence는 순서 유지가 핵심

 


2. Sequence Interface vs  Set Interface

2-1 Sequence Interface 

Maintain a sequence of items (order is extrinsic)

아이템들을 순서 있는 상태로 유지한다. 

데이터 값 자체에는 순서 정보가 없고, 데이터 구조 바깥에서 순서를 부여한다

예: 배열에서 값 3, 5, 7이 있으면 값 그 자체로는 누가 먼저인지 알 수 없지만
배열의 인덱스(0,1,2)가 순서 정보를 부여한다.

 

* extrinsic: 외부에서 

 

Ex: (x_0, x_1, x_2, . . . , x_n−1) (zero indexing)

보통 인덱스는 0부터 시작하는 zero indexing 방식이다. 
즉, 첫 번째 아이템은 x_0, 두 번째는 x_1 이런 식

 

(use n to denote the number of items stored in the data structure)

데이터 구조에서는 n 변수를 사용해서 아이템의 갯수를 표시한다. 

 

Supports sequence operations:

Sequence 인터페이스는 다음과 같은 시퀀스 연산들을 지원한다

 

Special case interfaces:

특별한 경우의 인터페이스들

일반적인 시퀀스 인터페이스에서 제한된 버전

Stack/Queue는 추상 자료형이기 때문에 구현 방식은 자유

 

stack 스택 (후입선출, LIFO): 

  • insert_last(x) → 마지막에 넣기 (push)
  • delete_last() → 마지막에서 꺼내기 (pop)

 

queue 큐 (선입선출, FIFO):

  • insert_last(x) → 마지막에 넣기 (enqueue)
  • delete_first() → 처음에서 꺼내기 (dequeue)



2-2. Set Interface 

Sequence about extrinsic order, set is about intrinsic order

Sequence는 외부적으로 부여된 순서를 다루고, Set은 데이터 자체에 내재된 키로 정해지는 순서를 다룬다

 

Maintain a set of items having unique keys (e.g., item x has key x.key)

Set은 각 아이템이 고유한 키를 가진다. (예: x라는 아이템은 x.key라는 식별자를 가짐)
이걸로 중복 없이 관리함

 

(Set or multi-set? We restrict to unique keys for now.)

Set에는 중복이 없는 Set과, 중복을 허용하는 Multi-set이 있는데, 지금은 중복 없는 Set만 이야기할 것이다

 

Often we let key of an item be the item itself, but may want to store more info than just key

보통은 아이템 값 자체를 키로 사용한다 (예: 숫자 3 자체가 키)
하지만 어떤 경우엔 키 외에도 추가 정보(예: 이름, 설명)를 같이 저장하고 싶을 수도 있다

 

Supports set operations:

 

Special case interfaces:

dictionary set without the Order operations

dictionary는 사실상 set처럼 동작하는데, 순서 관련 연산이 빠진 버전이다. 

순서가 중요하지 않고 키 → 값 매핑만 중요할 때의 인터페이스

myDict["apple"] = 3 → 여기서 apple이 key, 3이 value
하지만 순서는 신경 안 씀

 

In recitation, you will be asked to implement a Set, given a Sequence data structure.

보충 수업(recitation) 시간에, Sequence 자료구조만 주어진 상태에서 Set을 직접 구현하라는 과제가 나올 것이다

* recitation: 대학 수업에서 강의(lecture)는 교수님이 이론을 가르치는 시간

recitation(리사이트이션)은 조교(TA)나 조교수님이  학생들에게 문제를 풀게 하거나, 실습을 도와주거나, 과제 관련 설명을 하는 시간

 

 

3. Sequence Interface

이 번 강의에서는 sequence, set 중에 sequence interface를 좀 더 알아보자. 

데이터 구조표

Sequence Interface는 대표적으로 2가지로 나눌 수 있다. 

1. Array Sequence 

    다른 표현으로 Array-based Sequence, Static Sequence을 사용하기도 한다

2. Linked List Sequence 

    다른 표현으로 Pointer-based Sequence, Dynamic Sequence 용어을 사용하기도 한다

 

그럼 먼저 Array Sequence에 대해 알아보자.

3-1 Array Sequence (Static Array)

Array 메모리 구조 특징은? 

한 덩어리(block)로 연속된 메모리에 저장된다 

 

Array 메모리 관리 방식

크기를 정해 놓고 할당한다. 크기가 꽉 차면 더 큰 배열을 새로 만들어 복사한다

old 배열 메모리 해제된다

 

Array 장점 

  • 빠른 인덱스 접근: arr[i]는 O(1)
  • 메모리 주소들이 한 곳에 몰려 있어서 한 번 캐시할 때 인접 값들도 한꺼번에 올려줘서 CPU 캐시 친화적

Array 단점

  • 삽입/삭제 시 뒤로 밀거나 당겨야 → O(n)
  • 미리 큰 메모리를 잡거나, 늘릴 때 복사 비용 발

 

Array Sequence는 기본적으로 데이터 만큼만 Array 사이즈를 가진다.

예: 만약 데이터가 2개이면 

 

Array is great for static operations! get_at(i) and set_at(i, x) in Θ(1) time!

데이터를 읽거나, 수정하는 것은 Θ(1)으로 아주 빠르다

 

get_at(i) → i번째 값 읽기

 

set_at(i, x) → i번째 값 수정


이런 건 배열 사이즈를 바꿀 필요가 없으니 Θ(1) (= 즉시) 처리됨. 2칸 그대로임

 

But not so great at dynamic operations...
하지만 dynamic 작업에서는 새 값을 넣거나, 지우는 건 빠르지 않다
왜냐면 기존 배열은 아이템 갯수에 딱 맞게 만들어져서 새로 데이터를 넣거나 데이터를 지우면

배열 사이즈가 바뀌는 거라서 새 배열이 펼요해진다.

 

데이터가 3개가 됐을 시 3개짜리 배열로 복사 이동

 

 

데이터가 2개가 됐을 시 다시 2개짜리 배열로 복사 이동

 

 

(For consistency, we maintain the invariant that array is full)

일관성 유지를 위해 배열은 항상 빈 공간 없이 꽉 차 있어야 한다는 불변 조건을 유지한다
즉 아이템이 10개이면 array도 10칸. 이렇게 항상 꽉 채운 상태를 유지한다. 

 

Then inserting and removing items requires:

이런 조건에서 삽입이나 삭제를 하려면

 

– reallocating the array

새 크기의 배열을 다시 할당(reallocate)해야 함

예: 크기 5짜리 배열에 하나 더 넣으려면 크기 6짜리 새 배열을 만들어야 함.

 

– shifting all items after the modified item

중간에 넣거나 빼면 그 뒤에 있는 모든 아이템을 이동 시켜야 함.
예: [A, B, C, D] 에서 B와 C 사이에 X를 넣으면 → [A, B, X, C, D],
C, D는 한 칸씩 뒤로 밀려야 함.

 

이 것을 시간 복잡도로 나타내면 다음과 같다

 

 

3-2 Linked List Sequence 

 

Pointer data structure (this is not related to a Python “list”)

포인터 기반 자료구조 (예: Linked List) 
※ 주의: Python의 list는 배열 기반이라 이거랑 다름!

 

Each item stored in a node which contains a pointer to the next node in sequence

각 데이터는 노드(node)라는 작은 박스 안에 저장되고, 그 노드 안에는 다음 노드를 가리키는 포인터가 들어 있어.
예: A → B → C → D 

 

Each node has two fields: node.item and node.next

각 노드에는 다음 2 부분으로 나눠어 있음

  • item: 실제 데이터 값
  • next: 다음 노드를 가리키는 포인터

Can manipulate nodes simply by relinking pointers!
포인터만 다시 연결(relink)하면 노드들 사이를 쉽게 수정할 수 있다
중간에 새 노드 넣을 때, 앞 노드의 next만 새로 바꿔주면 됨.

 

Maintain pointers to the first node in sequence (called the head)
이 구조의 시작점을 head 라고 부른다
head → 첫 번째 노드
이걸 잃어버리면 리스트 전체를 못 찾음!

 

Can now insert and delete from the front in Θ(1) time! Yay!
맨 앞(head)에서 삽입/삭제는 포인터 한두 개만 바꾸면 되니까
매우 빠름 → Θ(1) (즉시 처리)

 

 

 

(Inserting/deleting efficiently from back is also possible; you will do this in PS1)
맨 뒤에서도 빠르게 삽입/삭제하려면 tail을 추가하면 가능하다
이건 PS1(Problem Set 1) 과제에서 해볼 것이다

Tail이 없이 head(첫 노드)만 알고 있는 경우 맨 뒤(back)로 가려면

맨 앞부터 끝까지 하나씩 따라가야 한다.

  • 맨 앞에 넣거나 빼는 건 → 그냥 head만 조작하면 되니까 Θ(1)
  • 맨 뒤에 넣거나 빼려면 → 끝까지 가야 하니까 O(n) :(

하지만 tail을 추가하면 head뿐 아니라 tail도 따로 기억한다

그러면 마지막 노드도 O(1)으로 바로 알 수 있다. 

 

맨 끝에 삽입 - O(1)

[A]:head → [B] → [C] → [D]:tail → None

[D].next -> [E]로 설정

tail이 E로 업데이트

[A]:head → [B] → [C] → [D] → [E]:tail →None

시간 복잡도: O(1) tail만 알면 되니까!

 

뒤에서 삭제 - O(n)

[A]:head → [B] → [C] → [D] → [E]:tail →None

여기서 맨 뒤 [E]를 삭제하려면 앞 노드 [D]를 찾아야 한다. 

 

단순 연결 리스트는 각 노드가 다음만 알고 있으므로, D가 E를 가리키고 있는 걸 찾으려면
head부터 쭉 따라가야 한다

 

1. head [A]부터 시작해서 [A] → [B] → [C] → [D] → [E]

2. D.next == E인 노드를 찾으면 

3. D.next = None으로 설정한다 

4. tail이 D로 업데이트된다.

마지막 앞 노드를 찾는 데 걸리는 시간 head부터 찾아가야하므로 O(n) 

 

tail을 바로 지울 수 없는 이유

[E]가 tail인 것을 알아도, 각 노드는 자기 다음 노드만 알고 있고, 이 전의 노드는 알지 못함

[D] → [E] (O)

[D] <- [E] (X)

그래서 [E] 전에 [D]라는 것을 알 수 없어서 [D].next를 지울 수 없음. 

[D].next가 여전히 [E]를 가리키고 있기에 메모리상 [E]는 남아 있음 

그래서 head부터 순서대로 찾아야 하니 O(n)

 

왜 그냥 tail만 지우면 안 되나요?

tail 변수는 리스트의 끝을 가리키는 포인터일 뿐, 실제 리스트의 연결 관계(next)를 바꾸지는 않음.

즉, 연결을 끊어야 진짜 삭제한 것.

 

만약 doubly linked list(이중 연결 리스트)였다면?

각 노드가 prev도 알고 있어서 tail.prev.next = None

O(1) 쌉가능

 

 

But now get_at(i) and set_at(i, x) each take O(n) time... :(
하지만 i번째 요소를 읽거나 수정하려면,

맨 앞(head)부터 차례로 따라가야 하니까 → O(n) 시간이 걸린다 ㅠ
배열처럼 바로 인덱스로 접근 불가능! 포인터 타고 가야함 

 

Can we get the best of both worlds? Yes! (Kind of...)
그럼 배열의 빠른 인덱스 접근 + 링크드 리스트의 빠른 삽입/삭제

둘 다 얻을 수 있는 방법이 있을까? 응, 어느 정도는 가능하다.
이제 배울 동적 배열(Dynamic Array)과,

양방향으로 왔다 갔다 할 수 있는 이중 연결 리스트(Doubly Linked List) 같은

하이브리드 자료구조들이 대안이 된다

해드를 알기 때문에 맨 처음에 삽입, 삭제는 O(1)로 가능 

 

Linked List 단점 - 메모리 관점 

  • 노드들이 메모리 여기저기 흩어져 있어서, 다음 노드로 이동할 때마다 새로운 메모리 주소를 찾으러 감.
  • 캐시가 잘 못 도와줌 → 캐시 미스(cache miss) 발생 → 느려짐.

 

3-3. Dynamic Array Sequence 

앞에서 Static Array Sequence를 살펴보았다.

Static Array Sequence는 데이터를 읽거나, 데이터 교체는 빨리 할 수 있지만, 

데이터를 추가하거나 삽입할 때는 매 번 새 배열로 이사를 가야해서 오래 걸렸다. 

이 단점을 보안하기 위해 나온 것이 Dynamic Array이다. 

 

Make an array efficient for last dynamic operations
마지막 부분에서의 동적 작업(추가, 삭제)에 대해 배열을 효율적으로 만들자 

 

Python “list” is a dynamic array
Python의 list 자료형은 동적 배열(dynamic array)이다. 

 

Idea! Allocate extra space so reallocation does not occur with every dynamic operation
아이디어! 매번 데이터 추가, 삭제 같은 동적 작업있을 때 배열을 그 때 그 때 늘리거나 줄여서 새로 만들지 말고

미리 여유 공간을 확보해 두자
그래야 새 아이템이 들어와도 매번 새 배열로 복사할 필요 없다

 

Fill ratio: 0 ≤ r ≤ 1 the ratio of items to space
fill ratio : 배열의 채워진 정도.
예: 배열 크기가 10이고, 5개만 채워져 있으면 → r=0.5

 

Whenever array is full (r = 1), allocate Θ(n) extra space at end to fill ratio r_i (e.g., 1/2)
배열이 꽉 찼을 때 r=1, 한 번에 Θ(n) 만큼 여유 공간을 새로 만들어서 fill ratio r_i (예: 1/2)로 맞춰준다
앞으로 여러 개 추가될 걸 예상해서 한 번에 2배씩 늘림

r= 1: 배열이 꽉 찼을 때

r= 0.5 배열이 절반만 찼을 때

 

Will have to insert Θ(n) items before the next reallocation
이렇게 한 번 크게 늘리면, 다음에 크기를 늘리기 전까지 Θ(n)개 아이템을 추가할 수 있음

 

A single operation can take Θ(n) time for reallocation
하지만 크기를 늘리는 순간에는 한 번에 Θ(n) 시간이 든다
왜냐하면 새 배열을 만들고, 기존 값들 복사해야 하기 때문이다

 

However, any sequence of Θ(n) operations takes Θ(n) time
하지만 Θ(n) 번의 연산을 하면, 총 시간도 Θ(n)이 된다. 

 

So each operation takes Θ(1) time “on average”
한 번 크게 비용을 치르고, 이후 여러 번은 공짜로 처리하니까 

한 번의 연산당 평균적으로(amortized) Θ(1) 시간만 든다고 본다

 

Amortized Analysis

단계 현재 배열 크기 현재 채운 아이템 수 추가 아이템 크기 늘림 발생? 비용 (복사 + 추가)

           
단계  현재 배열 크기 현재 채운 아이템 수 추가 아이템 크기 늘림 발생? 비용 (복사 + 추가)
1 1 0 +1 O(1) (no) 1
2 1 → 2 1 +1 O(1 + 1 copy) 2
3 2 2 +1 O(1) (no) 1
4 2 → 4 3 +1 O(1 + 2 copy) 3
5 4 4 +1 O(1) (no) 1
6 4 5 +1 O(1) (no) 1
7 4 → 8 6 +1 O(1 + 4 copy) 5
8 8 7 +1 O(1) (no) 1

 

총 비용 계산

  • 총 8번 추가 → 총 비용 = 1 + 2 + 1 + 3 + 1 + 1 + 5 + 1 = 15
  • 평균 (amortized) 비용 = 15 / 8 ≈ 1.875 ≈ O(1)

크기 늘리는 순간엔 비싸지만, 전체로 보면 평균은 일정하다!

 

Data structure analysis technique to distribute cost over many operations
자료구조 분석 기법 중 하나로, 특정 연산 하나하나의 큰 비용을 여러 번의 연산에 분산시켜 분석하는 기법.
비싼 순간이 있어도 전체 평균으로 보면 싸지는 지 봄 

 

Operation has amortized cost T(n) if k operations cost at most ≤ kT(n)
만약 k번의 연산이 총 비용 ≤ k × T(n) 안에서 끝난다면,
각 연산의 amortized (평균) 비용은 T(n) 이라 본다.
한두 번 비싼 연산 때문에 전체 평가가 깨지지 않게, 묶음으로 본다.

* T(n): 이 자료구조에서 연산의 평균 비용

 

“T(n) amortized” roughly means T(n) “on average” over many operations
"T(n) amortized" 라고 하면, 많은 연산을 평균내어 보면 대략 T(n)이라는 뜻.
몇 번은 O(n)이지만, 수백 번 반복하면 평균 O(1)처럼 동작.

 

Inserting into a dynamic array takes Θ(1) amortized time
동적 배열(dynamic array)에 값 넣으면 평균적으로 Θ(1) 시간 걸린다.
크기 늘리는 순간은 O(n)이지만, 전체 반복에 섞이면 amortized O(1)

 

More amortization analysis techniques in 6.046!
(MIT 강의 번호) 6.046 강의에서 더 다양한 amortization 분석 기법을 배울 수 있다!

 

Dynamic Array Deletion 

Delete from back? Θ(1) time without effort, yay!
배열 끝에서 삭제하는 것은 별다른 추가 작업 없이 Θ(1) 시간에 가능하다.

 

However, can be very wasteful in space. Want size of data structure to stay Θ(n)
하지만 이렇게 하면 공간을 매우 낭비할 수 있으므로 자료구조의 크기는 데이터 수(n)와 같은 Θ(n) 정도로 유지하고 싶다.

 

Attempt: if very empty, resize to r = 1. Alternating insertion and deletion could be bad...
시도: 너무 비어 있으면 배열 크기를 r = 1로 줄일 수 있겠지만, 삽입과 삭제를 번갈아 하면 비효율이 생길 수 있다.

 

Idea! When r < r_d, resize array to ratio r_i where r_d < r_i (e.g., r_d = 1/4, r_i = 1/2)

아이디어: 비율 r이 임계값 r_d보다 작아지면, 배열을 r_i 비율로 조정한다 (예: r_d = 1/4, r_i = 1/2).

배열이 점점 비어가서 채운 비율 r이 r_d보다 낮아지면 → 공간 낭비니까 배열 크기를 줄여야 한다.

줄이는 방식은 배열을 너무 꽉 채우지 않게 r_i 정도로 맞춘다.
즉, 배열 크기를 줄여서 남은 아이템들이 배열에서 약 r_i (예: 50%) 정도 차도록 맞춘다.
너무 딱 맞추면 (r = 1) 또 금방 리사이즈해야 해서 효율이 떨어지니까 여유 공간을 확보하는 거야.

 

r → 현재 배열의 “채워진 정도” (fill ratio)

r= 1: 배열이 꽉 찼을 때, r= 0.5 배열이 절반만 찼을 때

 

r_d (down threshold) → 배열이 너무 비었다고 판단하는 임계값
예: r_d = 1/4 → 배열이 25% 이하로 차 있으면 너무 비었다고 본다.

 

r_i (increase ratio) → 리사이즈 후 배열을 얼마나 채우도록 만들지 정하는 목표 비율
예: r_i = 1/2 → 배열 리사이즈 후, 배열을 50% 정도 차 있도록 조정한다.

 

예시 

 

  • 원래 배열 크기: 100
  • 아이템: 20개
  • r = 20/100 = 0.2 → r_d = 0.25보다 작음 → 리사이즈 필요!
  • 새로운 배열 크기: 20 / 0.5 = 40 (아이템 20개가 50% 채우도록 조정)

 

Then Θ(n) cheap operations must be made before next expensive resize
이렇게 하면 다음 고비용 리사이즈 전에 최소 Θ(n)개의 값싼 연산을 할 수 있게 된다.

 

Can limit extra space usage to (1 + ε)n for any ε > 0 (set r_d = 1 / (1 + ε), r_i = r_d+1/2)
추가 공간 사용을 (1 + ε)n 이하로 제한할 수 있으며, ε > 0일 때 rd와 ri 값을 적절히 설정하면 된다.

 

Dynamic arrays only support dynamic last operations in Θ(1) time
다이나믹 배열은 마지막 위치에서의 동적 연산만 Θ(1) 시간에 지원한다.

 

Python List append and pop are amortized O(1) time, other operations can be O(n)!
파이썬 리스트의 append와 pop은 amortized(평균) O(1) 시간이지만, 다른 연산들은 O(n) 시간이 걸릴 수 있다.

 

(Inserting/deleting efficiently from front is also possible; you will ...)
(앞쪽에서의 삽입과 삭제도 효율적으로 구현할 수 있으며, 이후에 이를 배우게 될 것이다.)

 

 


 

출처 

강의 자료 https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/resources/mit6_006s20_lec2/

강의 https://youtu.be/CHhwJjR0mZA?si=wRabHIlgM4hwjxDK

MIT introduction to Algorithm - Lecture 2