Post

알고리즘 [자료구조]

Posted
By your_full_name
45 min read
알고리즘 [자료구조]

자료구조의 종류

자료구조의 종류는 단순 구조, 선형 구조, 비선형 구조로 나뉜다.

  • 단순 구조 정수, 실수, 문자열, 논리

  • 선형 구조 배열, 연결 리스트, 스택, 큐

  • 비선형 구조 트리, 그래프

스택(Stack)

스택은 후입선출(LIFO, Last In First Out) 구조를 가진 자료구조입니다. 즉, 가장 나중에 삽입된 데이터가 가장 먼저 제거됩니다. 스택은 주로 배열(Array)이나 연결 리스트(Linked List)를 사용하여 구현합니다.

스택의 주요 연산

  1. Push: 데이터를 스택에 추가.
  2. Pop: 스택의 가장 위에 있는 데이터를 제거하고 반환.
  3. Peek (Top): 스택의 가장 위에 있는 데이터를 제거하지 않고 반환.
  4. IsEmpty: 스택이 비어 있는지 확인.
  5. Size: 스택에 포함된 데이터의 개수를 반환.

장점

  1. 간단한 구현
    • 스택은 구현이 간단하고 직관적입니다. 배열이나 연결 리스트를 사용해 쉽게 구현할 수 있습니다.
  2. 함수 호출 스택 관리
    • 함수 호출 시 발생하는 재귀 호출이나 프로세스 상태를 관리하는 데 유용합니다. 시스템 내부적으로 스택을 활용해 호출 순서를 추적합니다.
  3. 후입선출 구조의 적합성
    • 특정 상황(예: 웹 브라우저의 뒤로 가기, 수식 계산, 괄호 검사)에서 자연스럽게 문제 해결을 돕습니다.
  4. 메모리 활용 효율적
    • 메모리가 제한된 환경에서도 데이터의 추가와 제거가 상단에서만 이루어져 관리가 용이합니다.

단점

  1. 무작위 접근 불가
    • 스택에서는 가장 상단(top) 데이터만 접근할 수 있어, 특정 위치의 데이터를 확인하려면 전체 스택을 다루어야 하는 경우가 발생합니다.
  2. 크기 제한
    • 배열 기반 스택에서는 미리 크기를 설정해야 하며, 크기를 초과하면 Overflow가 발생합니다.
    • 연결 리스트 기반 스택에서는 메모리 사용량이 데이터 크기에 비례하여 증가합니다.
  3. 단방향 처리
    • LIFO 구조이기 때문에 순차적 처리 외에는 복잡한 작업에 적합하지 않습니다.
  4. 효율성 문제
    • 특정 응용 프로그램에서는 큐(Queue)나 데크(Deque)와 같은 다른 자료구조가 더 적합할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

#include <iostream>
#include <stack>

using namespace std;

int main(void)
{
    stack<int> s;
    s.push(3);
    s.push(6);
    s.push(5);
    s.pop();
    s.push(7);
    s.pop();

    while (!s.empty())
    {
        cout << s.top() << endl;
        s.pop();
    }
    return 0;
}

출력

1
2

6
3

큐(Queue)

큐(Queue)는 선입선출(FIFO, First In First Out) 구조를 가진 자료구조입니다. 즉, 가장 먼저 삽입된 데이터가 가장 먼저 제거됩니다. 큐는 배열(Array)이나 연결 리스트(Linked List)로 구현할 수 있으며, 운영 체제, 네트워킹, 시뮬레이션 등 다양한 분야에서 사용됩니다.

큐의 주요 연산

  1. push
    • 데이터를 큐의 뒤쪽(Rear)에 추가.
    • 예: q.push(10); → 10을 큐에 추가.
  2. pop
    • 큐의 앞쪽(Front)에 있는 데이터를 제거.
    • 반환값이 없으므로, 제거 전에 front()를 사용하여 값을 확인.
    • 예:
      1
2

      std::cout << q.front() << std::endl; // 큐의 앞쪽 데이터 확인
q.pop(); // 제거
  3. front
    • 큐의 앞쪽(Front) 데이터를 참조(읽기).
    • 예: int x = q.front(); → 큐의 앞 데이터를 변수에 저장.
  4. back
    • 큐의 뒤쪽(Rear) 데이터를 참조(읽기).
    • 예: int y = q.back(); → 큐의 마지막 데이터를 변수에 저장.
  5. empty
    • 큐가 비어 있는지 확인.
    • 예: if (q.empty()) { ... } → 큐가 비었을 때 조건 처리.
  6. size
    • 큐에 저장된 데이터의 개수를 반환.
    • 예: std::cout << q.size();

