고급 자료구조: 해시맵, 셋, 트리, 힙 완벽 가이드

📌 학습 목표

• 중급 자료구조의 특성과 동작 원리 이해
• 해시 기반, 트리 기반, 힙 기반 구조의 차이점 학습
• 각 자료구조의 시간/공간 복잡도 분석
• 실무에서의 적절한 자료구조 선택 기준 습득

---

📝 개념 정리

1. 해시맵 (Hash Map)

핵심 원리:

• 해시 함수를 통해 키를 인덱스로 변환하여 키-값 쌍 저장
• 평균 시간복잡도: O(1) - 탐색, 삽입, 삭제
• 최악 시간복잡도: O(n) - 모든 키가 같은 해시값을 가질 때
• 공간복잡도: O(n)

해시 충돌 해결 방법:

1. 체이닝 (Chaining): ```cpp class HashMapChaining { private: vector<list<pair<int, string»> table; int size;

   int hashFunction(int key) { return key % size; }

public: HashMapChaining(int s) : size(s) { table.resize(size); }

void insert(int key, string value) {
    int index = hashFunction(key);
    
    // 기존 키 업데이트 확인
    for (auto& pair : table[index]) {
        if (pair.first == key) {
            pair.second = value;
            return;
        }
    }
    
    // 새 키-값 쌍 추가
    table[index].push_back({key, value});
}

string search(int key) {
    int index = hashFunction(key);
    for (auto& pair : table[index]) {
        if (pair.first == key) {
            return pair.second;
        }
    }
    return "";  // 키를 찾지 못함
} }; ```

1. 개방 주소법 (Open Addressing):

class HashMapOpenAddressing {
private:
    vector<pair<int, string>> table;
    vector<bool> deleted;
    int size;
    
    int hashFunction(int key) {
        return key % size;
    }
    
    int linearProbe(int key) {
        int index = hashFunction(key);
        while (table[index].first != -1 && table[index].first != key) {
            index = (index + 1) % size;
        }
        return index;
    }
    
public:
    HashMapOpenAddressing(int s) : size(s) {
        table.resize(size, {-1, ""});
        deleted.resize(size, false);
    }
    
    void insert(int key, string value) {
        int index = linearProbe(key);
        table[index] = {key, value};
        deleted[index] = false;
    }
};

2. 셋 (Set)

핵심 원리:

• 중복을 허용하지 않는 원소들의 집합
• 일반적으로 트리 기반(Red-Black Tree) 또는 해시 기반 구현
• 시간복잡도: O(log n) - 트리 기반, O(1) - 해시 기반

C++ STL 예제:

#include <set>
#include <unordered_set>

// 트리 기반 set (정렬된 상태 유지)
set<int> orderedSet;
orderedSet.insert(3);
orderedSet.insert(1);
orderedSet.insert(4);
// 결과: {1, 3, 4}

// 해시 기반 unordered_set (정렬되지 않음, 더 빠름)
unordered_set<int> hashSet;
hashSet.insert(3);
hashSet.insert(1);
hashSet.insert(4);
// 결과: 순서 보장 안됨

// 집합 연산
set<int> setA = {1, 2, 3, 4};
set<int> setB = {3, 4, 5, 6};
set<int> result;

// 교집합
set_intersection(setA.begin(), setA.end(),
                 setB.begin(), setB.end(),
                 inserter(result, result.begin()));
// 결과: {3, 4}

3. 트리 (Tree)

이진 탐색 트리 (Binary Search Tree):

• 왼쪽 자식 < 부모 < 오른쪽 자식 속성 유지
• 평균 시간복잡도: O(log n)
• 최악 시간복잡도: O(n) - 편향 트리일 때

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

class BST {
private:
    TreeNode* root;
    
    TreeNode* insert(TreeNode* node, int val) {
        if (!node) return new TreeNode(val);
        
        if (val < node->val) {
            node->left = insert(node->left, val);
        } else if (val > node->val) {
            node->right = insert(node->right, val);
        }
        return node;
    }
    
    TreeNode* search(TreeNode* node, int val) {
        if (!node || node->val == val) return node;
        
        if (val < node->val) {
            return search(node->left, val);
        }
        return search(node->right, val);
    }
    
    TreeNode* findMin(TreeNode* node) {
        while (node->left) node = node->left;
        return node;
    }
    
