Swift로 배우는
자료구조
"왜 이렇게 느려?" — 자료구조 하나 바꿨을 뿐인데 100배 빨라지는 경험.
10개 핵심 자료구조의 동작 원리를 시각화로 이해하고, Playground에서 직접 구현합니다.
기능은 동일합니다. 하지만 걸리는 시간은 전혀 다릅니다.
var seen: [String] = [] var duplicates: [String] = [] for name in allUsers { if seen.contains(name) { // O(n) 매번! duplicates.append(name) } seen.append(name) }
var seen: Set<String> = [] var duplicates: [String] = [] for name in allUsers { if !seen.insert(name).inserted { // O(1)! duplicates.append(name) } }
모양이 달라지면 같은 연산의 속도가 O(n)에서 O(1)로, O(n²)에서 O(n log n)으로 바뀝니다.
알고리즘을 아무리 최적화해도, 자료구조가 잘못되면 느릴 수밖에 없습니다.
// 정렬된 데이터에서 값 찾기 // Array + 선형탐색 → O(n) array.contains(target) // 맨 앞에 삽입이 잦은 경우 // Array → O(n) 매번 밀어야 함 array.insert(item, at: 0) // 최솟값을 반복적으로 꺼내기 // 정렬 안 된 Array → O(n) 매번 array.min()
// BST로 바꾸면 → O(log n) bst.search(target) // LinkedList → O(1) linkedList.prepend(item) // Heap → O(log n) heap.removeMin()
"개념은 알겠는데 실무에서 언제 쓰지?" — 각 자료구조가 실제로 쓰이는 구체적인 장면들입니다.
카드를 클릭하면 해당 챕터의 시각화로 이동합니다.
버튼을 눌러 삽입·삭제·탐색이 메모리/트리/그래프 위에서 어떻게 동작하는지 직접 관찰합니다.
시각화에서 확인한 동작을 직접 구현하고 실행해봅니다.
Array vs ContiguousArray
CoW(Copy-on-Write) 동작과 메모리 레이아웃의 차이를 시각적으로 확인합니다.
Swift의 Array를 복사했을 때 메모리는 어떻게 되는가?
검색 → Swift Array Copy-on-Write mechanismArray와 ContiguousArray는 언제 성능 차이가 나는가?
검색 → Swift ContiguousArray vs Array performance배열 끝에 추가하는 append()는 왜 O(1)이라고 하는가?
검색 → amortized time complexity array appendSwift의 Array는 값 타입이지만 내부적으로 힙 버퍼를 참조합니다. 복사를 해도 바로 메모리를 두 배로 쓰지 않고, 두 변수가 같은 버퍼를 공유합니다.
한쪽이 수정되는 순간 그때 비로소 버퍼를 복제합니다. 이를 CoW(Copy-on-Write)라고 합니다. 덕분에 불필요한 복사 비용을 줄일 수 있습니다.
ContiguousArray는 Obj-C 브릿징이 없어 항상 연속 메모리가 보장되고 성능이 더 예측 가능합니다.
- append() 를 눌러 배열 a에 원소를 추가하세요.
- b = a (복사) 를 누르면 b가 생깁니다. 아직 두 배열은 같은 메모리를 공유 중입니다.
- b.append() → CoW 발동 을 누르면 b가 수정되면서 버퍼가 실제로 복제되는 순간을 확인할 수 있습니다. 메모리 주소가 달라지는 것에 주목하세요.
var b = a 직후 b를 수정하지 않으면 메모리 사용량은 a 하나분인가 두 개분인가?
append()가 capacity를 넘어 재할당이 발생하면, 기존 데이터는 어디로 가는가?
ContiguousArray가 유리한 상황에서도 그냥 Array를 쓴다면 실제 성능 차이는 몇 %일까?
Linked List
노드가 포인터로 연결되는 구조. prepend/removeFirst는 O(1), 인덱스 접근은 O(n).
배열의 insert(at: 0)은 왜 느린가? 이 문제를 해결하는 자료구조는?
검색 → Swift LinkedList vs Array insert performance노드(Node)란 무엇이고 포인터는 어떤 역할을 하는가?
검색 → linked list node pointer conceptSwift에서 class와 struct의 차이가 연결 리스트 구현에 왜 중요한가?
검색 → Swift class reference type linked list각 노드가 값(value)과 다음 노드의 주소(next)를 함께 갖습니다. 배열과 달리 메모리가 연속되지 않아도 됩니다.
맨 앞(head)에 삽입·삭제는 포인터 하나만 바꾸면 되어 O(1)입니다. 반면 특정 인덱스에 접근하려면 head부터 순서대로 따라가야 하므로 O(n)입니다.
배열은 인덱스 접근이 빠르고, 연결 리스트는 앞쪽 삽입·삭제가 빠릅니다. 상황에 맞게 선택합니다.
- 숫자를 입력하고 prepend() 를 누르면 맨 앞에 추가됩니다. 기존 노드들이 오른쪽으로 밀리는 게 아니라 head 포인터만 바뀌는 것에 주목하세요.
- append() 는 맨 뒤에 추가합니다. 끝 노드까지 순회해야 해서 리스트가 길수록 느려집니다.
- removeFirst() 로 head를 제거하면 다음 노드가 head가 됩니다.
단방향 연결 리스트에서 "이전 노드"로 돌아가려면 어떻게 해야 하는가?
연결 리스트의 중간에서 삭제가 O(1)이라고 하는데, 해당 노드를 찾는 데 O(n)이 걸리면 실제로는 O(n) 아닌가?
Swift의 Array가 이미 충분히 빠른데, 연결 리스트를 직접 구현해야 하는 실무 상황이 있는가?
Stack / Queue
Stack은 LIFO, Queue는 FIFO. 이중 Stack으로 Queue를 amortized O(1)로 구현합니다.
iOS에서 "뒤로 가기"는 내부적으로 어떤 자료구조를 쓰는가?
검색 → UINavigationController stack push pop대기열(Queue)은 왜 배열의 removeFirst()로 구현하면 비효율적인가?
검색 → Swift Queue implementation Array removeFirst O(n)두 개의 Stack으로 Queue를 만들 수 있다는데, 어떻게 가능한가?
검색 → implement queue using two stacksStack은 책을 쌓는 것처럼 마지막에 넣은 것이 먼저 나옵니다(LIFO). 함수 호출 스택, undo/redo, 괄호 검사 등에 활용됩니다.
Queue는 줄 서기처럼 먼저 넣은 것이 먼저 나옵니다(FIFO). 이 시각화는 이중 Stack으로 Queue를 구현합니다. inbox에 쌓고, dequeue 시 outbox가 비어있으면 inbox를 통째로 뒤집어 옮겨 amortized O(1)을 달성합니다.
- [Stack] 숫자를 입력하고 push() 를 여러 번 누르세요. 쌓이는 방향을 확인합니다.
- [Stack] pop() 을 누르면 가장 마지막에 쌓인 것부터 나옵니다.
- [Queue] enqueue() 를 여러 번 눌러 inbox에 원소를 채운 뒤 dequeue() 를 누르세요. outbox가 비어있을 때 inbox가 뒤집히는 순간을 관찰하세요.
Stack을 Array로 구현할 때 push/pop은 항상 O(1)인가? capacity를 넘기면 어떻게 되는가?
이중 Stack Queue에서 inbox→outbox 전환이 O(n)인데 왜 amortized O(1)이라고 하는가?
재귀 함수 호출도 Stack 구조라는데, 재귀가 너무 깊으면 어떤 문제가 발생하는가?
Deque
링 버퍼(Ring Buffer) 기반 양방향 큐. 앞/뒤 모두 O(1) 삽입/삭제.
Stack은 한쪽, Queue는 양쪽이지만 방향이 다르다. 양쪽 모두 삽입/삭제가 필요한 경우는?
검색 → Double-ended queue deque use cases링 버퍼(Ring Buffer)란 무엇이고 왜 Deque 구현에 적합한가?
검색 → circular buffer ring buffer implementation슬라이딩 윈도우 알고리즘에서 Deque는 어떤 역할을 하는가?
검색 → sliding window deque algorithmDeque(Double-Ended Queue)는 앞과 뒤 양방향에서 모두 O(1)로 삽입·삭제할 수 있는 자료구조입니다.
링 버퍼(Ring Buffer)로 구현합니다. 고정 크기 배열을 원형으로 사용해, head와 tail 포인터가 배열 끝에 도달하면 다시 처음으로 돌아옵니다. 메모리 이동 없이 O(1)이 가능한 이유입니다.
앞/뒤로 자유롭게 넣고 빼야 하는 슬라이딩 윈도우, 양방향 탐색 등에 적합합니다.
- pushFront() 와 pushBack() 을 번갈아 눌러보세요. 원형 배열의 head와 tail 포인터가 어느 방향으로 이동하는지 확인합니다.
- capacity(8)가 꽉 찰 때까지 계속 추가하면 어떻게 되는지 확인하세요.
- popFront() 와 popBack() 으로 양쪽에서 삭제해보세요. 포인터가 반대 방향으로 이동합니다.
링 버퍼가 꽉 찼을 때 원소를 더 추가하면 어떻게 처리해야 하는가?
일반 배열로 Deque를 구현하면 앞쪽 삽입/삭제가 O(n)인데, 링 버퍼로 O(1)이 되는 원리는?
Swift Collections의 Deque와 직접 구현한 링 버퍼 Deque의 차이는 무엇일까?
Binary Tree
전위/중위/후위 순회를 애니메이션으로 확인합니다. 방문 순서가 핵심입니다.
트리 구조는 어디에 쓰이는가? 파일 시스템, SwiftUI View 계층 외에 또 있는가?
검색 → binary tree real world applications iOS전위/중위/후위 순회의 차이가 실무에서 왜 중요한가?
검색 → tree traversal preorder inorder postorder use casesBFS와 DFS는 각각 언제 선택하는가?
검색 → BFS vs DFS when to use각 노드가 최대 2개의 자식(왼쪽, 오른쪽)을 가지는 트리입니다. 트리에 저장된 모든 노드를 방문하는 방법이 4가지 있습니다.
전위(Pre-order): 루트 → 왼쪽 → 오른쪽. 트리 복사에 유용합니다.
중위(In-order): 왼쪽 → 루트 → 오른쪽. BST에서 사용하면 정렬된 순서로 방문됩니다.
후위(Post-order): 왼쪽 → 오른쪽 → 루트. 자식 먼저 처리해야 할 때 씁니다.
레벨(BFS): 위층부터 가까운 노드 순서로 방문합니다.
- 순회 버튼을 클릭하면 노드가 방문 순서에 따라 하나씩 하이라이트됩니다. 아래 상태 바에 방문 순서가 표시됩니다.
- 전위 / 중위 / 후위 를 각각 눌러 결과 순서를 비교해보세요. 루트(1)가 언제 방문되는지 주목하세요.
- 레벨 순회(BFS) 는 나머지와 달리 깊이가 아닌 층(레벨) 기준으로 방문합니다.
중위 순회를 BST에 적용하면 정렬된 순서가 나오는 이유는?
후위 순회가 "자식을 먼저 처리"하는데, 이것이 필요한 실무 상황은? (힌트: 디렉토리 삭제)
트리의 높이(height)가 성능에 미치는 영향은?
Binary Search Tree
삽입 시 불변 조건(왼쪽 < 루트 < 오른쪽)을 유지하며 트리가 자라는 과정을 봅니다.
정렬된 배열에서 이진 탐색은 O(log n)인데, 삽입은? BST가 이 문제를 어떻게 해결하는가?
검색 → binary search tree insert search O(log n)BST가 한쪽으로 치우치면 왜 성능이 나빠지는가?
검색 → BST worst case skewed tree균형 트리(AVL, Red-Black)는 어떤 원리로 편향을 방지하는가?
검색 → balanced BST AVL tree rotation이진 탐색 트리(BST)는 왼쪽 자식 < 부모 < 오른쪽 자식 규칙을 항상 지킵니다. 이 덕분에 탐색 시 절반씩 범위를 줄여가며 O(log n)에 찾을 수 있습니다.
단, 삽입 순서가 나쁘면 한쪽으로 치우쳐(편향 트리) 최악 O(n)이 될 수 있습니다. 이를 막기 위해 AVL 트리, 레드-블랙 트리 같은 균형 트리를 사용합니다.
- 숫자를 입력하고 insert() 를 누르세요. 루트부터 크기를 비교하며 올바른 자리를 찾아 내려가는 과정을 봅니다.
- 큰 수만 계속 입력(예: 50, 60, 70, 80)하면 오른쪽으로만 치우친 편향 트리가 됩니다. 이때 탐색이 왜 느려지는지 생각해보세요.
- 숫자 입력 후 search() 를 누르면 루트에서부터 비교하며 좁혀가는 경로가 표시됩니다.
[1, 2, 3, 4, 5]를 순서대로 BST에 삽입하면 어떤 모양이 되는가? 이때 탐색 시간은?
BST의 삭제에서 "자식이 2개인 노드"를 삭제할 때 후속자(successor)를 쓰는 이유는?
Swift의 SortedSet이 내부적으로 어떤 트리를 쓸까?
Heap / Priority Queue
Min-Heap: 루트가 항상 최솟값. siftUp/siftDown 과정을 시각화합니다.
배열에서 최솟값을 찾으면 O(n)인데, O(1)로 가져올 수 있는 자료구조는?
검색 → min heap priority queue O(1) minimumHeap은 트리인데 왜 배열로 저장하는가?
검색 → heap array representation parent child indexiOS에서 우선순위가 있는 작업 관리(예: 네트워크 요청 우선순위)는 어떻게 구현하는가?
검색 → priority queue iOS task schedulingHeap은 완전 이진 트리로, Min-Heap은 부모가 항상 자식보다 작거나 같습니다. 루트가 항상 최솟값이므로 O(1)로 최솟값을 꺼낼 수 있습니다.
삽입: 배열 끝에 추가 후 부모와 비교하며 올라갑니다(siftUp).
삭제: 루트 제거 후 마지막 원소를 루트로 올리고 자식과 비교하며 내려갑니다(siftDown).
트리 형태이지만 배열로 저장합니다. 인덱스 i의 부모는 (i-1)/2, 자식은 2i+1, 2i+2입니다.
- 숫자를 입력하고 insert() 를 누르세요. 트리 맨 끝에 추가된 뒤, 부모보다 작으면 자리를 바꾸며 올라가는(siftUp) 과정을 봅니다.
- remove() 를 누르면 루트(최솟값)가 제거됩니다. 마지막 노드가 루트로 올라온 뒤 아래로 내려가며(siftDown) 힙 조건을 복구하는 과정을 관찰하세요.
- 아래 배열 표현에서 트리와 배열이 어떻게 대응되는지 확인하세요.
Min-Heap에서 두 번째로 작은 값은 반드시 루트의 자식에 있는가?
siftUp과 siftDown의 시간복잡도가 O(log n)인 이유는? (힌트: 트리의 높이)
Max-Heap으로 바꾸려면 비교 연산만 뒤집으면 되는가?
Graph
BFS와 DFS 탐색 경로를 애니메이션으로 비교합니다.
소셜 네트워크에서 "친구 추천"은 어떤 알고리즘으로 가능한가?
검색 → graph BFS friend recommendation algorithm그래프를 코드로 표현하는 방법은 몇 가지가 있는가?
검색 → adjacency list vs adjacency matrix네비게이션 앱의 최단 경로는 어떤 그래프 알고리즘을 쓰는가?
검색 → Dijkstra shortest path algorithmGraph는 노드(정점, Vertex)와 노드를 잇는 간선(Edge)으로 구성됩니다. 트리와 달리 사이클이 있을 수 있고 부모-자식 관계가 없습니다.
BFS(너비 우선 탐색): 큐를 사용해 시작 노드에서 가까운 이웃부터 탐색합니다. 최단 경로 탐색에 적합합니다.
DFS(깊이 우선 탐색): 스택(또는 재귀)을 사용해 한 방향으로 끝까지 파고든 뒤 되돌아옵니다. 경로 탐색, 사이클 감지에 적합합니다.
- BFS 탐색 을 눌러보세요. 노드 A에서 출발해 거리 1인 이웃, 거리 2인 이웃 순서로 방문합니다. 가까운 곳부터 퍼져나가는 물결 형태입니다.
- DFS 탐색 을 눌러보세요. 한 경로를 끝까지 파고든 뒤 막히면 돌아와 다른 경로로 이동합니다.
- 두 방법의 방문 순서를 비교하며 어떤 상황에 어떤 탐색이 유리한지 생각해보세요.
BFS가 최단 경로를 보장하는 조건은? (힌트: 가중치)
DFS로 사이클을 감지하는 원리는?
인접 리스트와 인접 행렬 중 어떤 것이 메모리 효율적인가? (간선이 적을 때 vs 많을 때)
Hash Table
해시 충돌과 Separate Chaining을 직접 관찰합니다.
Swift의 Dictionary가 어떻게 O(1)로 값을 찾는가?
검색 → hash table dictionary O(1) lookup mechanism서로 다른 키가 같은 위치에 매핑되면(충돌) 어떻게 처리하는가?
검색 → hash collision resolution chaining open addressingHashable 프로토콜은 왜 필요한가?
검색 → Swift Hashable protocol dictionary keyHash Table은 키(Key)를 해시 함수로 숫자(인덱스)로 변환해 배열에 저장합니다. 평균 O(1)로 삽입·탐색·삭제가 가능합니다. Swift의 Dictionary가 내부적으로 이 구조입니다.
서로 다른 키가 같은 인덱스로 매핑될 때 충돌(Collision)이 발생합니다. 이 시각화는 같은 버킷에 연결 리스트로 이어 붙이는 Separate Chaining으로 충돌을 해결합니다.
- 키와 값을 입력하고 insert(key, val) 을 눌러보세요. 키가 해시되어 어느 버킷에 저장되는지 확인합니다.
- 여러 키를 넣다 보면 같은 버킷에 두 개 이상 쌓이는 충돌이 발생합니다. 같은 버킷에 체인처럼 이어지는 것을 관찰하세요.
- 키를 입력하고 search(key) 를 누르면 해당 버킷을 찾아 체인을 순회하며 키를 찾는 과정을 확인합니다.
해시 함수가 모든 키를 같은 버킷에 매핑하면 성능이 어떻게 되는가?
Load Factor가 높아지면 왜 성능이 나빠지는가? rehashing은 언제 하는가?
struct를 Dictionary 키로 쓰려면 무엇이 필요한가?
Trie
자동완성 탐색 경로가 트리 위에서 빛나며 강조됩니다.
10만 개의 단어에서 "app"으로 시작하는 단어를 모두 찾으려면?
검색 → trie autocomplete prefix search algorithmTrie의 탐색이 단어 수와 무관하게 O(m)인 이유는?
검색 → trie time complexity word lengthiOS 키보드 자동완성은 내부적으로 어떤 자료구조를 쓸까?
검색 → iOS keyboard autocomplete data structureTrie(트라이)는 문자열을 문자 단위로 쪼개 트리에 저장합니다. 공통 접두어를 가진 단어들이 같은 경로를 공유하기 때문에 메모리를 절약합니다.
m글자 단어의 탐색이 O(m)으로, 단어 수와 무관합니다. 자동완성, 사전 검색, 오타 교정 등에 사용됩니다. iOS의 키보드 자동완성도 유사한 구조입니다.
- 입력란에 접두어(예: ap)를 입력하고 autocomplete(prefix) 를 누르세요. 해당 경로가 빛나며 그 아래에 있는 단어들이 표시됩니다.
- app, apple, apply가 루트~p~p까지 경로를 공유하는 것을 확인하세요. 이것이 Trie의 핵심입니다.
- 새 단어(예: apt)를 입력하고 insert(word) 를 누르면 기존 경로와 분기되는 지점에 새 노드가 추가됩니다.
Trie에서 "apple"을 삭제할 때 "app"은 남겨야 한다면 어떻게 처리하는가?
HashMap으로도 자동완성을 구현할 수 있는데, Trie가 더 나은 이유는?
Trie의 메모리 사용량을 줄이는 방법은? (힌트: 압축 Trie)