큐의 장점

  1. 순차적 처리
    • 데이터를 입력된 순서대로 처리하기 때문에 프로세스, 요청 처리 등 순차 처리가 필요한 문제에서 효율적입니다.
  2. 공정성 보장
    • FIFO 구조로 인해, 모든 데이터가 입력된 순서대로 처리되므로 공정한 처리가 가능합니다.
  3. 간단한 구현
    • 배열 또는 연결 리스트를 사용하여 쉽게 구현할 수 있습니다.
  4. 다양한 응용
    • 작업 스케줄링, 프린터 작업 대기열, 네트워크 요청 처리 등 여러 분야에서 활용됩니다.

큐의 단점

  1. 무작위 접근 불가
    • 큐는 FIFO 구조로 설계되어 있기 때문에 특정 인덱스의 데이터에 접근하려면 큐 전체를 탐색해야 합니다.
  2. 고정 크기 문제(배열 기반 큐)
    • 배열 기반 큐는 크기를 미리 정의해야 하므로, 초과 시 Overflow 문제가 발생할 수 있습니다. (해결책: 동적 배열 사용 또는 연결 리스트 기반 큐)
  3. 메모리 낭비(순환 큐 미사용 시)
    • 배열 기반 큐에서 요소가 제거되면 해당 공간이 비지만 다시 사용할 수 없기 때문에, 순환 큐로 구현하지 않으면 메모리 낭비가 발생할 수 있습니다.
  4. 복잡한 삽입/제거(연결 리스트 기반 큐) 연결 리스트를 사용하는 경우 포인터를 관리해야 하므로 상대적으로 구현이 복잡해질 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
#include <queue>
using namespace std;

int main(void)
{
    queue <int> q;
    q.push(3);
    q.push(6);
    q.push(5);
    q.pop();
    q.push(7);
    q.pop();

    while (!q.empty())
    {
        cout << q.front() << endl;
        q.pop();
    }
    return 0;
}

출력

1
2

5
7

연결 리스트(Linked List)

연결 리스트(Linked List)는 데이터를 노드 단위로 저장하며, 각 노드는 데이터를 저장하는 필드와 다음 노드의 주소(포인터)를 포함하는 자료구조입니다. 연결 리스트는 동적 크기를 가지며, 삽입 및 삭제 연산이 유연합니다.

연결 리스트의 주요 특징

  1. 동적 크기
    • 연결 리스트는 필요에 따라 크기가 동적으로 조정됩니다. 배열처럼 고정된 크기를 미리 설정할 필요가 없습니다.
  2. 구조
    • 단일 연결 리스트(Singly Linked List): 노드가 한 방향으로만 연결.
    • 이중 연결 리스트(Doubly Linked List): 노드가 양쪽으로 연결되어 이전 및 다음 노드를 참조 가능.
    • 원형 연결 리스트(Circular Linked List): 마지막 노드가 처음 노드와 연결.

장점

  1. 동적 메모리 관리
    • 배열과 달리 크기가 가변적이므로, 메모리를 효율적으로 사용할 수 있습니다.
  2. 빠른 삽입/삭제
    • 특정 위치에서의 삽입 및 삭제 연산이 효율적입니다(O(1), 참조를 알고 있는 경우).
  3. 메모리 낭비 감소
    • 데이터의 크기를 동적으로 조정하므로, 불필요한 메모리 낭비가 줄어듭니다.

단점

  1. 임의 접근 불가
    • 특정 인덱스에 접근하려면 처음부터 순차적으로 탐색해야 합니다(O(n)).
  2. 추가 메모리 사용
    • 각 노드가 데이터를 저장하는 외에 포인터를 추가로 저장해야 하므로 메모리 사용량이 늘어납니다.
  3. 구현 복잡성
    • 배열에 비해 구조와 구현이 더 복잡합니다.

주요 연산

  1. 삽입
    • push_back(value): 리스트의 끝에 값을 삽입.
    • push_front(value): 리스트의 앞에 값을 삽입.
    • insert(iterator, value): 지정한 위치에 값을 삽입.
  2. 삭제
    • pop_back(): 리스트의 마지막 값을 제거.
    • pop_front(): 리스트의 첫 번째 값을 제거.
    • erase(iterator): 지정된 위치의 값을 제거.
  3. 탐색 및 확인
    • front(): 첫 번째 값을 반환.
    • back(): 마지막 값을 반환.
    • empty(): 리스트가 비어 있는지 확인.
    • size(): 리스트의 크기를 반환.
  4. 정렬 및 조작
    • sort(): 리스트를 정렬.
    • reverse(): 리스트를 역순으로 변환.
    • unique(): 중복된 값을 제거.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <iostream>
