SECTION 5.1 복잡도

자료 구조(Data Structure) 기초 — 복잡도 완벽 정리

자료 구조(data structure)란 효율적으로 데이터를 관리하고 수정, 삭제, 탐색, 저장할 수 있는 데이터 집합을 말합니다.

---

📌 사전 지식 — STL이란?

STL(Standard Template Library) 은 C++의 표준 템플릿 라이브러리로, 스택·배열 등 다양한 자료 구조와 알고리즘 함수를 제공하는 라이브러리 묶음입니다.

💡 C++는 어려운 언어처럼 느껴지지만, 자료 구조를 공부하는 수준에서는 매우 쉬운 난이도만 알아도 충분합니다.
별도 설치 없이 아래 링크에서 바로 실행해볼 수 있어요.
🔗 C++ 온라인 컴파일러

---

5.1 복잡도

복잡도는 크게 두 가지로 나뉩니다.

• 시간 복잡도 — 알고리즘 실행에 걸리는 시간
• 공간 복잡도 — 알고리즘 실행에 필요한 메모리 공간

---

5.1.1 시간 복잡도

C++ 기본 문법 훑기

시간 복잡도에 앞서, C++의 기본 구조를 간단히 살펴보겠습니다.
아래는 입력받은 문자열을 출력하는 가장 간단한 예제입니다.

#include <bits/stdc++.h>  // (1) STL 전체 포함 헤더
using namespace std;      // (2) std 네임스페이스 기본 설정
string a;                 // (3) 문자열 변수 선언

int main()
{
    cin >> a;             // (4) 입력
    cout << a << "\n";    // (5) 출력
    return 0;             // (6) 프로세스 정상 종료
}

번호	설명
(1)	bits/stdc++.h — 모든 표준 라이브러리가 포함된 헤더
(2)	std::cin → cin 처럼 네임스페이스 없이 사용 가능하게 설정
(3)	<타입> <변수명> 형태로 선언. a는 lvalue, "큰돌"은 rvalue
(4)	입력: cin, scanf 등
(5)	출력: cout, printf 등
(6)	return 0 — 정상 종료 신호

---

빅오(Big-O) 표기법

시간 복잡도 = 입력 크기 n에 대해 알고리즘이 실행되는 데 걸리는 시간

주요 로직의 반복 횟수를 기준으로 측정하며, 빅오 표기법으로 나타냅니다.

예를 들어 아래 코드의 시간 복잡도를 계산해봅시다.

for (int i = 0; i < 10; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            if (true) cout << k << '\n';  // 10 * n * n 번 실행
        }
    }
}
for (int i = 0; i < n; i++) {
    if (true) cout << i << '\n';          // n번 실행
}

총 연산량 = 10n² + n
→ 빅오 표기법으로는 O(n²)

핵심 원칙: 가장 영향이 큰 항만 남기고, 상수 계수와 하위 항은 제거합니다.
n이 커질수록 n²이 압도적으로 커지기 때문에 나머지는 무시해도 됩니다.

---

시간 복잡도가 왜 필요한가?

효율적인 코드로 개선하는 척도가 되기 때문입니다.

예를 들어 어떤 버튼을 누를 때 O(n²) 알고리즘으로 9초가 걸린다면,
이를 O(n) 알고리즘으로 개선하면 3초로 줄일 수 있습니다.

속도 비교

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ)

O(n²) 보다는 O(n), O(n) 보다는 O(1) 을 항상 지향하세요.

---

5.1.2 공간 복잡도

공간 복잡도 = 프로그램 실행 시 필요한 자원(메모리) 공간의 양

정적 변수뿐만 아니라, 재귀 함수로 인해 동적으로 쌓이는 공간도 포함합니다.

int a[1004];  // 1004 × 4바이트 = 약 4KB 사용

---

5.1.3 자료 구조별 시간 복잡도

자료 구조를 선택할 때는 평균과 최악의 시간 복잡도를 함께 고려해야 합니다.

평균 시간 복잡도

자료 구조	접근	탐색	삽입	삭제
배열(Array)	O(1)	O(n)	O(n)	O(n)
스택(Stack)	O(n)	O(n)	O(1)	O(1)
큐(Queue)	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트	O(n)	O(n)	O(1)	O(1)
해시 테이블	O(1)	O(1)	O(1)	O(1)
이진 탐색 트리(BST)	O(log n)	O(log n)	O(log n)	O(log n)
AVL 트리	O(log n)	O(log n)	O(log n)	O(log n)
레드 블랙 트리	O(log n)	O(log n)	O(log n)	O(log n)

최악 시간 복잡도

자료 구조	접근	탐색	삽입	삭제
배열(Array)	O(1)	O(n)	O(n)	O(n)
스택(Stack)	O(n)	O(n)	O(1)	O(1)
큐(Queue)	O(n)	O(n)	O(1)	O(1)
이중 연결 리스트	O(n)	O(n)	O(1)	O(1)
해시 테이블	O(n)	O(n)	O(n)	O(n)
이진 탐색 트리(BST)	O(n)	O(n)	O(n)	O(n)
AVL 트리	O(log n)	O(log n)	O(log n)	O(log n)
레드 블랙 트리	O(log n)	O(log n)	O(log n)	O(log n)

⚠️ BST vs AVL/레드 블랙 트리
BST는 편향 트리가 되면 최악 O(n)까지 떨어질 수 있지만,
AVL이나 레드 블랙 트리는 자동으로 균형을 맞춰 항상 O(log n)을 보장합니다.