자료구조 (Data Structures)

정의

자료구조 (Data Structure) 는 데이터를 효율적으로 저장하고 접근하기 위한 조직화 방법. 문제 풀이에서는 시간 복잡도와 공간 복잡도의 trade-off 를 정확히 파악해 적절한 자료구조를 선택하는 것이 핵심.

흔히 배열, 연결 리스트, 스택, 큐, 트리, 해시 테이블, 힙, 세그먼트 트리, 펜윅 트리 등을 포괄.

문제 상황과 동기

동일한 연산 (삽입, 삭제, 검색, 갱신) 도 자료구조에 따라 복잡도가 천차만별:

• 배열: 인덱스 접근 O(1), 검색 O(N), 삽입/삭제 O(N).
• 연결 리스트: 삽입/삭제 O(1) (노드 포인터를 이미 안다면), 검색 O(N).
• 해시 테이블: 평균 O(1) 삽입/검색, 최악 O(N), 순서 없음.
• 이진 탐색 트리 (BST): 평균 O(log N), 최악 O(N), 균형 트리 (AVL, Red-Black) 는 최악 O(log N).
• 세그먼트 트리: 구간 쿼리 + 점 갱신 O(log N), 메모리 O(N).
• 펜윅 트리 (BIT): 구간 쿼리 + 점 갱신 O(log N), 메모리 O(N), 구현 간단, 역원 필요.

핵심 통찰: 연산 빈도와 범위 에 따라 최적 자료구조가 결정된다. 예: 단순 스택은 LIFO, 큐는 FIFO, 우선순위 큐는 힙으로.

시각화

기본 자료구조 비교

핵심 아이디어

1. 배열 vs 연결 리스트

• 배열: 메모리 연속 배치, 캐시 히트율 높음, 인덱스 접근 O(1), 중간 삽입/삭제 O(N).
• 연결 리스트: 노드 포인터로 연결, 삽입/삭제 O(1) (포인터를 알면), 랜덤 접근 O(N).

PS 에서는 배열이 압도적으로 유리 (캐시 + 인덱스 접근). 연결 리스트는 LRU 캐시, 큰 원소 중간 삽입 등 특수 상황만.

2. 해시 vs 균형 트리

• 해시 (unordered_map, dict, HashMap): 평균 O(1), 순서 없음, 최악 O(N) (해시 충돌).
• 균형 트리 (map, TreeMap, set): 최악 O(log N), 순서 보장, 범위 쿼리 가능.

문제 조건:

• “존재 여부만” → 해시.
• “k번째 작은 값”, “l 이상 r 이하 개수” → 균형 트리 or 세그먼트 트리.

3. 세그먼트 트리 vs 펜윅 트리

둘 다 구간 쿼리 + 점 갱신 O(log N), 메모리 O(N).

PS 에서는 합 쿼리는 펜윅, min/max/gcd 는 세그먼트 트리.

4. 균형 트리 종류

PS 에서는 C++ std::set, std::map (Red-Black) 이 대부분. 직접 구현은 거의 안 함.

알고리즘

자료구조는 알고리즘이 아니므로 pseudocode 대신 연산별 복잡도와 선택 기준 을 정리.

선택 기준:
1. 연산 종류: 삽입/삭제 빈도, 검색 빈도, 구간 쿼리 필요?
2. 순서: 정렬 상태 유지 필요?
3. 메모리: N 크기, 메모리 제약?
4. 구현: 시간 제약, 라이브러리 사용 가능?

예시:
- "Q개 (key, value) 삽입 후 key로 value 검색" → 해시 테이블 O(N+Q).
- "Q개 삽입 + k번째 작은 값" → 균형 트리 O(Q log Q) or 세그트리.
- "배열, 구간 합 Q번" → [[Prefix Sum|누적 합]] O(N+Q) or 펜윅.
- "배열, 구간 합 + 점 갱신" → 펜윅 or 세그트리 O((N+Q) log N).
- "배열, 구간 min/max" → 세그트리 or [[Sparse Table|희소 배열]].

구현

자료구조 선택 예시: 배열 vs 해시 vs 균형 트리.

// 배열 vs 해시 vs 균형 트리
#include <bits/stdc++.h>
using namespace std;
int main() {
  int n; cin >> n;
  // 1. 배열: 인덱스 접근 O(1), 검색 O(N)
  vector<int> arr(n);
  for (auto& v : arr) cin >> v;
  cout << "arr[0] = " << arr[0] << "\n";
​
  // 2. 해시: 삽입/검색 평균 O(1)
  unordered_set<int> hs(arr.begin(), arr.end());
  cout << "hs.count(arr[0]) = " << hs.count(arr[0]) << "\n";
​
  // 3. 균형 트리: 삽입/검색 O(log N), 순서 보장
  set<int> st(arr.begin(), arr.end());
  cout << "st.size() = " << st.size() << "\n";
  cout << "*st.begin() = " << *st.begin() << "\n";
}