#include <list>
using namespace std;

int main() {
    // 리스트 선언
    list<int> myList;

    // 값 삽입
    myList.push_back(10);   // 리스트 끝에 삽입
    myList.push_front(5);   // 리스트 앞에 삽입
    myList.push_back(15);

    cout << "List after push operations: ";
    for (int val : myList) {
        cout << val << " ";
    }
    cout << endl;

    // 값 삭제
    myList.pop_front();     // 앞의 값 제거
    cout << "List after pop_front: ";
    for (int val : myList) {
        cout << val << " ";
    }
    cout << endl;

    // 값 삽입 (특정 위치)
    auto it = myList.begin(); // 첫 번째 위치의 iterator
    myList.insert(it, 20);    // 첫 번째 위치에 20 삽입

    cout << "List after insert: ";
    for (int val : myList) {
        cout << val << " ";
    }
    cout << endl;

    // 리스트 정렬 및 역순 변환
    myList.push_back(10);    // 중복 값 추가
    myList.sort();           // 정렬
    cout << "List after sort: ";
    for (int val : myList) {
        cout << val << " ";
    }
    cout << endl;

    myList.reverse();        // 역순 변환
    cout << "List after reverse: ";
    for (int val : myList) {
        cout << val << " ";
    }
    cout << endl;

    // 중복 제거
    myList.unique();         // 연속된 중복 값 제거
    cout << "List after unique: ";
    for (int val : myList) {
        cout << val << " ";
    }
    cout << endl;

    return 0;
}

1
2
3
4
5
6

List after push operations: 5 10 15 
List after pop_front: 10 15 
List after insert: 20 10 15 
List after sort: 10 10 15 20 
List after reverse: 20 15 10 10 
List after unique: 20 15 10

해시 테이블(Hash Table)

해시 테이블은 키(Key)-값(Value) 쌍을 저장하고, 데이터를 효율적으로 검색, 삽입, 삭제할 수 있는 자료구조입니다. 키를 해시 함수(Hash Function)를 통해 해시 값으로 변환하여, 데이터를 특정 버킷(Bucket)에 저장합니다.

C++에서는 해시 테이블 구현을 위해 std::unordered_map을 제공합니다. 이는 해시 테이블 기반의 연관 컨테이너입니다.

장점

  1. 빠른 검색, 삽입, 삭제
    • 평균적으로 O(1)의 시간 복잡도.
  2. 유연한 키 타입
    • 문자열, 정수 등 다양한 키 타입을 지원.
  3. 중복 없는 키 관리
    • 동일한 키를 여러 번 삽입할 수 없으므로 데이터 무결성 보장.

단점

  1. 해시 충돌(Hash Collision)
    • 충돌 해결 방법(체이닝, 개방 주소법 등)에 따라 성능 저하 가능.
  2. 순서 보장 없음
    • 데이터가 삽입된 순서를 보장하지 않음(필요 시 std::map 사용).
  3. 해시 함수 설계 중요
    • 비효율적인 해시 함수는 성능에 악영향을 줄 수 있음.

주요 연산

  1. 삽입
    • insert(pair<Key, Value>): 키-값 쌍을 삽입.
    • emplace(Key, Value): 키-값 쌍을 삽입(더 효율적).
  2. 검색
    • find(Key): 해당 키의 반복자 반환(없으면 end() 반환).
    • operator[]: 키를 통해 값에 접근(없으면 기본값으로 초기화된 키-값 추가).
  3. 삭제
    • erase(Key): 해당 키를 삭제.
    • clear(): 모든 요소 삭제.
  4. 크기와 상태 확인
    • size(): 요소의 개수 반환.
    • empty(): 비어 있는지 확인.
  5. 기타
    • bucket_count(): 버킷의 개수 반환.
    • load_factor(): 현재 요소 수와 버킷 수의 비율 반환.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    // unordered_map 선언
    unordered_map<string, int> scores;

    // 데이터 삽입
    scores["Alice"] = 95;
    scores["Bob"] = 89;
    scores["Charlie"] = 92;
    scores.emplace("David", 85); // 효율적인 삽입

    // 데이터 출력
    cout << "Initial scores:" << endl;
    for (const auto& pair : scores) {
        cout << pair.first << ": " << pair.second << endl;
    }

    // 데이터 검색
    string searchKey = "Charlie";
    if (scores.find(searchKey) != scores.end()) {
        cout << searchKey << "'s score: " << scores[searchKey] << endl;
    } else {
        cout << searchKey << " not found!" << endl;
    }

    // 데이터 삭제
    scores.erase("Bob");

    cout << "\nScores after deletion:" << endl;
    for (const auto& pair : scores) {
        cout << pair.first << ": " << pair.second << endl;
    }

    // 상태 확인
    cout << "\nNumber of elements: " << scores.size() << endl;
    cout << "Is map empty? " << (scores.empty() ? "Yes" : "No") << endl;

    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Initial scores:
