자료구조와 알고리즘 핵심 개념 총정리

개발자 채용 면접에서 빠지지 않는 단골 주제이자, 실무에서도 끊임없이 마주치는 자료구조와 알고리즘. 이 글에서는 핵심 개념을 한 곳에 정리합니다.

1. 자료구조 (Data Structures)

자료구조란 데이터를 효율적으로 저장하고 접근·수정하기 위한 구조입니다. 적절한 자료구조 선택은 알고리즘 성능에 직접적인 영향을 미칩니다.

1.1 배열 (Array)

동일한 타입의 데이터를 메모리에 연속적으로 저장하는 가장 기본적인 자료구조입니다.

특징

• 인덱스로 O(1) 시간에 요소 직접 접근 가능
• 크기가 고정됨 (정적 배열 기준)
• 삽입/삭제 시 최악 O(n) — 요소 이동 필요

Index:  [ 0 ] [ 1 ] [ 2 ] [ 3 ] [ 4 ]
Value:  [ 10] [ 20] [ 30] [ 40] [ 50]
Addr:   1000  1004  1008  1012  1016   (int = 4bytes)

언제 사용? 데이터 접근이 빈번하고 크기가 거의 변하지 않을 때

1.2 연결 리스트 (Linked List)

각 노드(Node) 가 데이터와 다음 노드를 가리키는 포인터(reference)로 구성된 자료구조입니다.

종류

• 단순 연결 리스트 (Singly): 한 방향으로만 연결
• 이중 연결 리스트 (Doubly): 앞/뒤 양방향 연결
• 원형 연결 리스트 (Circular): 마지막 노드가 첫 노드를 가리킴

[Head] → [10 | →] → [20 | →] → [30 | null]

언제 사용? 데이터 삽입/삭제가 빈번하고 크기를 미리 알 수 없을 때

1.3 스택 (Stack)

LIFO(Last In, First Out) 구조 — 마지막에 삽입된 데이터가 먼저 나옵니다.

push(1) → push(2) → push(3) → pop()
┌───┐     ┌───┐     ┌───┐     ┌───┐
│   │     │   │     │ 3 │←top │   │
│   │  →  │ 2 │  →  │ 2 │  →  │ 2 │
│ 1 │     │ 1 │     │ 1 │     │ 1 │
└───┘     └───┘     └───┘     └───┘

핵심 연산 (모두 O(1))

실제 활용: 함수 호출 스택(Call Stack), 괄호 짝 맞추기, 브라우저 뒤로 가기, DFS, 수식 계산(후위 표기법)

1.4 큐 (Queue)

FIFO(First In, First Out) 구조 — 먼저 삽입된 데이터가 먼저 나옵니다.

큐의 종류

• 일반 큐: 기본 FIFO 구조
• 덱(Deque): 앞/뒤 모두 삽입·삭제 가능
• 우선순위 큐(Priority Queue): 우선순위 기준으로 처리 (힙으로 구현)
• 원형 큐(Circular Queue): 배열의 공간 낭비를 해결한 형태

실제 활용: 프로세스 스케줄링, 네트워크 패킷 처리, BFS, 프린터 인쇄 대기열

1.5 트리 (Tree)

노드(Node)와 간선(Edge)으로 구성된 계층적(hierarchical) 비선형 자료구조입니다.

        [A]          ← 루트 (Depth 0)
       /   \
     [B]   [C]       ← Depth 1
    / \     \
  [D] [E]  [F]       ← Depth 2 (D, E, F는 리프)

트리 순회 (Tree Traversal)

이진 탐색 트리 (BST)

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

균형 이진 트리

• AVL 트리: 높이 차이 최대 1 유지, 모든 연산 O(log n) 보장
• Red-Black 트리: Java TreeMap, C++ std::map 내부 구현

1.6 그래프 (Graph)

정점(Vertex)과 간선(Edge)으로 이루어진 자료구조. 트리는 그래프의 특수한 형태입니다.

표현 방법 비교

그래프 탐색

1.7 해시 테이블 (Hash Table)

키(Key)를 해시 함수로 변환하여 배열의 인덱스로 사용하는 자료구조입니다. 평균 **O(1)**의 빠른 탐색이 가능합니다.

Key "apple"  →  Hash Function  →  Index 3  →  Array[3] = "apple"
Key "banana" →  Hash Function  →  Index 7  →  Array[7] = "banana"

해시 충돌(Collision) 해결 방법

1. 체이닝 (Chaining): 같은 인덱스에 연결 리스트로 연결
2. 개방 주소법 (Open Addressing): 충돌 시 다른 빈 슬롯을 탐색 (선형 탐사, 이중 해싱)

실제 활용: Python dict, Java HashMap, JavaScript Map, DB 인덱싱, 캐시 구현

