[면접을 위한 CS 전공 지식 노트] 5장. 자료구조

Section 1. 복잡도

5.1.1 시간 복잡도 

시간 복잡도란?

• 알고리즘이 실행되는 데 걸리는 시간을 입력 크기(n)에 대한 함수로 표현한 것이다.
• 즉, 입력 크기가 커질수록 알고리즘의 실행 시간이 어떻게 변하는지 분석하는 개념인 것이다.
• 어떠한 알고리즘의 로직이 '얼마나 오랜 시간'이 걸리는지를 알 수 있다.

 

빅오 표기법

• 시간 복잡도의 표기법이다. 
• 입력 범위 n을 기준으로 해서 로직이 몇 번 반복되는지 나타내는 것이다.
• '가장 영향을 많이 끼치는' 항의 상수 인자를 빼고 나머지 항을 없앤다.
• 입력 크기가 커질수록 연산량이 가장 많이 커지는 항만을 고려한다는 원리이다. 
  • 계수와 상수는 무시: O(2n) → O(n), O(5n²) → O(n²)
  • 가장 큰 차수만 남김: O(n² + n) → O(n²)
  • 최악의 경우를 기준으로 분석
• 일반적인 시간 복잡도 유형
  • O(1) → 매우 빠름 (상수 시간)
  • O(log n) → 빠름 (로그 시간)
  • O(n) → 보통 (선형 시간)
  • O(n log n) → 느림 (정렬 알고리즘)
  • O(n²) → 매우 느림 (이중 반복문)
  • O(2ⁿ) → 극도로 비효율적 (지수 증가)

 

자료구조에서의 평균 시간 복잡도

자료 구조	접근	탐색	삽입	삭제
배열(Array)	O(1)	O(N)	O(N)	O(N)
스택(stack)	O(N)	O(N)	O(1)	O(1)
큐(queue)	O(N)	O(N)	O(1)	O(1)
이중 연결 리스트(doubly linked list)	O(N)	O(N)	O(1)	O(1)
해시 테이블(hash table)	O(1)	O(1)	O(1)	O(1)
이진 탐색 트리(BST)	O(logN)	O(logN)	O(logN)	O(logN)
AVL 트리	O(logN)	O(logN)	O(logN)	O(logN)
레드 블랙 트리	O(logN)	O(logN)	O(logN)	O(logN)

 

 

자료구조에서의 최악의 시간 복잡도

자료 구조	접근	탐색	삽입	삭제
배열(Array)	O(1)	O(N)	O(N)	O(N)
스택(stack)	O(N)	O(N)	O(1)	O(1)
큐(queue)	O(N)	O(N)	O(1)	O(1)
이중 연결 리스트(doubly linked list)	O(N)	O(N)	O(1)	O(1)
해시 테이블(hash table)	O(N)	O(N)	O(N)	O(N)
이진 탐색 트리(BST)	O(N)	O(N)	O(N)	O(N)
AVL 트리	O(logN)	O(logN)	O(logN)	O(logN)
레드 블랙 트리	O(logN)	O(logN)	O(logN)	O(logN)

 

5.1.2 공간 복잡도

 

공간 복잡도란?

• 알고리즘이 실행될 때 필요한 메모리 공간을 입력 크기(n)에 따라 분석하는 개념이다. 
• 즉, 프로그램이 실행될 때 얼마나 많은 메모리를 사용하는지를 측정하는 것이다.

공간 복잡도의 표기(빅오 표기법)

O(1) - 상수 공간	입력 크기와 무관하게 일정한 공간 사용	단순한 변수 저장, 입력 크기와 관계없는 계산
O(n) - 선형 공간	입력 크기에 비례하여 메모리 사용 증가	배열, 리스트 저장
O(n²) - 이차 공간	2차원 배열, 행렬 연산 시 사용 공간 증가	그래프 인접 행렬, 동적 계획법(DP)
O(log n) - 로그 공간	입력 크기에 로그 비율로 증가	재귀 호출 시, 호출 스택 사용

 

 

---

Section 2. 선형 자료 구조

선형 자료 구조란?