David: 85
Charlie: 92
Alice: 95
Bob: 89
Charlie's score: 92

Scores after deletion:
David: 85
Charlie: 92
Alice: 95

Number of elements: 3
Is map empty? No

해시 충돌 해결 방법
해시 충돌은 서로 다른 키가 동일한 해시 값(버킷)에 매핑될 때 발생합니다. 이를 해결하기 위한 주요 방법은 다음과 같습니다.

1. 분리 연결법(Chaining)
충돌이 발생한 해시 값의 버킷에 연결 리스트를 저장하여, 같은 해시 값에 매핑된 여러 데이터를 저장.

  • 장점
    • 간단하고 직관적.
    • 해시 테이블의 크기를 초과하여 데이터를 저장할 수 있음.
  • 단점
    • 추가 메모리 사용(포인터 관리).
    • 연결 리스트가 길어질 경우 검색 속도 저하.

2. 개방 주소법(Open Addressing)
충돌이 발생하면 동일한 해시 테이블 내에서 다른 빈 버킷을 찾는 방식.

2-1. 선형 탐사(Linear Probing)

  • 충돌 시 한 칸씩 순차적으로 탐색.
  • 단점: 클러스터링 문제로 인해 성능 저하 가능.

2-2. 이차 탐사(Quadratic Probing)

  • 충돌 시, i²(1, 4, 9, …) 간격으로 탐색.
  • 단점: 해시 테이블 크기가 소수가 아니면 모든 버킷에 접근하지 못할 가능성.

2-3. 이중 해싱(Double Hashing)

  • 2개의 독립적인 해시 함수를 사용하여 두 번째 해시 값을 탐색 간격으로 사용.
  • 장점: 클러스터링 문제를 최소화.

3. 해시 테이블 재해싱(Rehashing)

  • 해시 테이블이 가득 차거나 충돌이 잦아질 경우, 더 큰 크기의 테이블로 옮겨 모든 키를 다시 해시.
  • 장점: 충돌 문제 감소.
  • 단점: 재해싱 과정에서 비용 발생.

해시 테이블을 사용하는 경우

  1. 빠른 데이터 검색
    • 키를 통해 값을 O(1) 시간에 검색해야 하는 경우(예: 데이터베이스 인덱스).
  2. 중복 제거
    • 중복된 값을 효율적으로 제거해야 하는 경우(예: 중복 검사).
  3. 빈도 계산
    • 문자열이나 숫자의 빈도를 효율적으로 계산해야 하는 경우(예: 단어 빈도 분석).
  4. 키-값 매핑
    • 사용자 ID와 관련 데이터를 매핑하거나 캐시를 구현할 때.

트리(Tree)

트리는 계층적 구조를 가진 자료구조로, 하나의 루트 노드(Root Node)와 자식 노드(Child Node)들로 구성됩니다. 트리는 순환(Cycle)이 없는 연결 그래프로 간주될 수 있습니다.

C++ STL은 트리 자료구조를 직접 제공하지 않지만, 다양한 트리 유형을 구현하거나 사용할 수 있는 기반 컨테이너를 제공합니다. 가장 간단한 예로 이진 트리(Binary Tree)를 사용자 정의 클래스로 구현하거나, std::map(레드-블랙 트리 기반)을 활용할 수 있습니다.

장점

  1. 효율적인 탐색
    • 이진 탐색 트리(BST)의 경우 정렬된 데이터를 효율적으로 탐색 가능(O(log n), 균형 트리일 경우).
  2. 구조적 데이터 표현
    • 계층적 데이터를 표현하는 데 적합(예: 파일 시스템, 조직도).
  3. 메모리 효율적 관리
    • 연결 리스트를 활용해 동적 메모리 관리를 수행.
  4. 빠른 삽입과 삭제
    • 정렬된 데이터를 유지하면서 삽입/삭제가 배열에 비해 빠름.

단점

  1. 비균형 문제
    • 일반적인 이진 트리는 비균형 상태가 될 수 있어 성능 저하(O(n)) 가능.
    • 해결책: AVL 트리, 레드-블랙 트리 같은 균형 트리.
  2. 복잡한 구현
    • 트리 구조와 균형 유지를 위한 알고리즘이 비교적 복잡.
  3. 노드 접근 제약
    • 특정 노드를 탐색하려면 루트부터 시작해야 함.

