5.3 비선형 자료 구조 (Non-Linear Data Structures)

5.3.1 그래프 (Graph)

그래프(Graph)는 정점(Vertex)과 간선(Edge)으로 이루어진 자료 구조

• 무방향 그래프 (Undirected Graph)
• 방향 그래프 (Directed Graph)
• 가중 그래프 (Weighted Graph)

C++ STL에서 그래프 구현

• 인접 리스트 (Adjacency List) → std::vector<std::list<int>>
• 인접 행렬 (Adjacency Matrix) → std::vector<std::vector<int>>

그래프의 시간 복잡도

표현 방법	메모리	간선 추가	간선 탐색
인접 행렬 (N×N)	O(N^2)	O(1)	O(1)
인접 리스트	O(N + M)	O(1)	O(N)

예제 vector를 활용한 그래프 구현 (인접 리스트)

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N = 5; // 정점 개수
    vector<vector<int>> graph(N);

    // 간선 추가 (무방향 그래프)
    graph[0].push_back(1);
    graph[1].push_back(0);
    graph[1].push_back(2);
    graph[2].push_back(1);

    // 출력
    for (int i = 0; i < N; i++) {
        cout << "노드 " << i << "의 인접 노드: ";
        for (int neighbor : graph[i]) {
            cout << neighbor << " ";
        }
        cout << endl;
    }

    return 0;
}

노드 0의 인접 노드: 1
노드 1의 인접 노드: 0 2
노드 2의 인접 노드: 1

• std::vector<std::vector<int>>를 사용해 인접 리스트 방식으로 그래프를 구현

---

5.3.2 트리 (Tree)

트리(Tree)는 부모-자식 관계를 가지는 계층적 자료 구조

• 이진 트리 (Binary Tree)
• 이진 탐색 트리 (BST, Binary Search Tree)
• 균형 트리 (AVL 트리, Red-Black 트리)

C++ STL에서 트리 구현

• 이진 탐색 트리 (BST) → std::set, std::map

트리의 시간 복잡도 (BST 기준)

연산	평균	최악
삽입 (insert())	O(log N)	O(N)
삭제 (erase())	O(log N)	O(N)
탐색 (find())	O(log N)	O(N)

예제 set을 이용한 이진 탐색 트리 (BST)

 

#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int> bst;

    bst.insert(10);
    bst.insert(5);
    bst.insert(15);

    cout << "BST 원소 출력: ";
    for (int x : bst) cout << x << " ";
    cout << endl;

    cout << "10이 존재하는가? " << (bst.find(10) != bst.end()) << endl;

    return 0;
}

BST 원소 출력: 5 10 15
10이 존재하는가? 1

• std::set은 Red-Black Tree 기반의 BST로 동작하며 O(log N)의 탐색

---

5.3.3 힙 (Heap)

힙(Heap)은 완전 이진 트리(Complete Binary Tree) 기반의 우선순위 자료 구조

• 최대 힙 (Max Heap) → 부모가 자식보다 크다.
• 최소 힙 (Min Heap) → 부모가 자식보다 작다.

C++ STL에서 힙 구현

• std::priority_queue 사용

힙의 시간 복잡도

연산	시간 복잡도
삽입 (push())	O(log N)
삭제 (pop())	O(log N)
최댓값 조회 (top())	O(1)

예제 코드: std::priority_queue 사용

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> maxHeap;
    
    maxHeap.push(30);
    maxHeap.push(10);
    maxHeap.push(20);

    cout << "최댓값: " << maxHeap.top() << endl;

    return 0;
}

• std::priority_queue는 기본적으로 최대 힙을 제공한다.

---

5.3.4 우선순위 큐 (Priority Queue)

우선순위 큐(Priority Queue)는 가장 우선순위가 높은 요소를 먼저 처리하는 큐
C++ STL에서 std::priority_queue를 사용하여 쉽게 구현

우선순위 큐의 시간 복잡도

연산	시간 복잡도
삽입 (push())	O(log N)
삭제 (pop())	O(log N)
조회 (top())	O(1)

예제 priority_queue

 

#include <iostream>
#include <queue>

using namespace std;

int main() {
    priority_queue<int> pq;

    pq.push(10);
    pq.push(20);
    pq.push(5);

    cout << "최댓값: " << pq.top() << endl;

    pq.pop();
    cout << "pop() 후 최댓값: " << pq.top() << endl;

    return 0;
}

최댓값: 20
pop() 후 최댓값: 10

• priority_queue는 최대 힙(Max Heap)을 기본으로 사용하여, 가장 큰 값을 top()에서 반환
• push() 및 pop() 연산은 O(log N)의 시간 복잡도

우선순위 큐를 최소 힙으로 사용하는 방법

priority_queue<int, vector<int>, greater<int>> minPQ;

• greater<int>을 사용하면 최소 힙(Min Heap)

 

---

5.3.5 맵 (Map)

맵(Map)은 (Key, Value) 쌍으로 이루어진 자료 구조

• 정렬된 맵 (Ordered Map) → std::map (BST 기반)
• 해시 맵 (Unordered Map) → std::unordered_map (해시 테이블 기반)

맵의 시간 복잡도

연산	std::map (O(log N))	std::unordered_map (O(1))
삽입 (insert())	O(log N)	O(1)
삭제 (erase())	O(log N)	O(1)
탐색 (find())	O(log N)	O(1)

예제 코드: std::map 사용

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<string, int> scores;

    scores["Alice"] = 90;
    scores["Bob"] = 80;

    cout << "Alice 점수: " << scores["Alice"] << endl;

    return 0;
}

---

5.3.6 셋 (Set)

셋(Set)은 중복을 허용하지 않는 자료 구조
C++ STL에서는 std::set과 std::unordered_set을 제공

셋의 유형

• 정렬된 셋 (Ordered Set) → std::set (Red-Black Tree 기반, 자동 정렬)
• 해시 셋 (Unordered Set) → std::unordered_set (해시 테이블 기반, 순서 없음)

셋의 시간 복잡도

연산	std::set (O(log N))	std::unordered_set (O(1))
삽입 (insert())	O(log N)	O(1)
삭제 (erase())	O(log N)	O(1)
탐색 (find())	O(log N)	O(1)

예제 코드: std::set 사용

 

#include <iostream>
#include <set>

using namespace std;

int main() {
    set<int> orderedSet;

    orderedSet.insert(20);
    orderedSet.insert(10);
    orderedSet.insert(30);

    cout << "정렬된 셋: ";
    for (int x : orderedSet) cout << x << " ";
    cout << endl;

    return 0;
}

• std::set은 자동 정렬되며, 중복 원소를 허용하지 않는다.

5.3.7 해시 테이블 (Hash Table)

해시 테이블(Hash Table)은 Key를 해싱(Hashing)하여 저장하는 자료 구조
C++ STL에서는 std::unordered_map을 제공

해시 테이블의 시간 복잡도

연산	시간 복잡도
삽입	O(1) (평균) / O(N) (최악)
삭제	O(1) (평균) / O(N) (최악)
탐색	O(1) (평균) / O(N) (최악)

예제 unordered_map

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
    unordered_map<string, int> hashTable;
    hashTable["apple"] = 1;
    hashTable["banana"] = 2;

    cout << "apple의 값: " << hashTable["apple"] << endl;

    return 0;
}