# 배열 vs 집합 vs 딕셔너리
import sys
input = sys.stdin.readline
​
n = int(input())
arr = list(map(int, input().split()))
​
# 1. 배열: 인덱스 O(1), 검색 O(N)
print(f"arr[0] = {arr[0]}")
​
# 2. 집합: 삽입/검색 평균 O(1)
hs = set(arr)
print(f"arr[0] in hs = {arr[0] in hs}")
​
# 3. 정렬된 집합 (bisect 활용)
import bisect
sorted_arr = sorted(set(arr))
print(f"len(sorted_arr) = {len(sorted_arr)}")
print(f"sorted_arr[0] = {sorted_arr[0]}")

// ArrayList vs HashSet vs TreeSet
import java.util.*;
import java.io.*;
public class Main {
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      int n = Integer.parseInt(br.readLine());
      StringTokenizer st = new StringTokenizer(br.readLine());
      
      // 1. ArrayList: 인덱스 O(1), 검색 O(N)
      ArrayList<Integer> arr = new ArrayList<>();
      for (int i = 0; i < n; i++) arr.add(Integer.parseInt(st.nextToken()));
      System.out.println("arr.get(0) = " + arr.get(0));
      
      // 2. HashSet: 삽입/검색 평균 O(1)
      HashSet<Integer> hs = new HashSet<>(arr);
      System.out.println("hs.contains(arr.get(0)) = " + hs.contains(arr.get(0)));
      
      // 3. TreeSet: 삽입/검색 O(log N), 순서 보장
      TreeSet<Integer> ts = new TreeSet<>(arr);
      System.out.println("ts.size() = " + ts.size());
      System.out.println("ts.first() = " + ts.first());
  }
}

5
3 1 4 1 5

arr[0] = 3
hs.count(arr[0]) = 1
st.size() = 4
*st.begin() = 1

복잡도

자료구조별 복잡도는 위 비교 표 참고. 일반적으로:

변형

1. 특수 자료구조

• Disjoint Set (Union-Find): 집합 합치기 + 같은 집합 판정, amortized O(α(N)) ≈ O(1).
• Trie: 문자열 집합, 검색 O(L) (L = 문자열 길이).
• Segment Tree with Lazy Propagation: 구간 갱신 O(log N).
• Persistent Segment Tree: 버전별 쿼리, PST 참고.
• Fenwick Tree 2D: 2차원 구간 합, 메모리 O(NM).
• Sparse Table: 불변 배열, 구간 min/max O(1) 쿼리, 희소 배열.

2. 고급 활용

• 좌표 압축 + 세그트리: 값 범위 10^9, 개수 N=10^5 → 좌표 압축 후 세그트리.
• 오프라인 쿼리 + 정렬: 쿼리 순서 바꿔 효율 증대.
• SQRT Decomposition: 세그트리 대신 블록 √N 개로 나눔, 구현 간단.

함정

1. 해시 테이블 최악 케이스

unordered_map 은 특정 입력 (해킹 테스트 케이스) 에서 O(N) 로 퇴화. Codeforces 등에서 TLE 발생 가능. 대책:

• reserve() + custom hash.
• map (Red-Black) 으로 fallback.

2. 세그트리 메모리 오버

배열 크기 N 에 대해 세그트리는 4N 메모리 필요. N=10^6 면 int 기준 16MB. vector<int>(4*N) 선언 필수.

3. 펜윅 트리 역원

펜윅은 역원이 필요한 연산 (덧셈, XOR) 만 가능. min/max 는 불가능 → 세그트리.

4. 균형 트리 중복

std::set 은 중복 불허, std::multiset 은 중복 허용. 문제 조건 확인 필수.

5. 배열 vs 동적 배열

C++ int arr[N] 은 컴파일 타임 상수 N 필요. 런타임 N 은 vector<int>(N) 또는 동적 할당.

BOJ 연습 문제

자료구조는 범위가 넓어 대표 문제만 나열. 각 자료구조별 문제는 해당 wiki 참고.

참고

• 세그먼트 트리
• 펜윅 트리
• 희소 배열
• 분리 집합
• 트라이
• 누적 합