트리의 주요 연산

  1. 삽입
    • 노드를 트리에 추가.
  2. 삭제
    • 특정 노드를 삭제.
  3. 탐색
    • 특정 값을 가진 노드를 찾음.
  4. 순회
    • 트리의 노드를 방문(DFS 기반의 전위, 중위, 후위 순회).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

#include <iostream>
using namespace std;

// 이진 트리 노드 구조체 정의
struct Node {
    int data;
    Node* left;
    Node* right;

    Node(int value) : data(value), left(nullptr), right(nullptr) {}
};

// 이진 트리 클래스 정의
class BinaryTree {
private:
    Node* root;

    // 중위 순회 (왼쪽, 루트, 오른쪽)
    void inorderTraversal(Node* node) {
        if (node == nullptr) return;
        inorderTraversal(node->left);
        cout << node->data << " ";
        inorderTraversal(node->right);
    }

public:
    BinaryTree() : root(nullptr) {}

    // 노드 삽입
    void insert(int value) {
        if (root == nullptr) {
            root = new Node(value);
            return;
        }

        Node* current = root;
        while (true) {
            if (value < current->data) {
                if (current->left == nullptr) {
                    current->left = new Node(value);
                    break;
                } else {
                    current = current->left;
                }
            } else {
                if (current->right == nullptr) {
                    current->right = new Node(value);
                    break;
                } else {
                    current = current->right;
                }
            }
        }
    }

    // 중위 순회 호출
    void displayInOrder() {
        inorderTraversal(root);
        cout << endl;
    }
};

int main() {
    BinaryTree tree;

    // 값 삽입
    tree.insert(10);
    tree.insert(5);
    tree.insert(15);
    tree.insert(3);
    tree.insert(7);

    // 중위 순회 출력
    cout << "In-order Traversal: ";
    tree.displayInOrder();

    return 0;
}

1

In-order Traversal: 3 5 7 10 15

그래프(Graph)

그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다. 그래프는 방향 그래프, 무방향 그래프, 가중치 그래프 등 여러 종류로 나뉩니다.

C++ STL에서 그래프는 직접 제공되지 않지만, std::vector와 std::list를 사용해 인접 리스트(Adjacency List) 형태로 구현합니다.

방향성에 따른 분류

  1. 무방향 그래프(Undirected Graph)
    • 간선이 방향을 가지지 않음.
    • 예: 친구 관계, 도로망.
  2. 방향 그래프(Directed Graph)
    • 간선이 방향성을 가짐.
    • 예: 웹페이지 링크, 작업 종속성.

간선 가중치에 따른 분류

  1. 가중 그래프(Weighted Graph)
    • 간선에 가중치가 부여된 그래프.
    • 예: 도로망에서 거리, 네트워크의 전송 시간.
  2. 비가중 그래프(Unweighted Graph)
    • 간선에 가중치가 없는 그래프.
    • 예: 단순한 친구 관계.

연결성에 따른 분류

  1. 연결 그래프(Connected Graph)
    • 모든 정점이 간선으로 연결되어 있음.
    • 예: 모든 도시가 도로로 연결된 지도.
  2. 비연결 그래프(Disconnected Graph)
    • 일부 정점이 간선으로 연결되지 않음.
    • 예: 네트워크 단절 상태.

특수 유형의 그래프

  1. 사이클 그래프(Cyclic Graph)
    • 하나 이상의 사이클(순환)을 포함한 그래프.
    • 예: 네트워크에서 패킷의 순환 경로.
  2. 비사이클 그래프(Acyclic Graph)
    • 순환을 포함하지 않는 그래프.
    • 예: 작업 종속성 그래프.
  3. 완전 그래프(Complete Graph)
    • 모든 정점이 서로 연결된 그래프.
    • 예: 모든 사람과 친구 관계를 맺은 SNS.
  4. 트리(Tree)
    • 비순환, 연결 그래프의 특별한 형태.
    • 예: 계층 구조, 조직도.

장점

  1. 복잡한 관계 표현
    • 정점과 간선을 활용하여 복잡한 네트워크를 표현 가능(예: 소셜 네트워크, 도시 지도).
  2. 다양한 유형 지원
    • 방향 그래프, 무방향 그래프, 가중 그래프 등으로 다양한 응용 가능.
  3. 효율적 탐색
    • BFS와 DFS 알고리즘으로 특정 노드나 경로를 탐색 가능.
  4. 최적 경로 문제 해결
    • 다익스트라, 플로이드-워셜 등의 알고리즘을 활용해 최단 경로 계산 가능.

