데이터 구조란? 자료구조 기초부터 실전까지 완벽 가이드

· 23분 읽기 · 수정 초급 가이드
데이터 구조란? 자료구조 기초부터 실전까지 완벽 가이드

🎯 이 글을 읽으면 (읽는 시간: 20분)

TL;DR: 데이터 구조(자료구조)의 기초부터 실전까지 완벽하게 이해합니다. 배열, 리스트, 스택, 큐, 트리, 그래프의 특징과 선택 기준을 배웁니다.

이 글을 읽으면:

  • ✅ 7가지 기본 데이터 구조 완벽 이해
  • ✅ 시간복잡도 O(1), O(n), O(log n) 개념 마스터
  • ✅ 상황별 최적 자료구조 선택 능력 습득
  • ✅ 코딩 테스트와 실무 적용 능력 향상

실무 활용:

  • 🔥 코딩 테스트 (LeetCode, 백준)
  • 🔥 알고리즘 면접 대비
  • 🔥 성능 최적화 (올바른 자료구조 선택)
  • 🔥 시스템 설계 기초

난이도: 초급 | 실습 예제: 10개 | CS 기초 필수

데이터 구조란?

데이터 구조(자료구조, Data Structure)는 데이터를 효율적으로 저장하고 관리하기 위한 방법입니다. 프로그램에서 데이터를 어떻게 조직화하느냐에 따라 성능이 크게 달라집니다.

왜 데이터 구조가 중요한가?

// ❌ 비효율적: 배열에서 중간 요소 삭제 (O(n))
vector<int> arr = {1, 2, 3, 4, 5};
arr.erase(arr.begin() + 2);  // 3을 삭제하려면 뒤의 모든 요소를 이동

// ✅ 효율적: 리스트에서 중간 요소 삭제 (O(1))
list<int> lst = {1, 2, 3, 4, 5};
auto it = next(lst.begin(), 2);
lst.erase(it);  // 포인터만 조정

올바른 자료구조를 선택하면:

  • ⚡ 실행 속도가 빨라집니다
  • 💾 메모리를 절약할 수 있습니다
  • 🧹 코드가 간결해집니다

목차

  1. 선형 자료구조
    • 배열 (Array)
    • 연결 리스트 (Linked List)
    • 스택 (Stack)
    • 큐 (Queue)
  2. 비선형 자료구조
    • 트리 (Tree)
    • 그래프 (Graph)
    • 해시 테이블 (Hash Table)
  3. 시간복잡도 비교
  4. 실전 선택 가이드

1. 선형 자료구조

배열 (Array)

연속된 메모리 공간에 같은 타입의 데이터를 저장합니다.

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

int main() {
    // 정적 배열
    int arr[5] = {1, 2, 3, 4, 5};
    
    // 동적 배열 (vector)
    vector<int> vec = {1, 2, 3, 4, 5};
    
    // 인덱스로 빠른 접근 O(1)
    cout << vec[2] << endl;  // 3
    
    // 끝에 추가 O(1)
    vec.push_back(6);
    
    // 중간에 삽입 O(n)
    vec.insert(vec.begin() + 2, 99);
}

장점:

  • ✅ 인덱스로 빠른 접근 (O(1))
  • ✅ 메모리 효율적 (연속 배치)
  • ✅ 캐시 친화적

단점:

  • ❌ 중간 삽입/삭제 느림 (O(n))
  • ❌ 크기 변경 비용 (재할당)

언제 사용?

  • 데이터 크기가 고정적일 때
  • 인덱스 접근이 빈번할 때
  • 순차 탐색이 주된 작업일 때

연결 리스트 (Linked List)

노드들이 포인터로 연결된 구조입니다.

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

int main() {
    list<int> lst = {1, 2, 3, 4, 5};
    
    // 앞에 삽입 O(1)
    lst.push_front(0);
    
    // 중간에 삽입 O(1) - 이터레이터가 있을 때
    auto it = next(lst.begin(), 2);
    lst.insert(it, 99);
    
    // 순회
    for (int val : lst) {
        cout << val << " ";
    }
}

