C++ CS

[자료구조] 기본 자료구조 정리

Posted by DHniyeo Blog on April 28, 2024

개요

각 자료구조의 특징과 예시를 알아보기 위해 한번 정리해 보았다.

1. 배열 (Array)

  • 특징:
    • 고정된 길이의 요소를 저장
    • 인덱스를 이용하여 빠른 랜덤 접근 가능 (O(1))
    • 순차적 접근 불편
    • 추가/삭제 비효율적 (O(n))
  • 장점:
    • 랜덤 접근 속도 빠름
    • 메모리 할당 방식 간단
  • 단점:
    • 길이 변경 불가능
    • 추가/삭제 비효율적
    • 메모리 낭비 가능성 있음
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

#include <iostream>

using namespace std;

int main() {
  // 정수형 배열 선언 및 초기화
  int numbers[5] = {10, 20, 30, 40, 50};

  // 배열 요소 출력
  for (int i = 0; i < 5; i++) {
    cout << numbers[i] << " ";
  }
  cout << endl;

  // 특정 인덱스 접근
  cout << numbers[2] << endl;  // 30 출력

  // 배열 요소 변경
  numbers[3] = 100;

  // 변경된 배열 출력
  for (int i = 0; i < 5; i++) {
    cout << numbers[i] << " ";
  }
  cout << endl;

  return 0;
}

2. 벡터(vector)

  • 특징:
    • 동적 크기 조절 가능
    • 인덱스를 이용하여 빠른 랜덤 접근 가능 (O(1))
    • 메모리 사용 효율성이 높음
    • 벡터는 삽입, 삭제, 검색, 정렬 등 다양한 알고리즘을 효율적으로 지원
  • 장점:
    • 데이터 양이 미리 알려지지 않거나 변동 가능한 경우 유용
    • 인덱싱을 사용하여 빠른 접근 및 검색이 가능
    • 삽입, 삭제, 검색, 정렬 등 다양한 알고리즘을 효율적으로 지원
  • 단점:
    • 연속된 메모리 공간을 필요로 하기 때문에 메모리 할당 및 재할당 작업이 발생할 수 있음
    • 메모리 할당 및 재할당 작업으로 인해 캐시 미스가 발생할 가능성이 있음.
    • 삽입 및 삭제 연산이 특정 상황에서 비용이 많이 들 수 있음.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

#include <iostream>
#include <vector>

using namespace std;

int main() {
  // 학생 이름과 점수를 저장하는 벡터
  vector<pair<string, int>> students;

  // 학생 데이터 추가
  students.push_back({"Alice", 90});
  students.push_back({"Bob", 85});
  students.push_back({"Charlie", 70});

  // 학생 데이터 출력
  for (const auto& student : students) {
    cout << student.first << ": " << student.second << endl;
  }

  return 0;
}