    TreeNode* deleteNode(TreeNode* node, int val) {
        if (!node) return node;
        
        if (val < node->val) {
            node->left = deleteNode(node->left, val);
        } else if (val > node->val) {
            node->right = deleteNode(node->right, val);
        } else {
            // 삭제할 노드 발견
            if (!node->left) {
                TreeNode* temp = node->right;
                delete node;
                return temp;
            } else if (!node->right) {
                TreeNode* temp = node->left;
                delete node;
                return temp;
            }
            
            // 두 자식 모두 있는 경우
            TreeNode* temp = findMin(node->right);
            node->val = temp->val;
            node->right = deleteNode(node->right, temp->val);
        }
        return node;
    }
    
public:
    BST() : root(nullptr) {}
    
    void insert(int val) {
        root = insert(root, val);
    }
    
    bool search(int val) {
        return search(root, val) != nullptr;
    }
    
    void remove(int val) {
        root = deleteNode(root, val);
    }
};

자가 균형 트리 (Self-Balancing Trees):

• AVL 트리: 모든 노드의 좌우 서브트리 높이 차이 ≤ 1
• Red-Black 트리: 색상 규칙으로 균형 유지 (C++ STL map/set 내부 구현)

4. 힙 (Heap)

핵심 원리:

• 완전 이진 트리 기반의 자료구조
• 최대 힙: 부모 노드 ≥ 자식 노드
• 최소 힙: 부모 노드 ≤ 자식 노드
• 우선순위 큐 구현에 주로 활용

class MinHeap {
private:
    vector<int> heap;
    
    void heapifyUp(int index) {
        if (index == 0) return;
        
        int parent = (index - 1) / 2;
        if (heap[parent] > heap[index]) {
            swap(heap[parent], heap[index]);
            heapifyUp(parent);
        }
    }
    
    void heapifyDown(int index) {
        int left = 2 * index + 1;
        int right = 2 * index + 2;
        int smallest = index;
        
        if (left < heap.size() && heap[left] < heap[smallest]) {
            smallest = left;
        }
        
        if (right < heap.size() && heap[right] < heap[smallest]) {
            smallest = right;
        }
        
        if (smallest != index) {
            swap(heap[index], heap[smallest]);
            heapifyDown(smallest);
        }
    }
    
public:
    void insert(int val) {
        heap.push_back(val);
        heapifyUp(heap.size() - 1);
    }
    
    int extractMin() {
        if (heap.empty()) throw runtime_error("Heap is empty");
        
        int root = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        
        if (!heap.empty()) {
            heapifyDown(0);
        }
        
        return root;
    }
    
    int peek() {
        if (heap.empty()) throw runtime_error("Heap is empty");
        return heap[0];
    }
    
    bool empty() {
        return heap.empty();
    }
};

---

💻 실무 활용 예제

1. 단어 빈도 계산 (해시맵 활용)

unordered_map<string, int> countWords(vector<string>& words) {
    unordered_map<string, int> frequency;
    
    for (const string& word : words) {
        frequency[word]++;
    }
    
    return frequency;
}

// 사용 예시
vector<string> document = {"apple", "banana", "apple", "cherry", "banana", "apple"};
auto freq = countWords(document);
// 결과: {"apple": 3, "banana": 2, "cherry": 1}

2. 우선순위 작업 스케줄러 (힙 활용)

struct Task {
    int priority;
    string description;
    
    // 우선순위가 높을수록 먼저 처리 (최대 힙)
    bool operator<(const Task& other) const {
        return priority < other.priority;
    }
};

class TaskScheduler {
private:
    priority_queue<Task> taskQueue;
    
public:
    void addTask(int priority, string description) {
        taskQueue.push({priority, description});
    }
    
    Task getNextTask() {
        if (taskQueue.empty()) {
            throw runtime_error("No tasks available");
        }
        
        Task nextTask = taskQueue.top();
        taskQueue.pop();
        return nextTask;
    }
    
    bool hasTasks() {
        return !taskQueue.empty();
    }
};

3. 중복 제거와 정렬 (셋 활용)

vector<int> removeDuplicatesAndSort(vector<int>& nums) {
    set<int> uniqueNums(nums.begin(), nums.end());
    return vector<int>(uniqueNums.begin(), uniqueNums.end());
}