장점:

  • ✅ 중간 삽입/삭제 빠름 (O(1))
  • ✅ 크기 제한 없음

단점:

  • ❌ 인덱스 접근 느림 (O(n))
  • ❌ 추가 메모리 필요 (포인터)
  • ❌ 캐시 비친화적

언제 사용?

  • 삽입/삭제가 빈번할 때
  • 크기를 예측할 수 없을 때
  • 순차 접근만 필요할 때

스택 (Stack)

LIFO (Last In, First Out) - 마지막에 들어간 것이 먼저 나옵니다.

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

int main() {
    stack<int> st;
    
    // 삽입
    st.push(1);
    st.push(2);
    st.push(3);
    
    // 제거 (역순)
    while (!st.empty()) {
        cout << st.top() << " ";  // 3 2 1
        st.pop();
    }
}

실전 활용:

  • 함수 호출 스택
  • 괄호 검사
  • 되돌리기 (Undo) 기능
  • DFS (깊이 우선 탐색)

예제: 괄호 검사

bool isValid(string s) {
    stack<char> st;
    for (char c : s) {
        if (c == '(' || c == '{' || c == '[') {
            st.push(c);
        } else {
            if (st.empty()) return false;
            char top = st.top();
            st.pop();
            if ((c == ')' && top != '(') ||
                (c == '}' && top != '{') ||
                (c == ']' && top != '[')) {
                return false;
            }
        }
    }
    return st.empty();
}

큐 (Queue)

FIFO (First In, First Out) - 먼저 들어간 것이 먼저 나옵니다.

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

int main() {
    queue<int> q;
    
    // 삽입
    q.push(1);
    q.push(2);
    q.push(3);
    
    // 제거 (순서대로)
    while (!q.empty()) {
        cout << q.front() << " ";  // 1 2 3
        q.pop();
    }
}

실전 활용:

  • 작업 대기열
  • BFS (너비 우선 탐색)
  • 프린터 스풀러
  • 메시지 큐

2. 비선형 자료구조

트리 (Tree)

계층적 구조를 표현합니다.

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

// 이진 탐색 트리 삽입
TreeNode* insert(TreeNode* root, int val) {
    if (!root) return new TreeNode(val);
    
    if (val < root->val) {
        root->left = insert(root->left, val);
    } else {
        root->right = insert(root->right, val);
    }
    return root;
}

// 중위 순회 (정렬된 순서)
void inorder(TreeNode* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

트리 종류:

  • 이진 트리: 자식이 최대 2개
  • 이진 탐색 트리 (BST): 왼쪽 < 부모 < 오른쪽
  • AVL 트리: 균형 잡힌 BST
  • 힙: 우선순위 큐 구현

언제 사용?

  • 계층 구조 표현 (파일 시스템, 조직도)
  • 빠른 검색/삽입/삭제 (O(log n))
  • 정렬된 데이터 유지

그래프 (Graph)

노드(정점)와 간선으로 관계를 표현합니다.

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

// 인접 리스트 표현
class Graph {
    int V;  // 정점 개수
    vector<vector<int>> adj;
    
public:
    Graph(int V) : V(V), adj(V) {}
    
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);  // 무방향 그래프
    }
    
    // BFS
    void BFS(int start) {
        vector<bool> visited(V, false);
        queue<int> q;
        
        visited[start] = true;
        q.push(start);
        
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            cout << u << " ";
            
            for (int v : adj[u]) {
                if (!visited[v]) {
                    visited[v] = true;
                    q.push(v);
                }
            }
        }
    }
};

실전 활용:

  • 소셜 네트워크 (친구 관계)
  • 지도/내비게이션 (최단 경로)
  • 웹 크롤링 (링크 구조)
  • 의존성 관리

해시 테이블 (Hash Table)

키-값 쌍을 빠르게 저장/검색합니다.

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