단점

  1. 높은 메모리 사용량
    • 인접 행렬(Adjacency Matrix)을 사용할 경우 메모리 사용량이 O(V²)로 증가.
    • 대규모 그래프에서는 인접 리스트로 구현하여 해결 가능.
  2. 구현 복잡성
    • 탐색 및 경로 계산 알고리즘이 복잡(특히 가중 그래프).
  3. 사이클 관리 필요
    • 그래프에서 사이클 존재 여부를 확인하거나 제거하는 작업이 추가로 필요.

그래프의 주요 연산

  1. 삽입
    • 정점 추가, 간선 추가.
  2. 삭제
    • 정점 삭제, 간선 삭제.
  3. 탐색
    • BFS(너비 우선 탐색), DFS(깊이 우선 탐색).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

// 그래프 클래스 정의
class Graph {
private:
    int vertices;
    vector<vector<int>> adjList;

public:
    Graph(int v) : vertices(v), adjList(v) {}

    // 간선 추가
    void addEdge(int src, int dest) {
        adjList[src].push_back(dest);
        adjList[dest].push_back(src); // 무방향 그래프
    }

    // BFS 탐색
    void bfs(int start) {
        vector<bool> visited(vertices, false);
        queue<int> q;

        visited[start] = true;
        q.push(start);

        cout << "BFS Traversal: ";
        while (!q.empty()) {
            int current = q.front();
            q.pop();
            cout << current << " ";

            for (int neighbor : adjList[current]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }
        cout << endl;
    }
};

int main() {
    Graph g(5);

    // 간선 추가
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(1, 3);
    g.addEdge(1, 4);

    // BFS 탐색
    g.bfs(0);

    return 0;
}

출력

1

BFS Traversal: 0 1 2 3 4

그래프 활용 사례

  1. 네트워크: 패킷 전송 경로, 네트워크 구조.
  2. 지도: 도시 간 최단 경로 탐색.
  3. 소셜 네트워크: 친구 관계, 추천 시스템.
  4. 작업 스케줄링: 종속성을 가진 작업의 순서 결정(DAG 기반).

힙(Heap)

힙은 완전 이진 트리(Complete Binary Tree) 기반의 자료구조로, 최대 힙(Max-Heap)과 최소 힙(Min-Heap) 두 가지 유형이 있습니다.

  • 최대 힙: 부모 노드가 자식 노드보다 크거나 같음.
  • 최소 힙: 부모 노드가 자식 노드보다 작거나 같음. C++에서는 힙을 구현하기 위해 STL의 std::priority_queue를 사용합니다.

장점

  1. 효율적인 최댓값/최솟값 탐색
    • 최댓값/최솟값을 O(1) 시간에 반환 가능.
  2. 구조적 효율성
    • 삽입 및 삭제가 O(log n)으로 효율적.

단점

  1. 정렬된 순서 탐색 불가
    • 순서대로 정렬된 데이터를 얻으려면 추가 작업 필요.
  2. 비균형 트리 가능성 없음
    • 완전 이진 트리 구조를 유지하지만, 메모리 사용이 많아질 수 있음.

힙의 주요 연산

  1. 삽입 (O(log n)): 데이터를 힙에 삽입.
  2. 삭제 (O(log n)): 루트 노드 제거.
  3. 탐색 (O(1)): 루트 노드(최댓값 또는 최솟값) 반환.

예제 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <iostream>
#include <queue>
using namespace std;

int main() {
    // 최대 힙 (기본 설정)
    priority_queue<int> maxHeap;

    // 데이터 삽입
    maxHeap.push(10);
    maxHeap.push(20);
    maxHeap.push(15);

    // 최대값 출력 및 삭제
    cout << "Max-Heap:" << endl;
    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " "; // 최댓값 출력
        maxHeap.pop();                // 최댓값 삭제
    }
    cout << endl;

    // 최소 힙
    priority_queue<int, vector<int>, greater<int>> minHeap;

    minHeap.push(10);
    minHeap.push(20);
    minHeap.push(15);

    cout << "Min-Heap:" << endl;
    while (!minHeap.empty()) {
        cout << minHeap.top() << " "; // 최솟값 출력
        minHeap.pop();                // 최솟값 삭제
    }

    return 0;
}

집합(Set)

집합은 중복 없는 데이터를 저장하는 컨테이너입니다. C++에서는 std::set(이진 검색 트리 기반)과 std::unordered_set(해시 테이블 기반)을 제공합니다.

장점

  1. 중복 데이터 방지
    • 자동으로 중복된 데이터를 제거.
  2. 정렬 지원 (std::set)
    • std::set은 정렬된 상태로 데이터를 저장.

