코딩테스트 대비 자료구조 정리: 꼭 알아야 할 핵심 개념과 활용 예시

자료구조 정리

 

1. 배열 (Array)

개념

• 선형 자료구조 (Linear) – 인덱스로 원소에 접근
• 메모리 상에서 연속된 공간에 저장
• 고정 크기 배열 vs 동적 배열

 

시간 복잡도 (N = 원소 개수)

연산 시간	복잡도	설명
인덱스 접근 (access)	O(1)	시작 주소 + 인덱스로 바로 계산
값 변경 (update)	O(1)	접근만 하면 됨
초기화 (size N 생성)	O(N)	N칸 메모리 할당 & 기본값 채우기
맨 뒤에 삽입 (append)	보통 O(1) (암시적) / 최악 O(N)	동적 배열 resize 시 복사 비용
맨 뒤에서 삭제 (pop)	O(1)	마지막 원소만 제거
중간에 삽입 (insert i)	O(N)	뒤에 있는 것들 전부 한 칸씩 밀기
중간에서 삭제 (delete i)	O(N)	뒤에 있는 것들 한 칸씩 당기기

 

고정 vs 동적 배열

• 고정 배열: 크기 변경 불가, 생성 시 N칸 한 번에 잡음
• 동적 배열 (JS [], 파이썬 list)
  • 내부적으로 더 큰 고정 배열을 새로 만들고 복사하는 식으로 사이즈 늘림
  • 보통 “충분히 크게”(예: 2배) 늘려서 평균 append = O(1) 암티화로 간주

 

 

---

2. 단일 연결 리스트 (Singly Linked List)

개념

• 선형 구조지만, 배열처럼 연속 메모리가 아니라,
  각 **노드(node)**가 value와 next 포인터를 가지고 체인처럼 연결
• head (맨 앞 노드)에 대한 참조를 보관

[ val | next ] -> [ val | next ] -> [ val | next ] -> null

 

기본 연산

연산 시간	복잡도	설명
i번째 원소 접근 (index access)	O(N)	head부터 차례로 next 따라감
맨 앞 삽입 (insert front)	O(1)	새 노드의 next = 기존 head, head 교체
맨 앞 삭제 (delete front)	O(1)	head = head.next
맨 뒤 삽입/삭제 (naive 구현)	O(N)	tail까지 순회 필요
임의 위치 삽입/삭제 (중간)	O(N)	해당 노드/이전 노드 찾기 위해 순회

 

원형 단일 리스트(circular) + tail을 저장하면:

• tail.next = head 로 원형
• tail을 알고 있으면:
  • 끝에 삽입 / 삭제, 앞에서 삭제/삽입 등을 더 효율적으로 할 수 있음 (구현 방식에 따라 O(1) 가능)

 

 

---

3. 이중 연결 리스트 (Doubly Linked List)

개념

• 각 노드가 value, next, prev 를 가짐

null <- [ prev | val | next ] <-> [ prev | val | next ] <-> ... -> null

• 앞/뒤 양방향 순회 가능

 

장점

• 어떤 노드를 이미 가리키고 있을 때:
  • 그 앞/뒤에 삽입·삭제를 O(1) 에 가능
• 음악 플레이어, 브라우저 히스토리처럼 앞/뒤 이동이 많은 경우 유리

 

단점

• 포인터가 하나 더 있어서 메모리 사용량 증가
• 삽입/삭제 시 업데이트해야 할 포인터가 더 많아 구현이 더 복잡

 

 

---

4. 큐 (Queue)

개념

• 선형 구조, FIFO (First In, First Out) – “줄 서기/대기열”
• 연산 이름:
  • enqueue / push / offer : 뒤에 넣기
  • dequeue / pop / poll : 앞에서 빼기
  • front / peek : 맨 앞 값만 보기
  • isEmpty : 비었는지 확인

 

타임 컴플렉시티 목표

연산 목표	시간 복잡도
enqueue	O(1)
dequeue	O(1)
front/peek	O(1)
isEmpty	O(1)

 

구현

• 배열로 front에서 빼면 → 요소들을 당겨야 해서 O(N) (비효율)
• 그래서 보통
  • 연결 리스트 + head/tail 포인터 로 구현
  • 또는 원형 버퍼(circular buffer) 로 구현

 

 

---

5. 스택 (Stack)

