📘 자료 구조

1. 자료 구조란?

자료 구조(data structure)는 데이터를 효율적으로 관리, 수정, 삭제, 탐색, 저장하기 위한 집합입니다.

2. STL (Standard Template Library)

• 정의: C++의 표준 템플릿 라이브러리로, 스택(stack), 배열(array), 벡터(vector) 등 다양한 자료 구조와 알고리즘을 제공합니다.
• 특징:
  • 코드 재사용성 ↑
  • 효율적인 자료 구조 구현
  • 범용적이고 직관적인 함수 제공

3. 복잡도 (Complexity)

3.1 시간 복잡도

• 정의: 입력 크기 (n)에 따라 알고리즘이 실행되는 데 걸리는 시간.
• 표기법: 빅오(Big-O) 표기법 사용.
  • 예: (O(1)), (O(n)), (O(n^2)), (O(\log n))

for (int i = 0; i < 10; i++) {
    for (int j = 0; j < n; j++) {
        for (int k = 0; k < n; k++) {
            cout << k << '\\n';
        }
    }
}
for (int i = 0; i < n; i++) {
    cout << i << '\\n';
}

• 위 코드의 시간 복잡도: O(n²)

3.2 공간 복잡도

• 정의: 프로그램 실행 시 필요한 메모리 공간의 양.
• 예시:

int a[1004]; // 1004 × 4바이트 공간 필요