단점

  1. 메모리 사용량
    • std::unordered_set의 경우, 해시 충돌 방지를 위해 추가 메모리 사용.
  2. 정렬 불가 (std::unordered_set)
    • std::unordered_set은 순서를 보장하지 않음.

집합의 주요 연산

  1. 삽입 (O(log n) 또는 O(1))
    • 중복되지 않은 요소를 삽입.
  2. 삭제 (O(log n) 또는 O(1))
    • 특정 요소를 삭제.
  3. 탐색 (O(log n) 또는 O(1))
    • 특정 요소 존재 여부 확인.

집합 예제 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

#include <iostream>
#include <set>
#include <unordered_set>
using namespace std;

int main() {
    // 정렬된 집합
    set<int> sortedSet = {20, 10, 40, 30};

    cout << "Sorted Set:" << endl;
    for (int val : sortedSet) {
        cout << val << " "; // 자동 정렬된 데이터
    }
    cout << endl;

    // 삽입
    sortedSet.insert(25);
    cout << "After Insertion: ";
    for (int val : sortedSet) {
        cout << val << " ";
    }
    cout << endl;

    // 삭제
    sortedSet.erase(20);
    cout << "After Deletion: ";
    for (int val : sortedSet) {
        cout << val << " ";
    }
    cout << endl;

    // 해시 기반 집합
    unordered_set<int> hashSet = {20, 10, 40, 30};
    cout << "Unordered Set:" << endl;
    for (int val : hashSet) {
        cout << val << " "; // 순서 보장 없음
    }
    cout << endl;

    return 0;
}

맵(Map)

맵은 키(Key)와 값(Value)의 쌍을 저장하는 자료구조입니다. C++에서는 std::map(레드-블랙 트리 기반)과 std::unordered_map(해시 테이블 기반)을 제공합니다.

장점

  1. 키를 통한 빠른 접근
    • 특정 키를 통해 O(log n) 또는 O(1) 시간에 값에 접근 가능.
  2. 정렬 지원 (std::map)
    • 키를 기준으로 정렬된 상태 유지.

단점

  1. 메모리 사용량 증가
    • std::unordered_map은 해시 충돌 방지를 위해 추가 메모리 사용.
  2. 정렬 불가 (std::unordered_map)
    • 해시 테이블 기반으로 순서를 보장하지 않음.

맵의 주요 연산

  1. 삽입 (O(log n) 또는 O(1))
    • 키-값 쌍을 삽입.
  2. 삭제 (O(log n) 또는 O(1))
    • 특정 키를 삭제.
  3. 탐색 (O(log n) 또는 O(1))
    • 특정 키에 해당하는 값을 검색.

맵 예제 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#include <iostream>
#include <map>
#include <unordered_map>
using namespace std;

int main() {
    // 정렬된 맵
    map<string, int> sortedMap;

    sortedMap["Alice"] = 95;
    sortedMap["Bob"] = 89;
    sortedMap["Charlie"] = 92;

    cout << "Sorted Map:" << endl;
    for (const auto& pair : sortedMap) {
        cout << pair.first << ": " << pair.second << endl;
    }

    // 해시 기반 맵
    unordered_map<string, int> hashMap;

    hashMap["Alice"] = 95;
    hashMap["Bob"] = 89;
    hashMap["Charlie"] = 92;

    cout << "Unordered Map:" << endl;
    for (const auto& pair : hashMap) {
        cout << pair.first << ": " << pair.second << endl;
    }

    return 0;
}

트라이(Trie)

트라이는 문자열을 효율적으로 저장하고 검색하기 위해 사용하는 트리 기반의 자료구조입니다. 각 노드는 문자(character)를 저장하며, 문자열의 공통 접두사를 공유합니다. 이는 접두사 트리(Prefix Tree)라고도 불립니다.

트라이의 주요 특징

  1. 구조
    • 루트 노드에서 시작하며, 각 노드는 자식 노드와 연결되어 특정 문자를 저장.
    • 문자열의 끝을 나타내는 종단 표시(End of Word)를 포함.
  2. 주요 연산
    • 삽입 (Insert): 문자열을 트라이에 삽입.
    • 탐색 (Search): 특정 문자열이 존재하는지 확인.
    • 삭제 (Delete): 문자열 제거(선택적 구현).
    • 접두사 검색 (Prefix Search): 특정 접두사로 시작하는 모든 문자열 검색.