• 데이터가 순차적으로 나열된 형태의 자료 구조이다.
• 데이터들이 일렬로 정렬되어 있으며, 특정 규칙에 따라 앞뒤로 연결된 구조를 가진다. 

 

5.2.1 연결 리스트 🔗

• 노드(데이터 포함됨)들을 포인터로 연결해서 공간적인 효율성을 극대화시킨 자료 구조이다. 
• 특징
  • 연속된 메모리 공간이 필요 없음 → 동적 크기 할당 가능.
  • 삽입/삭제가 빠름 (O(1)) → 포인터만 변경하면 됨.
  • 임의 접근이 느림 (O(n)) → 특정 위치의 데이터를 찾으려면 처음부터 탐색해야 함.
   

• prev 포인터와 next 포인터로 앞과 뒤의 노드를 연결시킨 것이다.
• 종류
  • 싱글 연결 리스트: next 포인터만 가진다.
  • 이중 연결 리스트: next 포인터와 prev 포인터를 가진다. 
  • 원형 이중 연결 리스트: 이중 연결 리스트와 같지만 마지막 노드의 next 포인터가 헤드 노드를 가리키는 것을 말한다. 

 

5.2.2 배열 📦

• 같은 데이터 타입의 요소들이 연속된 메모리 공간에 저장되는 구조
• 특징
  • 임의 접근 가능 (O(1)) → 특정 위치의 데이터에 빠르게 접근 가능.
  • 크기 변경이 어렵다 → 정적 크기 할당이 필요.
  • 삽입/삭제가 느림 (O(n)) → 중간에 데이터를 추가/삭제하면 이동이 필요.
  • 중복을 허용하고 순서가 있다

• 순차적 접근과 랜덤 접근
  • 순차적 접근
    • 배열의 데티어를 처음부터 끝까지 차례대로 탐색하는 방식
    • for num in arr: print(num) #O(N)
  • 랜덤 접근
    • 배열의 특정 위치(index)에 직접 접근하는 방식 
    • print(arr[2]) #O(1)

 

[배열과 연결 리스트 비교]

 

비교 항목	배열(Array)	연결 리스트(Linked List)
메모리 구조	연속된 메모리 공간에 저장	노드들이 포인터로 연결되어 비연속적으로 저장
데이터 접근	랜덤 접근 가능 (O(1))	순차 접근만 가능 (O(n))
삽입/삭제	중간에 삽입/삭제 시 데이터 이동 필요 (O(n))	노드 포인터만 변경하면 됨 (O(1))
검색 속도	특정 인덱스 검색 O(1), 특정 값 검색 O(n)	특정 노드 검색 O(n)
메모리 사용	고정 크기 할당 (공간 낭비 발생 가능)	동적 크기 할당 가능 (필요한 만큼만 사용)
구현 난이도	간단함 (배열 선언 후 사용 가능)	상대적으로 복잡함 (노드와 포인터 관리 필요)
추가 공간	데이터만 저장 (추가 메모리 필요 없음)	각 노드마다 추가 포인터 저장 공간 필요
연속된 데이터 저장	가능 (메모리 공간 확보 필요)	불가능 (메모리 조각화 발생 가능)
사용 사례	고정 크기 데이터 저장, 빠른 조회가 필요한 경우	삽입/삭제가 빈번한 경우, 동적 크기 데이터 관리 필요

 

5.2.3 벡터 

• 동적 배열(Dynamic Array)의 한 종류로, 크기를 자동으로 조절할 수 있는 배열이다 .
• 배열의 크기가 고정되어 있지 않고 필요할 때 자동으로 확장되거나 축소된다. 

벡터의 특징

특징	설명
동적 크기 조절	요소를 추가하면 크기가 자동으로 늘어나고, 요소를 삭제하면 필요에 따라 줄어듦
연속된 메모리 할당	일반 배열처럼 메모리상에서 연속된 공간을 사용
랜덤 접근 가능	배열과 동일하게 O(1) 시간에 특정 요소에 접근 가능
삽입/삭제 효율성	마지막 요소 추가/삭제는 O(1), 중간 삽입/삭제는 O(n)
자동 확장(Resize)	크기가 부족하면 기존 크기의 2배로 확장
자동 축소	요소가 일정 비율 이하로 줄어들면 메모리 사용을 줄이기 위해 축소

 

 