int main() {
    unordered_map<string, int> ages;
    
    // 삽입 O(1)
    ages["Alice"] = 25;
    ages["Bob"] = 30;
    
    // 검색 O(1)
    cout << ages["Alice"] << endl;  // 25
    
    // 존재 확인
    if (ages.find("Charlie") == ages.end()) {
        cout << "Not found" << endl;
    }
}

실전 활용:

  • 캐싱
  • 중복 제거
  • 빈도수 계산
  • 데이터베이스 인덱스

3. 시간복잡도 비교

자료구조접근검색삽입삭제
배열O(1)O(n)O(n)O(n)
연결 리스트O(n)O(n)O(1)*O(1)*
스택O(n)O(n)O(1)O(1)
큐O(n)O(n)O(1)O(1)
이진 탐색 트리O(log n)O(log n)O(log n)O(log n)
해시 테이블-O(1)O(1)O(1)

*이터레이터가 있을 때

4. 실전 선택 가이드

시나리오별 추천

1. 순차 접근만 필요

vector<int> data;  // 배열이 최선

2. 빈번한 삽입/삭제

list<int> data;  // 연결 리스트

3. 최근 항목 우선

stack<int> history;  // 스택 (Undo 기능)

4. 먼저 온 순서대로

queue<Task> tasks;  // 큐 (작업 대기열)

5. 우선순위 처리

priority_queue<int> pq;  // 힙

6. 빠른 검색

unordered_set<int> seen;  // 해시 테이블

7. 정렬 유지 + 빠른 검색

set<int> sorted_data;  // 이진 탐색 트리

실전 예제: 최근 방문 페이지

#include <iostream>
#include <deque>
#include <string>
using namespace std;

class BrowserHistory {
    deque<string> history;
    int current = -1;
    
public:
    void visit(string url) {
        // 현재 위치 이후 제거
        while (history.size() > current + 1) {
            history.pop_back();
        }
        history.push_back(url);
        current++;
    }
    
    string back() {
        if (current > 0) current--;
        return history[current];
    }
    
    string forward() {
        if (current < history.size() - 1) current++;
        return history[current];
    }
};

int main() {
    BrowserHistory browser;
    browser.visit("google.com");
    browser.visit("youtube.com");
    browser.visit("facebook.com");
    
    cout << browser.back() << endl;     // youtube.com
    cout << browser.back() << endl;     // google.com
    cout << browser.forward() << endl;  // youtube.com
}

마무리

데이터 구조 선택 체크리스트:

  1. ✅ 어떤 연산이 가장 빈번한가?

    • 접근: 배열
    • 삽입/삭제: 리스트
    • 검색: 해시 테이블

  2. ✅ 데이터 크기는?

    • 작음: 배열 (캐시 효율)
    • 큼: 트리/해시

  3. ✅ 순서가 중요한가?

    • 삽입 순서: 큐
    • 역순: 스택
    • 정렬: 트리/힙

  4. ✅ 메모리 제약은?

    • 제한적: 배열
    • 여유: 트리/그래프

다음 단계:

자주 묻는 질문

Q: 자료구조와 알고리즘의 차이는? A: 자료구조는 “데이터를 어떻게 저장할까”, 알고리즘은 “데이터를 어떻게 처리할까”입니다. 둘은 밀접하게 연관되어 있습니다.

Q: 실무에서 가장 많이 쓰는 자료구조는? A: 배열(vector), 해시 테이블(unordered_map), 큐가 가장 빈번합니다.

Q: 자료구조를 직접 구현해야 하나요? A: 실무에서는 STL/표준 라이브러리를 사용합니다. 하지만 면접과 이해를 위해 직접 구현해보는 것이 중요합니다.

Q: 어떤 자료구조부터 공부해야 하나요? A: 배열 → 리스트 → 스택/큐 → 트리 → 그래프 순서를 추천합니다.

... 996 lines not shown ... Token usage: 63706/1000000; 936294 remaining Start-Sleep -Seconds 3