3. 연결 리스트 (Linked List)

  • 특징:
    • 동적 메모리 할당
    • 순차적 접근 용이 (O(1))
    • 랜덤 접근 불편 (O(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
42
43
44

#include <iostream>
#include <list>

using namespace std;

int main() {
  // list 컨테이너 생성 및 요소 초기화
  list<int> numbers = {10, 20, 30, 40, 50};

  // 연결 리스트 출력 (front() ~ back() 사용)
  cout << "front: " << numbers.front() << endl;
  cout << "back: " << numbers.back() << endl;

  // 이터레이터를 이용한 순차적 접근 및 출력
  for (auto it = numbers.begin(); it != numbers.end(); ++it) {
    cout << *it << " ";
  }
  cout << endl;

  // 특정 위치에 요소 삽입
  it = numbers.begin();
  advance(it, 2); // 두 번째 위치로 이동
  it->insert(25); // 25를 삽입

  // 변경된 연결 리스트 출력
  for (auto it = numbers.begin(); it != numbers.end(); ++it) {
    cout << *it << " ";
  }
  cout << endl;

  // 특정 요소 삭제
  it = find(numbers.begin(), numbers.end(), 40);
  if (it != numbers.end()) {
    numbers.erase(it);
  }

  // 삭제된 연결 리스트 출력
  for (auto it = numbers.begin(); it != numbers.end(); ++it) {
    cout << *it << " ";
  }
  cout << endl;

  return 0;
}

4. 스택 (Stack)

  • 특징:
    • LIFO (Last In, First Out) 방식
    • Push, Pop 연산 지원
    • 선형 자료구조
  • 장점:
    • 간단한 구현
    • 재귀, 백트래킹 등에 유용
  • 단점:
    • 특정 요소 추출 어려움
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

#include <iostream>
#include <stack>

using namespace std;

int main() {
  // 스택 생성
  stack<int> s;

  // 스택에 데이터 삽입 (push)
  s.push(10);
  s.push(20);
  s.push(30);

  // 스택 데이터 출력 (top)
  cout << s.top() << endl; // 30 출력

  // 스택 데이터 꺼내기 (pop)
  s.pop();

  // 변경된 스택 데이터 출력
  cout << s.top() << endl; // 20 출력

  // 스택 비어있는지 확인 (empty)
  if (s.empty()) {
    cout << "스택이 비어 있습니다." << endl;
  } else {
    cout << "스택에 데이터가 있습니다." << endl;
  }

  return 0;

5. 큐 (Queue)

  • 특징:
    • FIFO (First In, First Out) 방식
    • Enqueue, Dequeue 연산 지원
    • 선형 자료구조
  • 장점:
    • 간단한 구현
    • 작업 처리 순서 유지 용이
  • 단점:
    • 특정 요소 추출 어려움
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

C++ 내장 라이브러리를 활용한 큐 구현 및 활용 예시
1. 큐 (Queue)

FIFO (First In, First Out) 방식으로 데이터를 저장하며, enqueue, dequeue 연산을 지원하는 큐는 다양한 상황에서 활용됩니다. 예를 들어, 프린터 대기열, 네트워크 패킷 전송 등에서 사용됩니다. C++ STL에는 queue 컨테이너가 제공되어 큐를 간편하게 구현하고 사용할 수 있습니다.

queue 컨테이너 특징:

FIFO 방식: 먼저 삽입된 데이터가 먼저 추출됩니다.
삽입/추출 효율성: enqueue, dequeue 연산은 O(1)의 평균 시간 복잡도를 가지고 매우 빠릅니다.
동적 메모리 관리: 필요한 만큼 메모리를 할당하고 해제하며, 메모리 낭비를 최소화합니다.
알고리즘 지원: STL에서 제공하는 다양한 알고리즘들을 queue 컨테이너에 적용하여 큐를 효율적으로 조작할 수 있습니다.
queue 컨테이너 사용 예시:

C++
#include <iostream>
#include <queue>

using namespace std;

int main() {
  // queue 컨테이너 생성
  queue<int> q;

  // 데이터 삽입 (enqueue)
  q.push(10);
  q.push(20);
  q.push(30);

  // 큐 첫 번째 데이터 출력 (front)
  cout << q.front() << endl; // 10 출력

  // 데이터 추출 (dequeue)
  q.pop();

  // 변경된 큐 첫 번째 데이터 출력
  cout << q.front() << endl; // 20 출력

  // 큐 비어있는지 확인 (empty)
  if (q.empty()) {
    cout << "큐가 비어 있습니다." << endl;
  } else {
    cout << "큐에 데이터가 있습니다." << endl;
  }

  // 모든 데이터 출력 (while문 사용)
  while (!q.empty()) {
    cout << q.front() << " ";
    q.pop();
  }
  cout << endl;

  return 0;
}

6. 해시 테이블 (Hash Table)

  • 특징:
    • 키 기반 빠른 검색 및 접근 (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 <unordered_map>

using namespace std;

int main() {
  // unordered_map 컨테이너 생성
  unordered_map<string, int> hashTable;

  // 키-값 쌍 삽입
  hashTable["apple"] = 100;
  hashTable["banana"] = 200;
  hashTable["orange"] = 300;

  // 키 기반 검색
  if (hashTable.find("banana") != hashTable.end()) {
    cout << "banana의 값은 " << hashTable["banana"] << "입니다." << endl;
  } else {
    cout << "banana 키가 존재하지 않습니다." << endl;
  }

  // 키-값 쌍 출력 (범위 기반 for문 사용)
  for (auto it = hashTable.begin(); it != hashTable.end(); ++it) {
    cout << it->first << ": " << it->second << endl;
  }

  // 특정 키 삭제
  hashTable.erase("orange");

  // 변경된 해시 테이블 출력
  for (auto it = hashTable.begin(); it != hashTable.end(); ++it) {
    cout << it->first << ": " << it->second << endl;
  }

  return 0;
}

7. 그래프 (Graph)

  • 특징:
    • 노드와 연결 관계 표현
    • 다양한 응용 분야 (네트워크, 알고리즘 등)
  • 장점:
    • 관계 표현에 유용
    • 다양한 알고리즘 설계 가능
  • 단점:
    • 복잡한 구현
    • 메모리 사용량 증가 가능성
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

#include <iostream>
#include <map>
#include <vector>

using namespace std;

struct Node {
  int data;
  vector<int> neighbors;
};

int main() {
  // 인접 리스트 표현 (map과 vector 사용)
  map<int, Node> graph;

  // 노드 추가 (data와 이웃 노드 정보 설정)
  Node node1{1, {2, 3}};
  Node node2{2, {1, 4}};
  Node node3{3, {1}};
  Node node4{4, {2}};

  graph[1] = node1;
  graph[2] = node2;
  graph[3] = node3;
  graph[4] = node4;

  // 그래프 탐색 (BFS)
  int startNode = 1;
  map<int, bool> visited;

  queue<int> q;
  q.push(startNode);

  while (!q.empty()) {
    int currentNode = q.front();
    q.pop();

    if (visited[currentNode]) continue;

    cout << currentNode << " ";
    visited[currentNode] = true;

    for (int nextNode : graph[currentNode].neighbors) {
      if (!visited[nextNode]) {
        q.push(nextNode);
      }
    }
  }
  cout << endl;

  return 0;
}

8. 트리 (Tree - 라이브러리 x)

  • 특징:
    • 계층적 구조
    • 탐색, 정렬 등에 활용
    • 다양한 종류 (이진 트리, 힙 트리 등)
  • 장점:
    • 효율적인 탐색 및 정렬 가능
    • 데이터 계층적 표현 용이
  • 단점:
    • 불균형 트리는 성능 저하
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

#include <iostream>
#include <vector>

using namespace std;

struct Node {
  int data;
  vector<Node*> children;
};

int main() {
  // 루트 노드 생성
  Node* root = new Node{10};

  // 자식 노드 생성 및 연결
  Node* child1 = new Node{20};
  Node* child2 = new Node{30};
  Node* child3 = new Node{40};

  root->children.push_back(child1);
  root->children.push_back(child2);
  root->children.push_back(child3);

  // 전위 순회 (재귀 함수 사용)
  void preorder(Node* node) {
    if (node == NULL) return;

    cout << node->data << " ";
    preorder(node->children[0]);
    preorder(node->children[1]);
    preorder(node->children[2]);
  }

  preorder(root);
  cout << endl;

  // 메모리 해제 (소멸자 사용)
  delete root;
  delete child1;
  delete child2;
  delete child3;

  return 0;
}

9. 맵 (Map)

  • 특징:
    • 키-값 쌍 저장
    • 빠른 키 기반 검색 및 접근 (O(1))
    • 다양한 프로그래밍 언어에서 제공
  • 장점:
    • 키 기반 데이터 관리 용이
    • 객체 속성 관리 등에 활용 가능
  • 단점:
    • 해시 테이블 기반 구현으로 충돌 해결 필요
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

#include <iostream>
#include <map>

using namespace std;

int main() {
  // 맵 컨테이너 선언
  map<string, int> myMap;

  // 키-값 쌍 삽입
  myMap["apple"] = 100;
  myMap["banana"] = 200;
  myMap["orange"] = 300;

  return 0;
}

10. 세트(set)

  • 특징:
    • 동일한 값이 두 번 이상 포함될 수 없다
    • 항상 오름차순 또는 내림차순으로 정렬된 상태를 유지 (하지만 값 순서는 보장x)
    • 특정 값이 존재하는지 빠르게 확인 가능 (평균 검색 복잡도는 O(1)
    • 값 삽입 및 삭제 연산이 빠름 (평균 삽입/삭제 복잡도는 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

#include <iostream>
#include <set>

int main() {
  // Set 생성
  std::set<int> numbers;

  // 값 삽입
  numbers.insert(10);
  numbers.insert(5);
  numbers.insert(15);
  numbers.insert(5); // 중복된 값은 무시됩니다.

  // Set 출력
  for (int number : numbers) {
    std::cout << number << " ";
  }
  std::cout << std::endl;

  // 특정 값 존재 여부 확인
  if (numbers.count(7) > 0) {
    std::cout << "7은 Set에 존재합니다." << std::endl;
  } else {
    std::cout << "7은 Set에 존재하지 않습니다." << std::endl;
  }

  return 0;
}

정리

아래는 각종 자주 쓰이는 자료구조의 특징을 간단히 정리한 표이다.

자료구조 특징 장점 단점 활용 사례
Array 연속적인 메모리 공간, 빠른 접근 인덱스를 통한 빠른 접근, 메모리 효율적 크기 변경 어려움, 중복 허용 데이터 배열, 고정 길이 데이터 저장
Vector 순서 유지, 빠른 삽입/삭제 값 순서 직접 제어 가능, 키-값 쌍 저장 가능 중복 허용, 검색 비교적 느림 순서 중요한 데이터 저장, 동적 배열 구현
List 순서 유지, 삽입/삭제 용이 삽입/삭제 연산이 빠름 검색 비교적 느림, 메모리 비효율적일 수 있음 순서 중요한 데이터 처리, 연결 리스트 구현
Stack 선입후출 (LIFO) 선입후출 방식 데이터 처리에 적합 삽입/삭제 제한적 스택 기반 알고리즘 구현, 함수 호출 관리
Queue 선입선출 (FIFO) 선입선출 방식 데이터 처리에 적합 순서 제어 어려움 큐잉 시스템, 작업 처리
unordered_map 키-값 쌍 저장, 빠른 검색/삽입/삭제 키-값 쌍 저장에 적합, 중복 허용 순서 유지 안 됨 데이터베이스 인덱싱, 캐싱, 컨피그 파일 관리
Graph 노드와 간선으로 구성된 네트워크 관계 표현 및 분석에 적합 구현 및 알고리즘 복잡 네트워킹, 경로탐색, 소셜 네트워크 분석
Tree 계층적 구조, 효율적인 검색 순서 유지, 범위 검색 가능 삽입/삭제 비교적 느림 파일 시스템 구조, 데이터베이스 인덱싱
Map 키-값 쌍 저장, 빠른 검색 키-값 쌍 저장에 적합 순서 유지 안 됨, 중복 허용 개체 속성 관리, 데이터베이스 인덱싱
Set 중복 불허용, 정렬 유지, 빠른 검색/삽입/삭제 중복 제거, 고유 값 관리, 집합 연산 값 순서 직접 제어 불가, 키-값 쌍 저장 불가 고유한 값 목록 관리, 데이터 중복 제거, 집합 연산 수행

undefined

정리

아래는 각종 자주 쓰이는 자료구조의 특징을 간단히 정리한 표이다.

자료구조 특징 장점 단점 활용 사례
Array 연속적인 메모리 공간, 빠른 접근 인덱스를 통한 빠른 접근, 메모리 효율적 크기 변경 어려움, 중복 허용 데이터 배열, 고정 길이 데이터 저장
Vector 순서 유지, 빠른 삽입/삭제 값 순서 직접 제어 가능, 키-값 쌍 저장 가능 중복 허용, 검색 비교적 느림 순서 중요한 데이터 저장, 동적 배열 구현
List 순서 유지, 삽입/삭제 용이 삽입/삭제 연산이 빠름 검색 비교적 느림, 메모리 비효율적일 수 있음 순서 중요한 데이터 처리, 연결 리스트 구현
Stack 선입후출 (LIFO) 선입후출 방식 데이터 처리에 적합 삽입/삭제 제한적 스택 기반 알고리즘 구현, 함수 호출 관리
Queue 선입선출 (FIFO) 선입선출 방식 데이터 처리에 적합 순서 제어 어려움 큐잉 시스템, 작업 처리
unordered_map 키-값 쌍 저장, 빠른 검색/삽입/삭제 키-값 쌍 저장에 적합, 중복 허용 순서 유지 안 됨 데이터베이스 인덱싱, 캐싱, 컨피그 파일 관리
Graph 노드와 간선으로 구성된 네트워크 관계 표현 및 분석에 적합 구현 및 알고리즘 복잡 네트워킹, 경로탐색, 소셜 네트워크 분석
Tree 계층적 구조, 효율적인 검색 순서 유지, 범위 검색 가능 삽입/삭제 비교적 느림 파일 시스템 구조, 데이터베이스 인덱싱
Map 키-값 쌍 저장, 빠른 검색 키-값 쌍 저장에 적합 순서 유지 안 됨, 중복 허용 개체 속성 관리, 데이터베이스 인덱싱
Set 중복 불허용, 정렬 유지, 빠른 검색/삽입/삭제 중복 제거, 고유 값 관리, 집합 연산 값 순서 직접 제어 불가, 키-값 쌍 저장 불가 고유한 값 목록 관리, 데이터 중복 제거, 집합 연산 수행

undefined 자료구조 선택 시 성능, 메모리 사용량, 구현 복잡도 등을 고려해야 좀 더 효율적인 알고리즘을 작성 할 수 있다.

CATALOG
    FEATURED TAGS
    CS Algorithm-DFS/BFS Algorithm-구현 Samsung-Coding Algorithm-브루트 포스 Algorithm-DP C++ Algorithm-그리디 알고리즘 Algorithm-백트래킹 C Information Algorithm-이분탐색 BOJ Algorithm-정렬 Python web AI Git IT-Tech-자동차 Notion PJT TroubleShoot etc
    FRIENDS