자료구조¶

1. 배열 (Array)¶

같은 타입의 원소를 연속된 메모리에 저장합니다.

연산	시간복잡도
인덱스 접근	O(1)
탐색	O(n)
삽입/삭제	O(n)

크기가 고정됨
중간 삽입/삭제 시 원소 이동 필요

2. 연결 리스트 (Linked List)¶

노드(데이터 + 포인터)를 연결한 구조입니다. 메모리가 분산되어 있습니다.

연산	시간복잡도
접근	O(n)
삽입/삭제 (앞/뒤)	O(1)
탐색	O(n)

종류¶

단일 연결 리스트: [Data|Next] → [Data|Next] → [Data|NULL]

이중 연결 리스트: [Prev|Data|Next] ↔ [Prev|Data|Next] - 양방향 탐색 가능

원형 연결 리스트: 마지막 노드의 Next가 첫 노드를 가리킴

배열 vs 연결 리스트¶

구분	배열	연결 리스트
접근	O(1)	O(n)
삽입/삭제	O(n)	O(1)
메모리	연속	분산
크기	고정	가변

3. 스택 (Stack)¶

LIFO (Last In First Out) — 마지막에 넣은 것이 먼저 나옵니다.

Push(1) → Push(2) → Push(3)
Stack: [1, 2, 3↑]
Pop() → 3
Pop() → 2

연산	설명	복잡도
Push	삽입	O(1)
Pop	꺼내기	O(1)
Peek	최상단 확인	O(1)

활용: 함수 호출 스택, 괄호 검사, 역순 처리, DFS 구현

4. 큐 (Queue)¶

FIFO (First In First Out) — 먼저 넣은 것이 먼저 나옵니다.

Enqueue(1) → Enqueue(2) → Enqueue(3)
Queue: [1→, 2, 3]
Dequeue() → 1
Dequeue() → 2

연산	설명	복잡도
Enqueue	삽입	O(1)
Dequeue	꺼내기	O(1)

종류¶

원형 큐 (Circular Queue): 배열의 끝과 시작을 연결해 공간 낭비 방지
우선순위 큐 (Priority Queue): 우선순위가 높은 원소부터 꺼냄 (힙으로 구현)
덱 (Deque): 앞뒤 양방향으로 삽입/삭제 가능

활용: BFS 구현, 프린터 대기열, 프로세스 스케줄링

5. 트리 (Tree)¶

계층적 구조의 비선형 자료구조입니다.

        A (루트)
       / \
      B   C
     / \
    D   E (리프)

용어¶

루트(Root): 최상위 노드
리프(Leaf): 자식이 없는 노드
높이(Height): 루트에서 리프까지 최대 거리
차수(Degree): 노드의 자식 수

이진 탐색 트리 (BST)¶

왼쪽 서브트리 < 노드 < 오른쪽 서브트리
탐색/삽입/삭제: 평균 O(log n), 최악 O(n)

트리 순회¶

방식	순서	예시 결과
전위 (Preorder)	노드 → 좌 → 우	5, 3, 2, 4, 7, 9
중위 (Inorder)	좌 → 노드 → 우	2, 3, 4, 5, 7, 9
후위 (Postorder)	좌 → 우 → 노드	2, 4, 3, 9, 7, 5
레벨순회	BFS 방식	5, 3, 7, 2, 4, 9

BST 중위순회 결과 = 오름차순 정렬된 값

균형 이진 트리¶

AVL 트리: 모든 노드의 좌우 높이 차이 ≤ 1, 항상 O(log n) 보장
레드-블랙 트리: Java의 TreeMap, C++ STL map에서 사용

6. 그래프 (Graph)¶

정점(Vertex)과 간선(Edge)으로 이루어진 자료구조입니다.

표현 방식¶

인접 행렬 (Adjacency Matrix)¶

2차원 배열로 표현
간선 확인: O(1), 공간: O(V²)
밀집 그래프에 유리

인접 리스트 (Adjacency List)¶

각 정점의 인접 정점 리스트로 표현
공간: O(V+E)
희소 그래프에 유리

종류¶

구분	설명
무방향 그래프	간선에 방향 없음
방향 그래프	간선에 방향 있음
가중치 그래프	간선에 비용 있음
완전 그래프	모든 정점이 연결됨

7. 힙 (Heap)¶

완전 이진 트리 기반으로 최댓값/최솟값을 빠르게 꺼낼 수 있습니다.

최대 힙: 부모 ≥ 자식 (루트가 최댓값)
최소 힙: 부모 ≤ 자식 (루트가 최솟값)
삽입/삭제: O(log n)
우선순위 큐 구현에 사용

8. 해시 테이블 (Hash Table)¶

키(Key)를 해시 함수로 변환해 인덱스를 구하고 값(Value)을 저장합니다.

평균 탐색/삽입/삭제: O(1)
최악(충돌 심할 때): O(n)

충돌 해결 방법¶

방법	설명
체이닝 (Chaining)	같은 인덱스에 연결 리스트로 연결
개방 주소법	빈 슬롯을 찾아 저장
선형 탐사	다음 빈 슬롯 순서대로 탐색
이차 탐사	제곱 간격으로 탐색
이중 해싱	두 번째 해시 함수로 간격 결정

시험 포인트¶

스택 LIFO / 큐 FIFO 구분 필수
BST 중위순회 = 오름차순 정렬
트리 순회 결과를 직접 추적하는 문제 자주 출제
배열 접근 O(1), 연결 리스트 접근 O(n)
해시 충돌 해결 방법 4가지 암기
우선순위 큐 = 힙으로 구현