5.2.4 스택 

• 후입선출(LIFO, Last In First Out) 방식의 자료 구조
• 한쪽 끝(Top)에서만 삽입/삭제 가능.
• 사용사례
  • 재귀 호출, 함수 호출 스택
  • 웹 브라우저 방문 기록 등에 사용.
• 시간 복잡도:
  • 삽입/삭제 → O(1)
  • 검색 → O(n)
   

 

5.2.5 큐

• 선입선출(FIFO, First In First Out) 방식의 자료 구조
• 먼저 들어온 데이터가 먼저 나감.
• 사용사례:
  • CPU 작업을 기다리는 프로세스
  • 스레드 행렬
  • 네트워크 접속을 기다리는 행렬
  • 너비 우선 탐색
  • 캐시
• 시간 복잡도:
  • 삽입/삭제 → O(1)
  • 검색 → O(n)
   

 

---

Section 3. 비선형 자료 구조

비선형 자료 구조란?

데이터가 순차적으로 저장되지 않고, 복잡한 관계를 가지는 자료 구조입니다. 즉, 데이터가 연결 리스트나 배열처럼 일렬로 나열되지 않고, 트리(Tree)나 그래프(Graph)처럼 계층적 구조나 네트워크 형태로 저장됩니다.

특징	설명
순차적 접근이 어려움	선형 자료 구조(배열, 리스트)처럼 인덱스로 직접 접근할 수 없음
노드(Node)와 간선(Edge) 개념 사용	데이터 간의 관계를 나타내는 연결 구조를 가짐
계층적 구조 or 네트워크 구조	트리는 부모-자식 관계, 그래프는 복잡한 연결 관계
동적인 크기	필요에 따라 크기를 유동적으로 변경할 수 있음
검색, 탐색, 경로 찾기 등이 주 목적	특정 노드 검색, 최단 경로 찾기 등에 사용

 

 

5.3.1 그래프

• 여러 개의 노드(Node)와 간선(Edge)으로 이루어진 네트워크 형태의 자료 구조
• 특징
  • 순환(Cycle)이 존재할 수도 있음.
  • 두 노드 간의 관계를 방향(Directed) 또는 무방향(Undirected)으로 표현.
  • 사용 사례:
    • SNS 친구 추천 (Facebook, Twitter)
    • 네트워크 라우팅 (인터넷, 네트워크 연결)
    • 지도 길찾기 알고리즘 (Dijkstra, A 알고리즘)

그래프의 유형

그래프 종류	설명
무방향 그래프 (Undirected Graph)	모든 간선이 양방향 (A ↔ B).
방향 그래프 (Directed Graph, Digraph)	간선이 한 방향으로만 연결됨 (A → B).
가중 그래프 (Weighted Graph)	간선에 가중치(Weight)가 있음 (예: 도로 거리).
비가중 그래프 (Unweighted Graph)	간선에 가중치가 없음.
연결 그래프 (Connected Graph)	모든 정점이 연결됨 (어떤 정점에서도 다른 정점으로 이동 가능).
비연결 그래프 (Disconnected Graph)	일부 정점이 연결되지 않음.
사이클 그래프 (Cyclic Graph)	특정 정점에서 시작하여 다시 돌아올 수 있음.
비순환 그래프 (Acyclic Graph)	사이클이 없는 그래프 (예: 트리).

 

5.3.2 트리

• 계층적인 구조를 가지며 부모-자식 관계로 연결된 데이터 구조
• 루프 노드, 내부 노드, 리프 노드 등으로 구성된다. (집합: 숲)

 

• 특징
  • 루트(Root) 노드에서 시작하여 여러 개의 자식 노드로 확장됨.
  • 부모 노드는 여러 개의 자식을 가질 수 있지만, 자식 노드는 하나의 부모만 가짐.
  • 순환(Cycle)이 없음.
• 사용 사례:
  • 파일 시스템 (디렉토리 구조)
  • 이진 탐색 트리(Binary Search Tree, BST)
  • HTML/XML 파싱

트리의 높이와 레벨