장점

  1. 빠른 검색
    • 문자열 길이에 비례한 시간 복잡도 O(m), m은 문자열 길이.
  2. 공통 접두사 활용
    • 저장 공간 절약(공통 접두사 공유).
  3. 자동 완성 및 제안
    • 접두사 기반 검색에 유용.

단점

  1. 메모리 사용량 증가
    • 각 문자마다 노드가 필요하여 메모리 소비가 많음.
  2. 복잡한 구현
    • 트리 노드와 자식 관계를 설정하는 코드가 복잡할 수 있음.

트라이 구현 예제 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

#include <iostream>
#include <unordered_map>
using namespace std;

// 트라이 노드 정의
class TrieNode {
public:
    unordered_map<char, TrieNode*> children;
    bool isEndOfWord;

    TrieNode() : isEndOfWord(false) {}
};

// 트라이 클래스 정의
class Trie {
private:
    TrieNode* root;

public:
    Trie() {
        root = new TrieNode();
    }

    // 문자열 삽입
    void insert(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                node->children[c] = new TrieNode();
            }
            node = node->children[c];
        }
        node->isEndOfWord = true;
    }

    // 문자열 탐색
    bool search(const string& word) {
        TrieNode* node = root;
        for (char c : word) {
            if (node->children.find(c) == node->children.end()) {
                return false;
            }
            node = node->children[c];
        }
        return node->isEndOfWord;
    }

    // 접두사 탐색
    bool startsWith(const string& prefix) {
        TrieNode* node = root;
        for (char c : prefix) {
            if (node->children.find(c) == node->children.end()) {
                return false;
            }
            node = node->children[c];
        }
        return true;
    }
};

int main() {
    Trie trie;
    trie.insert("apple");
    trie.insert("app");
    trie.insert("bat");

    cout << "Search 'apple': " << trie.search("apple") << endl; // true
    cout << "Search 'app': " << trie.search("app") << endl;     // true
    cout << "Starts with 'ap': " << trie.startsWith("ap") << endl; // true
    cout << "Search 'bat': " << trie.search("bat") << endl;     // true
    cout << "Search 'cat': " << trie.search("cat") << endl;     // false

    return 0;
}

출력결과

1
2
3
4
5

Search 'apple': 1
Search 'app': 1
Starts with 'ap': 1
Search 'bat': 1
Search 'cat': 0

분리집합(Disjoint Set, Union-Find)

분리 집합은 상호 배타적 집합(Disjoint Set)을 관리하는 자료구조로, 대표적으로 그래프에서 사이클 탐지와 최소 신장 트리(MST) 알고리즘에 사용됩니다.

분리 집합의 주요 연산

  1. Find:
    • 특정 원소가 속한 집합의 대표(루트)를 찾음.
    • 경로 압축(Path Compression) 기법을 사용해 탐색 시간 최적화.
  2. Union:
    • 두 집합을 하나로 합침.
    • 유니온 바이 랭크(Union by Rank) 기법을 사용해 트리 높이를 최소화.

장점

  1. 빠른 집합 연산
    • 경로 압축과 유니온 바이 랭크를 함께 사용하면 거의 O(1)의 시간 복잡도.
  2. 효율적인 사이클 검출
    • 그래프 알고리즘(예: Kruskal 알고리즘)에 매우 적합. 단점
  3. 메모리 사용량
    • 트리 구조를 관리하기 위한 추가 메모리 필요.
  4. 다양한 응용 제한
    • 집합 연산 외의 복잡한 작업에는 적합하지 않음.

분리 집합 예제 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

#include <iostream>
#include <vector>
using namespace std;

class DisjointSet {
private:
    vector<int> parent, rank;

public:
    // 초기화
    DisjointSet(int n) {
        parent.resize(n);
        rank.resize(n, 0);
        for (int i = 0; i < n; ++i) {
            parent[i] = i;
        }
    }

    // Find 연산 (경로 압축)
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // 경로 압축
        }
        return parent[x];
    }

    // Union 연산 (랭크 기반)
    void unionSets(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
};

int main() {
    DisjointSet ds(5);

    ds.unionSets(0, 1);
    ds.unionSets(1, 2);
    ds.unionSets(3, 4);

    cout << "Find(0): " << ds.find(0) << endl; // 0
    cout << "Find(1): " << ds.find(1) << endl; // 0
    cout << "Find(3): " << ds.find(3) << endl; // 3

    ds.unionSets(2, 3);

    cout << "Find(4): " << ds.find(4) << endl; // 0

    return 0;
}

출력 결과

1
2
3
4

Find(0): 0
Find(1): 0
Find(3): 3
Find(4): 0

참고 블로그

참고 링크

알고리즘, 자료구조
알고리즘
This post is licensed under CC BY 4.0 by the author.