2. 알고리즘 복잡도 (Algorithm Complexity)

2.1 Big-O 표기법

가장 나쁜 경우(최악)를 기준으로 표기하며, 상수와 계수는 무시합니다.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)
 상수    로그      선형    선형로그       이차     지수    팩토리얼

💡 실용 가이드: 코딩 테스트에서 n = 10⁶일 때 O(n log n) 이하면 통과 가능. O(n²)은 n ≤ 10,000 정도까지만 허용됩니다.

3. 정렬 알고리즘 (Sorting Algorithms)

3.1 비교 기반 정렬 알고리즘 비교

3.2 핵심 정렬 알고리즘

🔹 병합 정렬 (Merge Sort)

분할 정복(Divide and Conquer) 방식. 배열을 반으로 나누고, 각각 정렬 후 병합합니다.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let l = 0, r = 0;
  while (l < left.length && r < right.length) {
    if (left[l] <= right[r]) result.push(left[l++]);
    else result.push(right[r++]);
  }
  return [...result, ...left.slice(l), ...right.slice(r)];
}

• 항상 O(n log n) 보장 → 안정적인 성능
• 추가 메모리 필요: O(n)
• 연결 리스트 정렬에 특히 적합

🔹 퀵 정렬 (Quick Sort)

피벗(Pivot) 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할합니다.

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  const pivot = partition(arr, lo, hi);
  quickSort(arr, lo, pivot - 1);
  quickSort(arr, pivot + 1, hi);
  return arr;
}

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  return i + 1;
}

• 평균 O(n log n), 최악 O(n²) (피벗이 항상 최솟/최댓값일 때)
• 캐시 효율이 좋아 실제로는 가장 빠른 정렬 중 하나
• 피벗 선택 전략: 랜덤, 중앙값-세-개(Median of Three)

4. 탐색 알고리즘 (Search Algorithms)

4.1 이진 탐색 (Binary Search)

정렬된 배열에서 중간값과 비교하며 범위를 절반씩 줄여가며 탐색합니다.

function binarySearch(arr, target) {
  let left = 0, right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) return mid;
    else if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1; // 찾지 못한 경우
}

• 시간 복잡도: O(log n)
• 전제 조건: 반드시 정렬된 배열이어야 함

4.2 BFS vs DFS

5. 핵심 정리 & 면접 출제 포인트

✅ 자료구조 선택 가이드

빠른 접근이 필요한 경우          →  배열 (Array)
빈번한 삽입/삭제가 필요한 경우    →  연결 리스트 (Linked List)
LIFO 구조가 필요한 경우           →  스택 (Stack)
FIFO 구조가 필요한 경우           →  큐 (Queue)
계층적 데이터 표현이 필요한 경우  →  트리 (Tree)
관계 데이터를 표현해야 하는 경우  →  그래프 (Graph)
빠른 키-값 탐색이 필요한 경우    →  해시 테이블 (Hash Table)

✅ 면접 단골 질문 & 모범 답변

Q1. 스택과 큐의 차이점은?

스택은 LIFO, 큐는 FIFO 구조입니다. 스택은 함수 호출 스택·DFS에, 큐는 프로세스 스케줄링·BFS에 활용됩니다.

Q2. BST의 최악 시간복잡도가 O(n)인 이유는?

정렬된 데이터를 순서대로 삽입하면 트리가 한쪽으로 치우쳐 선형 구조(편향 트리)가 됩니다. 이를 방지하기 위해 AVL 트리, Red-Black 트리 같은 자가 균형 BST를 사용합니다.

Q3. 해시 충돌(Hash Collision)이란?

서로 다른 키가 같은 해시값을 가지는 현상입니다. 체이닝(Chaining) 또는 개방 주소법(Open Addressing)으로 해결합니다.

Q4. 병합 정렬이 퀵 정렬보다 항상 좋은가?

아닙니다. 병합 정렬은 O(n log n)이 보장되지만 추가 메모리(O(n))가 필요합니다. 퀵 정렬은 평균적으로 더 빠르고 캐시 효율이 좋지만, 최악 O(n²)이 될 수 있습니다. 실무에서는 대부분 퀵 정렬의 변형(Intro Sort 등)을 사용합니다.

Q5. DFS와 BFS 중 최단 경로 탐색에 적합한 것은?

BFS입니다. BFS는 가중치 없는 그래프에서 최단 경로를 보장합니다. DFS는 경로 존재 여부나 사이클 탐지에 더 적합합니다.

📌 핵심 키워드

Array · Linked List · Stack · Queue · Tree · Graph · Hash Table · Big-O · Merge Sort · Quick Sort · Binary Search · BFS · DFS

다음 포스트: 운영체제(OS) 핵심 개념 — 프로세스, 스레드, 메모리 관리, 교착상태