개념

• 선형 구조, LIFO (Last In, First Out) – “접시 더미”
• 연산:
  • push : 위에 쌓기
  • pop : 위에서 하나 빼기
  • top / peek : 위 값만 보기
  • isEmpty

 

시간 복잡도	연산 시간
push	O(1)
pop	O(1)
peek/top	O(1)
isEmpty	O(1)

 

구현

• 보통 배열 하나로 충분 (끝에서 push/pop만 하니까)
• 활용 예시
  • 브라우저 뒤로가기
  • 함수 호출 스택 (재귀)
  • 괄호 검사, DFS 구현 등

 

재미있는 응용: 스택 2개로 큐 만들기

• in 스택으로 들어오는 것 저장, out 스택으로 나갈 것 저장
• dequeue 시 out이 비어 있으면 in의 모든 원소를 out으로 옮겨서 순서 뒤집기

 

 

---

6. 이진 트리 (Binary Tree)

개념

• 각 노드가 최대 2개의 자식 (left, right)을 가지는 트리 구조
• 용어:
  • root(루트), child(자식), parent(부모)
  • leaf(리프): 자식이 없는 노드
  • height(높이): 루트에서 가장 깊은 노드까지의 간선 수
  • depth(깊이): 특정 노드에서 루트까지의 간선 수

 

트리 순회(Traversal) – DFS 변형 3종

전부 재귀나 스택으로 구현 가능:

1. In-order (중위 순회)
   • Left → Node → Right
2. Pre-order (전위 순회)
   • Node → Left → Right
3. Post-order (후위 순회)
   • Left → Right → Node

BFS 순회는 큐 사용 (레벨 순서대로)

 

트리의 형태들

• Full Binary Tree
  • 모든 노드가 자식이 0개 또는 2개
• Complete Binary Tree
  • 마지막 레벨을 제외하고 모든 레벨이 꽉 차 있음
  • 마지막 레벨의 노드는 왼쪽부터 연속해서 채워져 있음
• Perfect Binary Tree
  • 모든 레벨이 꽉 차 있음 (leaf 모두 같은 depth)
• Balanced Binary Tree (대략적 의미)
  • 어느 노드에서도 왼쪽/오른쪽 서브트리의 높이 차가 1 이내

 

 

---

7. 이진 탐색 트리 (BST, Binary Search Tree)

핵심 속성

• 각 노드에 대해:
  • 왼쪽 서브트리의 모든 값 < 현재 노드 값
  • 오른쪽 서브트리의 모든 값 > (또는 ≥) 현재 노드 값
• 이 조건 덕분에 검색/삽입/삭제를 빠르게 할 수 있음

 

시간 복잡도 (H = 트리 높이)

연산	시간 복잡도	설명
검색(search)	O(H) (평균 O(log N))	값 비교하며 좌/우로 내려감
삽입(insert)	O(H)	검색 로직으로 위치 찾은 뒤 leaf에 삽입
삭제(delete)	O(H)	경우에 따라 처리 (0, 1, 2 자식)

 

삭제 케이스 요약

1. 자식 0개 (leaf):
   • 그냥 부모에서 해당 링크 끊기
2. 자식 1개:
   • 부모가 가리키던 포인터를 자식 노드로 교체
3. 자식 2개:
   • 두 방법 중 하나 선택
     • 왼쪽 서브트리에서 최댓값 찾기 (가장 오른쪽 leaf)
     • 또는 오른쪽 서브트리에서 최솟값 찾기 (가장 왼쪽 leaf)
   • 그 노드의 값을 현재 노드로 복사
   • 그 노드를 1번 또는 2번 케이스로 삭제

 

주의 – 최악 경우

• 값들이 정렬된 순서로 삽입되면 BST가 한쪽으로 기운 linked list처럼 변해서
  • 높이 H ≈ N-1
  • 시간 복잡도 O(N) 으로 퇴화
• 그래서 실무/라이브러리에서는 self-balancing BST (AVL, Red-Black tree 등) 을 사용

 

 

---

8. 힙 (Heap) – (강의에서는 Max Heap 위주)

개념

• 완전 이진 트리 + 힙 속성
• Max heap: 부모 노드 ≥ 자식 노드
• Min heap: 부모 노드 ≤ 자식 노드
• 항상 루트가 최대값(또는 최소값) 이라,
  우선순위 큐(priority queue) 구현에 쓰기 좋음

 