// 사용 예시
vector<int> input = {3, 1, 4, 1, 5, 9, 2, 6, 5};
vector<int> result = removeDuplicatesAndSort(input);
// 결과: {1, 2, 3, 4, 5, 6, 9}

---

🎯 연습 문제

1. LRU 캐시 구현 (해시맵 + 이중 연결 리스트)

class LRUCache {
private:
    struct Node {
        int key, value;
        Node* prev;
        Node* next;
        Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
    };
    
    unordered_map<int, Node*> cache;
    Node* head;
    Node* tail;
    int capacity;
    
    void addToHead(Node* node) {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }
    
    void removeNode(Node* node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }
    
public:
    LRUCache(int cap) : capacity(cap) {
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if (cache.find(key) != cache.end()) {
            Node* node = cache[key];
            removeNode(node);
            addToHead(node);
            return node->value;
        }
        return -1;
    }
    
    void put(int key, int value) {
        if (cache.find(key) != cache.end()) {
            Node* node = cache[key];
            node->value = value;
            removeNode(node);
            addToHead(node);
        } else {
            if (cache.size() >= capacity) {
                Node* last = tail->prev;
                removeNode(last);
                cache.erase(last->key);
                delete last;
            }
            
            Node* newNode = new Node(key, value);
            addToHead(newNode);
            cache[key] = newNode;
        }
    }
};

2. K개의 가장 빈번한 원소 찾기 (힙 활용)

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> frequency;
    for (int num : nums) {
        frequency[num]++;
    }
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
    
    for (auto& [num, freq] : frequency) {
        minHeap.push({freq, num});
        if (minHeap.size() > k) {
            minHeap.pop();
        }
    }
    
    vector<int> result;
    while (!minHeap.empty()) {
        result.push_back(minHeap.top().second);
        minHeap.pop();
    }
    
    return result;
}

---

🔎 심화 학습

고급 해시 기법

// Robin Hood Hashing - 더 균등한 분포
// Cuckoo Hashing - 최악의 경우에도 O(1) 보장
// Consistent Hashing - 분산 시스템에서 활용

고급 트리 구조

// B-Tree, B+ Tree - 데이터베이스 인덱스
// Trie (Prefix Tree) - 문자열 검색
// Segment Tree - 구간 쿼리 처리
// Fenwick Tree (Binary Indexed Tree) - 누적합 쿼리

자료구조 성능 비교표

자료구조	탐색	삽입	삭제	공간복잡도	특징
해시맵	O(1)	O(1)	O(1)	O(n)	순서 없음, 충돌 가능
트리맵	O(log n)	O(log n)	O(log n)	O(n)	정렬된 순서 유지
힙	O(n)	O(log n)	O(log n)	O(n)	최대/최소값 빠른 접근

---

🌐 외부 링크

• cppreference - STL Containers
• GeeksforGeeks - Data Structures
• Visualizing Data Structures

---

💡 실무 적용 팁

1. 자료구조 선택 기준:
   • 빈번한 탐색이 필요하면 해시맵 고려
   • 정렬된 데이터가 필요하면 트리맵 선택
   • 우선순위 처리가 필요하면 힙 활용
2. 성능 최적화:
   • 해시맵의 로드 팩터 관리 (0.75 이하 유지)
   • 트리의 균형 유지로 최악 성능 방지
   • 힙에서는 배열 기반 구현으로 캐시 효율성 향상
3. 메모리 관리:
   • 동적 할당 최소화
   • 메모리 풀 사용 고려
   • 참조 지역성 고려한 데이터 배치

---

다음 학습 주제

• 고급 트리: Trie, Segment Tree, Fenwick Tree
• 그래프 자료구조: 인접 리스트, 인접 행렬, Union-Find
• 문자열 자료구조: Suffix Array, Suffix Tree
• 확률적 자료구조: Bloom Filter, Count-Min Sketch

---

🪞 회고 질문

• 해시 충돌이 발생했을 때 어떤 해결 방법을 선택할 것인가?
• 힙과 트리의 차이점을 실무 상황에 맞춰 설명할 수 있는가?
• 대용량 데이터 처리 시 어떤 자료구조가 가장 적합할까?
• 메모리 제약이 있는 환경에서는 어떤 자료구조를 우선적으로 고려해야 할까?