• 트리 높이(Height): 루트 노드에서 가장 깊은 리프 노드까지의 최대 거리(간선 개수).
• 노드의 레벨(Level): 루트에서 해당 노드까지의 깊이(간선 개수). 깊이랑 비슷한 개념.
• 높이가 작을수록 탐색이 빠르고, 레벨은 BFS 탐색에서 활용.

 

 

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

• 이진 탐색 트리(BST)는 각 노드가 최대 두 개의 자식을 가지면서, 왼쪽 자식은 작은 값, 오른쪽 자식은 큰 값을 저장하는 트리입니다.
• 규칙
  • 왼쪽 서브트리의 모든 값 < 부모 노드 값.
  • 오른쪽 서브트리의 모든 값 > 부모 노드 값.
  • 중복된 값은 일반적으로 허용되지 않음.
• 장점
  • 탐색, 삽입, 삭제 연산이 평균적으로 O(log n)
  • 중위 순회(Inorder Traversal)하면 오름차순 정렬됨
  • 이진 탐색이 가능하여 빠른 탐색 가능
• 단점
  • 탐색 성능이 최악의 경우 O(n)이 걸림
    • 왜? - 삽입 순서에 따라 선형적일 수 있음(한쪽으로 치우친 불균형의 트리)

 

 

AVL 트리

• 앞서 설명한 최악의 경우 선형적인 트리가 되는 것을 방지하고 스스로 균형을 잡는 이진 탐색 트리이다.
• 두 자식 서브트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있다.
• 장점
  
  • 탐색, 삽입, 삭제 모두 시간 복잡도 - O(logN) 
• 단점
  • 삽입, 삭제를 할 때마다 균형이 안 맞는 것을 맞추기 위해 트리 일부를 왼쪽 혹은 오른쪽으로 회전시키며 균형을 잡는다. 

 

레드 블랙 트리

• 레드-블랙 트리는 균형 잡힌 BST의 일종으로, 삽입과 삭제 시 균형을 유지하기 위해 색깔 규칙을 적용한 트리이다.
  1. 각 노드는 빨간색(Red) 또는 검은색(Black) 중 하나.
  2. 루트 노드는 항상 검은색(Black).
  3. 어떤 노드도 연속된 빨간색(Red) 노드를 가질 수 없음.
  4. 모든 리프 노드(NULL 노드)는 검은색(Black).
  5. 어떤 노드에서 자손 리프 노드까지의 검은색 노드 개수는 항상 동일해야 함.
• 장점
  • BST보다 균형이 유지됨 → O(log n) 보장
  • AVL보다 삽입/삭제 연산이 빠름 (회전이 적음)
  • 탐색 성능이 안정적
• 단점
  • AVL보다 탐색이 약간 느릴 수 있음 (균형이 100% 맞춰지지는 않음)
  • 구현이 복잡함

 

[이진 탐색 트리, AVL 트리, 레드-블랙 트리 비교]

구분	이진 탐색 트리 (BST)	AVL 트리	레드-블랙 트리
균형 유지	❌ (균형 깨질 수 있음)	✅ (항상 균형 유지)	✅ (약간의 불균형 허용)
탐색 속도	O(log n) (최악 O(n))	O(log n)	O(log n)
삽입/삭제 속도	O(log n) (최악 O(n))	O(log n) (회전 발생)	O(log n) (AVL보다 회전 적음)
회전 연산	❌ 없음	✅ 자주 발생	✅ 가끔 발생
구현 난이도	쉬움	어려움	매우 어려움
사용 예시	일반적인 데이터 저장	검색이 중요한 시스템	데이터베이스, 운영체제

 

5.3.3 힙

• 우선순위를 기준으로 정렬되는 완전 이진 트리이다.
• 항상 특정 우선순위를 가지는 노드(최댓값 또는 최솟값)가 루트에 위치하는 트리이다. 
  • 최대힙: 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 가장 커야 함. 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 함. 
  • 최소힙: 최소힙에서 루트 노드에 있는 키는 모든 자식에 있는 키 중에서 최솟값이어야 함. 각 노드의 자식 노드와의 관계도 이와 같은 특징이 재귀적으로 이루어져야 함