배열로 구현하는 이유

• 힙은 항상 완전 이진 트리 → 배열 인덱스로 부모/자식 계산 가능

 

인덱스 i 에서:

• 왼쪽 자식: left = 2*i + 1
• 오른쪽 자식: right = 2*i + 2
• 부모: parent = floor((i - 1) / 2)

 

연산

연산 시간	복잡도	설명
peek (최댓값/최솟값)	O(1)	루트
insert (push)	O(log N)	마지막에 넣고 위로 “sift up”
extract-max / extract-min	O(log N)	루트와 마지막 노드를 교환, 마지막 제거 후 아래로 “sift down”

 

Heapify / Heap Sort 개념

• 임의 배열을 힙으로 만드는 과정: heapify
• 배열 전체를 힙으로 만든 뒤,
  최대/최소를 하나씩 뽑아 새 배열에 담으면 → Heap Sort (O(N log N))

 

---

9. 그래프 (Graph)

개념

• 정점(vertex / node) + 간선(edge)의 집합
• 굉장히 일반적인 구조:
  친구 관계, 도로망, 네트워크, 환율, 의존성 등 표현 가능

 

용어

• 정점 (vertex): 노드
• 간선 (edge): 정점 사이의 연결
• 인접(adjacent): 간선으로 직접 연결된 정점
• 이웃(neighbor): 같은 의미

 

그래프의 종류

• 무방향 그래프 (undirected)
  • 간선 (u, v) = (v, u)
• 방향 그래프 (directed)
  • 간선 (u, v) 는 u→v 방향만
• 가중치 그래프 (weighted)
  • 간선마다 비용/거리 같은 weight 존재
• 비가중치 그래프 (unweighted)
  • weight가 없거나 모두 동일하다고 보는 경우
• 사이클(graph cycle)
  • 어떤 정점에서 시작해서 방향을 따라 다시 자기 자신으로 되돌아오는 경로
• 사이클 그래프(cyclic) vs 비순환 그래프(acyclic)
• 연결/비연결(disconnected) 그래프
  • 어떤 정점에서 다른 정점으로 갈 수 없는 경우 존재 → disconnected

 

표현 방식

1. 인접 행렬 (Adjacency Matrix)
   • V개의 정점 → V×V 2D 배열
   • matrix[i][j] = 1 (간선 있음) or weight
   • 공간: O(V²) – 밀도가 높은 그래프에 유리
2. 인접 리스트 (Adjacency List)
   • 각 정점마다 “연결된 정점 리스트” 보관
   • 공간: O(V + E) – sparse 그래프에 유리

 

 

---

10. 해싱 / 해시 (Hashing) – 맛보기

강의 마지막 부분에서 막 시작된 내용:

개념

• 어떤 입력 데이터(문자열, 숫자 등)를 hash 함수에 넣어서
  고정 길이의 “이상한 숫자/문자열”로 바꾸는 것
• 이 결과를 hash / digest라고 부름

input:  "hi"  ──>  hash_function ──>  4732 (예시)

 

특징 (이상적인 해시 함수)

• 같은 입력 → 항상 같은 출력
• 다른 입력 → 충돌(collison)이 적게 발생
• 출력값이 균등하게 분포 (버킷 골고루 사용)

 

이 해싱 아이디어를 바탕으로

• Hash Table / Hash Map (파이썬 dict, JS Object/Map 등) 에서
  • key 를 hash해서 배열 인덱스로 사용 → 평균적으로 **O(1)**에
    • 삽입, 검색, 삭제 가능

 

 

---

마지막으로 – 이걸 어떻게 활용하면 좋을까?

이 긴 스크립트를 기반으로 공부할 때는:

1. 자료구조별로 “한 줄 정의 + 대표 연산 + 빅오” 를 외운다.
2. 각 구조에 대해 꼭 떠올릴 수 있어야 할 것:
   • 언제 쓰는지 (사용 예시 1~2개)
   • 어떤 연산이 빠르고, 어떤 연산이 느린지
3. 코딩테스트/LeetCode에서는:
   • Queue, Stack, Heap, HashMap, BST-ish (정렬 + 이분 탐색) 정도만 제대로 써도 문제 절반 이상 커버됨.