programming language/자료구조

C++ 자료구조 개요

metamong-data 2025. 1. 23. 16:48
728x90
반응형

자료구조(Data Structure)는 데이터를 효율적으로 저장하고 관리하는 구조입니다. C++에서 자료구조는 다양한 데이터 유형과 알고리즘의 기반을 형성하며, 적절한 자료구조를 선택하는 것은 프로그램의 성능과 효율성을 결정하는 중요한 요소입니다.

1. 자료구조의 필요성

  1. 효율적인 데이터 관리:

    • 데이터의 수가 많아질수록 효율적인 관리가 필요합니다.

    • 예: 1,000,000명의 학생 정보를 관리하는 프로그램.

  2. 성능 최적화:

    • 자료구조와 알고리즘의 성능을 고려해야 합니다.

    • 성능 비교의 주요 지표:

      • 시간 복잡도 (Time Complexity): 연산의 수행 횟수.

      • 공간 복잡도 (Space Complexity): 메모리 사용량.

  3. 적합한 자료구조 선택:

    • 문제에 따라 적합한 자료구조를 선택하여 효율성을 극대화합니다.

    • 예: 검색이 빠른 트리(Tree) 구조.

2. 자료구조의 분류

자료구조는 크게 선형 자료구조와 비선형 자료구조로 나눌 수 있습니다.

2.1 선형 자료구조 (Linear Data Structure)

  1. 특징:

    • 데이터가 순차적으로 연결되어 있습니다.

    • 데이터가 하나의 직선상에 배치됩니다.

  2. 예시:

    • 배열 (Array)

    • 연결 리스트 (Linked List)

    • 스택 (Stack)

    • 큐 (Queue)

    • 덱 (Deque)

  3. 사용 사례:

    • 순차적으로 데이터 접근 및 관리가 필요한 경우.

예시: 배열

#include <iostream>
using namespace std;

int main() {
    int arr[5] = {1, 2, 3, 4, 5};
    for (int i = 0; i < 5; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

출력

1 2 3 4 5

2.2 비선형 자료구조 (Non-linear Data Structure)

  1. 특징:

    • 데이터가 계층적이거나 비선형적으로 연결됩니다.

    • 데이터 간의 관계가 복잡한 구조를 가집니다.

  2. 예시:

    • 트리 (Tree)

    • 그래프 (Graph)

  3. 사용 사례:

    • 계층적 데이터 표현(예: 디렉토리 구조).

    • 복잡한 관계를 모델링(예: 소셜 네트워크).

예시: 트리

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

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

Node* createNode(int data) {
    Node* newNode = new Node;
    newNode->data = data;
    return newNode;
}

int main() {
    Node* root = createNode(1);
    root->children.push_back(createNode(2));
    root->children.push_back(createNode(3));
    root->children[0]->children.push_back(createNode(4));

    cout << "Root: " << root->data << endl;
    cout << "Child 1: " << root->children[0]->data << endl;
    cout << "Child 2: " << root->children[1]->data << endl;
    cout << "Grandchild: " << root->children[0]->children[0]->data << endl;
    return 0;
}

출력

Root: 1
Child 1: 2
Child 2: 3
Grandchild: 4

3. 자료구조와 알고리즘의 관계

  1. 시간 복잡도 (Big-O 표기법):

    • 알고리즘의 성능을 수치적으로 표현.

    • 예: O(1), O(n), O(n²).

  2. 공간 복잡도:

    • 알고리즘이 사용하는 메모리 양.

    • 예: 4MB 배열은 int a[1000000];과 같이 선언.

  3. 알고리즘 성능 비교:

    • 연산 횟수가 많을수록 성능 저하.

    • O(n)과 O(n²)의 차이는 데이터가 많아질수록 커짐.

4. 결론

C++의 자료구조는 데이터를 효율적으로 저장하고 처리하는 데 중요한 역할을 합니다. 적절한 자료구조 선택은 성능 최적화의 핵심입니다. 다양한 자료구조의 특성을 이해하고 문제에 적합한 자료구조를 사용함으로써 효율적인 코드를 작성할 수 있습니다.

728x90