• 힙의 시간 복잡도
  • 삽입: O(logN)
  • 삭제: O(logN)
  • 최대/최소값 조회: O(1)
  • 힙 정렬: O(N logN) 
• 사용 사례
  • 우선순위 큐: 운영체제 스케줄링, 다익스트라 최단 경로 알고리즘
  • 힙 정렬: O(NlogN)
  • 실시간 데이터 스트림: 최대값/ 최소값 빠르게 찾아야 하는 문제
  • 네트워크 패킷 스케줄링: 가장 우선순위 높은 패킷을 먼저 처리
• 최대힙의 삽입
  • 해당 노드 위에 있는 노드와 스왑하는 과정을 거쳐 최대힙 조건을 만족하게 됨. 

5.3.4 우선순위 큐

 

• 우선순위(priority)를 기준으로 가장 높은(낮은) 우선순위를 가진 요소를 먼저 꺼내는 자료구조.
• 일반적인 큐(Queue)는 FIFO(First-In, First-Out) 방식이지만, 우선순위 큐는 우선순위가 높은 데이터를 먼저 반환.
• 힙(Heap) 자료구조를 기반으로 구현됨.
• 특징
  • 최댓값 또는 최솟값을 빠르게 찾을 수 있음.
  • 힙(Heap)으로 구현하면 O(log n)의 시간 복잡도.
  • 우선순위를 기준으로 삽입/삭제가 수행됨.
• 동작방식
  • 삽입(Enqueue) → 요소를 우선순위에 따라 저장 (O(log n)).
  • 삭제(Dequeue) → 최우선순위 요소 제거 (O(log n)).
  • 우선순위 비교 → 힙을 이용하여 빠르게 정렬 유지

 

5.3.5 맵

 

• 키(Key)와 값(Value) 쌍으로 데이터를 저장하는 자료구조.
• 빠른 검색(O(1)~O(log n)), 삽입(O(1)), 삭제(O(1))을 제공.
• Python에서는 딕셔너리(Dictionary), Java에서는 HashMap, C++에서는 std::map으로 구현됨.
• 특징
  
  • 키는 유일해야 하며, 중복되지 않음
  • 값(Value)은 중복 가능
• 동작 방식
  • 삽입(Put) → (Key, Value) 형태로 데이터 저장.
  • 검색(Get) → 키(Key)를 이용해 데이터 조회.
  • 삭제(Delete) → 특정 키(Key)를 삭제.

 

5.3.6 셋

• 중복을 허용하지 않고 오로지 unique 값만 저장하는 데이터 집합.
• 빠른 삽입, 삭제, 검색(O(1))을 제공.
• Python의 set, Java의 HashSet, C++의 unordered_set으로 구현됨.
• 특징
  • 중복 값 저장 불가능.
  • 순서 보장 없음.
  • 해시 테이블(Hash Table) 기반으로 동작.
  • 검색, 삽입, 삭제가 O(1)~O(log n).
• 동작방식
  • 삽입(Add) → 중복 없이 데이터 저장.
  • 삭제(Remove) → 특정 요소 제거.
  • 검색(Contains) → 특정 요소 존재 여부 확인.

5.3.7 해시 테이블 

• 키(Key) 값을 해시 함수(Hash Function)를 사용하여 특정 메모리 주소에 저장하는 자료구조.
• 무한에 가까운 데이터들을 유한한 개수의 해시 값으로 매핑한 테이블.
• 삽입, 삭제, 탐색 시 평균적으로 O(1)의 시간 복잡도를 가지며 unordered_map으로 구현함.
• 맵(Map), 딕셔너리(Dictionary), 셋(Set) 등의 내부 구현에 사용됨.
• 충돌 해결(Collision Resolution) 기법 필요 (체이닝, 개방 주소법).
• 특징
  • 빠른 검색, 삽입, 삭제 (평균 O(1), 최악 O(n))
  • 해시 충돌이 발생할 수 있음
  • 충돌 해결 기법(체이닝, 개방 주소법) 필요
• 동작방식
  • 해시 함수(Hash Function) 적용 → 키(Key)를 특정 메모리 주소로 변환.
  • 버킷(Bucket)에 저장 → 키-값 쌍을 저장.
  • 검색 시 해시 함수로 주소 조회