“배열을 써야 할까, 해시맵을 써야 할까?” 코딩 테스트를 풀 때도, 실무 시스템을 설계할 때도, 기술 면접에서 화이트보드 앞에 섰을 때도 이 질문은 항상 따라옵니다. 자료구조 선택 가이드가 필요한 이유는 자료구조 하나의 선택이 코드 전체의 시간복잡도와 공간복잡도를 결정하기 때문입니다. 배열 대신 해시맵을 선택하는 것만으로 O(n)이던 탐색이 O(1)로 바뀌고, 큐 대신 힙을 선택하는 것으로 O(n log n)이던 정렬이 O(log n)의 삽입으로 대체됩니다. 오늘은 각 자료구조의 내부 동작 원리·시간복잡도·강점·약점을 완전히 분석하고, “어떤 상황에서 무엇을 선택해야 하는가”를 의사결정 트리와 실무 코드 예시로 완전히 정리해 드립니다.
목차
- 자료구조 선택의 핵심 원칙 — 무엇을 기준으로 고르는가
- 선형 자료구조 완전 분석 — 배열·연결리스트·스택·큐
- 해시 기반 자료구조 — 해시맵·해시셋의 원리와 선택 기준
- 트리 기반 자료구조 — 이진탐색트리·힙·트라이
- 그래프와 고급 자료구조 — 언제 필요하고 어떻게 선택하는가
- 자료구조 선택 의사결정 트리 — 상황별 최종 정리
1. 자료구조 선택의 핵심 원칙 — 무엇을 기준으로 고르는가
자료구조를 선택하는 것은 연장통에서 도구를 꺼내는 것과 같습니다. 못을 박을 때는 망치가 최선이지만, 나사를 조일 때 망치를 쓰면 오히려 망가집니다. 자료구조도 마찬가지로 문제의 성격에 맞는 도구를 선택해야 합니다.
판단 기준 1. 어떤 연산이 가장 빈번한가
자료구조 선택에서 가장 먼저 물어야 할 질문은 “이 데이터에서 가장 자주 수행하는 연산이 무엇인가”입니다. 같은 데이터를 담더라도 주로 탐색을 할지, 삽입·삭제를 할지, 정렬이 필요한지에 따라 최적 자료구조가 완전히 달라집니다.
주요 연산 빈도에 따른 1차 선택 기준:
탐색(조회)이 90% 이상 → 해시맵, 배열(인덱스 접근)
삽입·삭제가 잦음 → 연결리스트, 해시맵
정렬된 상태 유지 필요 → 이진탐색트리, 정렬 배열
최솟값·최댓값 빠른 접근 → 힙(우선순위 큐)
중복 없는 집합 관리 → 해시셋
계층적 데이터 표현 → 트리
관계·경로 표현 → 그래프판단 기준 2. 시간복잡도 빅오(Big-O) 비교표
자료구조 선택의 객관적 기준은 각 연산의 시간복잡도입니다. 아래 표를 기준점으로 삼고, 병목이 될 연산의 복잡도를 최소화하는 자료구조를 선택합니다.
| 자료구조 | 접근 | 탐색 | 삽입 | 삭제 | 비고 |
|---|---|---|---|---|---|
| 배열(Array) | O(1) | O(n) | O(n) | O(n) | 인덱스 접근 최강 |
| 연결리스트 | O(n) | O(n) | O(1)* | O(1)* | *노드 위치 알 때 |
| 스택 | O(n) | O(n) | O(1) | O(1) | top만 접근 |
| 큐 | O(n) | O(n) | O(1) | O(1) | front/rear만 접근 |
| 해시맵 | O(1)** | O(1)** | O(1)** | O(1)** | **평균, 최악 O(n) |
| 이진탐색트리(균형) | O(log n) | O(log n) | O(log n) | O(log n) | 정렬 유지 |
| 힙 | O(1)*** | O(n) | O(log n) | O(log n) | ***min/max만 O(1) |
| 트라이 | O(m) | O(m) | O(m) | O(m) | m=문자열 길이 |
| 그래프 | — | O(V+E) | O(1) | O(E) | V=정점, E=간선 |
판단 기준 3. 메모리 효율과 공간복잡도
시간복잡도만큼 중요한 것이 공간복잡도입니다. 해시맵은 빠른 탐색을 위해 배열 대비 더 많은 메모리를 사용합니다. 연결리스트는 각 노드마다 다음 노드 포인터를 추가로 저장합니다. 제한된 메모리 환경(임베디드 시스템, 모바일, 캐시 레이어)에서는 시간복잡도를 일부 희생하더라도 공간 효율적인 자료구조를 선택해야 합니다.
판단 기준 4. 데이터의 정적·동적 성격
데이터 크기가 고정되어 있고 미리 알 수 있다면 배열이 가장 효율적입니다. 반면 데이터가 런타임에 계속 추가·삭제된다면 동적으로 크기를 조절할 수 있는 연결리스트, 동적 배열(ArrayList/Vector), 해시맵을 고려합니다.
2. 선형 자료구조 완전 분석 — 배열·연결리스트·스택·큐
선형 자료구조는 데이터가 순서대로 나열된 구조입니다. 가장 기본적이면서도 실무에서 가장 자주 사용되는 자료구조 그룹입니다.
배열(Array) — 인덱스 접근이 전부다
배열은 메모리에 데이터를 연속적으로 저장하는 자료구조입니다. 이 “연속성”이 배열의 모든 장점과 단점을 만들어냅니다. 인덱스로 임의 위치에 O(1)로 접근할 수 있는 것이 최대 강점이고, 중간 삽입·삭제 시 이후 요소를 모두 이동해야 하는 것이 O(n)으로 느린 이유입니다.
python
# 배열이 최선인 경우
# 1. 인덱스 기반 임의 접근이 빈번할 때
scores = [85, 92, 78, 95, 88]
third_score = scores[2] # O(1) — 즉시 접근
# 2. 크기가 고정되어 있고 순서가 중요할 때
days_of_week = ["월", "화", "수", "목", "금", "토", "일"]
# 3. 수학적 연산·행렬 계산
import numpy as np
matrix = np.array([[1, 2], [3, 4]])
result = matrix @ matrix # 행렬 곱
# 배열이 약한 경우 — 중간 삽입은 O(n)
students = ["Alice", "Bob", "Dave"]
students.insert(2, "Charlie") # Charlie 삽입 위해 Dave 밀어야 함 → O(n)배열을 선택해야 하는 신호:
- 인덱스(위치)로 데이터를 자주 조회한다
- 데이터 크기가 고정되거나 거의 변하지 않는다
- 캐시 지역성(Cache Locality)이 중요한 고성능 연산을 한다
- 순서가 있는 데이터를 순차적으로 처리한다
연결리스트(Linked List) — 삽입·삭제의 제왕
연결리스트는 각 노드가 데이터와 다음 노드의 포인터를 함께 저장하는 구조입니다. 메모리에 흩어져 있어도 되기 때문에 삽입·삭제가 O(1)이지만(위치를 알 때), 특정 위치 접근은 처음부터 따라가야 해서 O(n)입니다.
python
# 연결리스트 직접 구현
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def prepend(self, data): # 맨 앞 삽입 O(1)
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def delete_node(self, target_data): # 삭제 O(n) 탐색 + O(1) 삭제
if not self.head:
return
if self.head.data == target_data:
self.head = self.head.next
return
current = self.head
while current.next:
if current.next.data == target_data:
current.next = current.next.next # 포인터만 변경 O(1)
return
current = current.next
# 실무에서는 Python deque, Java LinkedList로 사용
from collections import deque
# deque — 양방향 연결리스트 기반, 양끝 O(1) 삽입·삭제
dq = deque([1, 2, 3])
dq.appendleft(0) # 왼쪽 삽입 O(1)
dq.append(4) # 오른쪽 삽입 O(1)
dq.popleft() # 왼쪽 삭제 O(1)연결리스트를 선택해야 하는 신호:
- 리스트 앞·중간에 빈번한 삽입·삭제가 필요하다
- 데이터 크기가 런타임에 크게 변동한다
- 큐·스택의 기반 자료구조로 활용할 때
스택(Stack) — LIFO의 힘
스택은 가장 마지막에 넣은 데이터를 가장 먼저 꺼내는 LIFO(Last In, First Out) 구조입니다. 후입선출이 필요한 거의 모든 문제에서 스택이 해법의 핵심입니다.
python
# 스택의 대표 사용 사례 1. 괄호 유효성 검사
def is_valid_parentheses(s: str) -> bool:
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in s:
if char in mapping: # 닫는 괄호
top = stack.pop() if stack else "#"
if mapping[char] != top:
return False
else: # 여는 괄호
stack.append(char)
return not stack
print(is_valid_parentheses("({[]})")) # True
print(is_valid_parentheses("({[})")) # False
# 스택의 대표 사용 사례 2. 뒤로 가기(브라우저 히스토리)
class BrowserHistory:
def __init__(self):
self.history = []
self.current = -1
def visit(self, url):
# 현재 위치 이후 히스토리 제거
self.history = self.history[:self.current + 1]
self.history.append(url)
self.current += 1
def back(self):
if self.current > 0:
self.current -= 1
return self.history[self.current]
# 스택의 대표 사용 사례 3. DFS(깊이 우선 탐색) 반복 구현
def dfs_iterative(graph, start):
stack = [start]
visited = set()
while stack:
node = stack.pop() # O(1)
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
stack.append(neighbor)
return visited스택을 선택해야 하는 신호:
- 실행 취소(Undo)/재실행(Redo) 기능이 필요하다
- 중첩 구조(괄호, HTML 태그, 함수 호출 스택)를 검사한다
- DFS 탐색을 반복으로 구현한다
- 후위 표기식(Postfix) 계산이 필요하다
큐(Queue) — FIFO의 힘
큐는 가장 먼저 넣은 데이터를 가장 먼저 꺼내는 FIFO(First In, First Out) 구조입니다. 순서가 공정해야 하는 모든 시나리오에서 큐가 등장합니다.
python
from collections import deque
# 큐의 대표 사용 사례 1. BFS(너비 우선 탐색)
def bfs(graph, start):
queue = deque([start]) # deque를 큐로 활용
visited = {start}
result = []
while queue:
node = queue.popleft() # O(1) — list.pop(0)은 O(n)!
result.append(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
# 큐의 대표 사용 사례 2. 작업 처리 시스템
import queue
task_queue = queue.Queue()
# Producer: 작업 추가
task_queue.put({"id": 1, "task": "이메일 발송"})
task_queue.put({"id": 2, "task": "PDF 생성"})
task_queue.put({"id": 3, "task": "데이터 백업"})
# Consumer: 순서대로 처리
while not task_queue.empty():
task = task_queue.get() # FIFO 순서 보장
print(f"처리 중: {task['task']}")
# 큐의 대표 사용 사례 3. 슬라이딩 윈도우
def max_sliding_window(nums, k):
from collections import deque
dq = deque() # 인덱스 저장
result = []
for i, num in enumerate(nums):
# 윈도우 밖 인덱스 제거
while dq and dq[0] < i - k + 1:
dq.popleft()
# 현재 값보다 작은 인덱스 제거
while dq and nums[dq[-1]] < num:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result큐를 선택해야 하는 신호:
- BFS 탐색을 구현한다
- 먼저 들어온 순서대로 처리해야 한다(메시지 큐, 인쇄 대기열)
- 레벨 순서 트리 순회(Level-order Traversal)가 필요하다
3. 해시 기반 자료구조 — 해시맵·해시셋의 원리와 선택 기준
해시 기반 자료구조는 평균 O(1) 의 탐색·삽입·삭제를 제공하는 강력한 도구입니다. 해시 함수로 키를 인덱스로 변환하여 데이터를 저장하는 원리로 동작합니다.
해시맵(HashMap / Dictionary) — O(1) 탐색의 비밀
python
# 해시맵의 대표 사용 사례 1. 빈도 카운팅
from collections import Counter, defaultdict
# Counter — 빈도 카운팅에 특화
words = ["apple", "banana", "apple", "cherry", "banana", "apple"]
freq = Counter(words)
print(freq) # Counter({'apple': 3, 'banana': 2, 'cherry': 1})
print(freq.most_common(2)) # [('apple', 3), ('banana', 2)]
# defaultdict — 기본값 자동 생성
graph = defaultdict(list)
graph["A"].append("B") # "A" 키 없어도 자동으로 [] 생성
# 해시맵의 대표 사용 사례 2. Two Sum 문제 — O(n) 해결
def two_sum(nums, target):
seen = {} # {값: 인덱스} 해시맵
for i, num in enumerate(nums):
complement = target - num
if complement in seen: # O(1) 탐색
return [seen[complement], i]
seen[num] = i # O(1) 저장
return []
# O(n²) 브루트포스 대신 O(n) 해시맵으로 해결
# 해시맵의 대표 사용 사례 3. 캐싱(메모이제이션)
from functools import lru_cache
@lru_cache(maxsize=None) # 내부적으로 해시맵 사용
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
# O(2^n) → O(n)으로 극적 개선
# 해시맵의 대표 사용 사례 4. 그룹핑
students = [
{"name": "Alice", "grade": "A"},
{"name": "Bob", "grade": "B"},
{"name": "Charlie", "grade": "A"},
{"name": "Dave", "grade": "B"},
]
grade_groups = defaultdict(list)
for student in students:
grade_groups[student["grade"]].append(student["name"])
print(dict(grade_groups))
# {'A': ['Alice', 'Charlie'], 'B': ['Bob', 'Dave']}해시셋(HashSet) — 중복 제거와 멤버십 검사
python
# 해시셋의 대표 사용 사례 1. 중복 제거
numbers = [1, 2, 3, 2, 1, 4, 3, 5]
unique = list(set(numbers)) # O(n)으로 중복 제거
# 해시셋의 대표 사용 사례 2. 멤버십 검사 — O(1)
blacklist = {"spammer@evil.com", "hacker@bad.com", "bot@spam.com"}
def is_blocked(email):
return email in blacklist # O(1) — 리스트라면 O(n)
# 해시셋의 대표 사용 사례 3. 집합 연산
visited_a = {"서울", "부산", "대구"}
visited_b = {"부산", "광주", "서울"}
both_visited = visited_a & visited_b # 교집합: {'서울', '부산'}
either_visited = visited_a | visited_b # 합집합
only_a = visited_a - visited_b # 차집합: {'대구'}
# 해시셋의 대표 사용 사례 4. 사이클 탐지
def has_cycle_in_sequence(sequence):
seen = set()
for item in sequence:
if item in seen:
return True # 중복 발견 = 사이클
seen.add(item)
return False해시 충돌과 해시맵의 한계
python
# 해시맵이 약한 경우 — 순서 보장 X (Python 3.7+은 삽입 순서 보장)
# 최악의 경우 O(n) — 해시 충돌이 모두 같은 버킷에 몰릴 때
# 정렬된 순회가 필요할 때는 TreeMap(정렬된 딕셔너리) 고려
from sortedcontainers import SortedDict
# 정렬된 키 순서가 필요할 때 — O(log n) 연산
sd = SortedDict()
sd[3] = "C"
sd[1] = "A"
sd[2] = "B"
print(list(sd.keys())) # [1, 2, 3] — 항상 정렬된 순서
# 범위 쿼리가 필요할 때 — 해시맵은 불가능
keys_in_range = list(sd.irange(1, 2)) # [1, 2]해시맵·해시셋을 선택해야 하는 신호:
- 키로 값을 빠르게 조회해야 한다
- 데이터 존재 여부를 O(1)로 확인해야 한다
- 빈도 카운팅, 그룹핑, 캐싱이 필요하다
- 중복을 제거하거나 집합 연산이 필요하다
4. 트리 기반 자료구조 — 이진탐색트리·힙·트라이
트리는 계층적(hierarchical) 관계를 표현하거나, 정렬된 상태를 유지하면서도 효율적인 연산이 필요할 때 등장합니다.
이진탐색트리(BST)와 균형 트리 — 정렬된 탐색의 핵심
이진탐색트리는 왼쪽 자식 < 부모 < 오른쪽 자식 규칙을 유지하는 트리입니다. 균형이 유지되면 탐색·삽입·삭제 모두 O(log n)이지만, 편향되면 O(n)으로 악화됩니다. 실무에서는 자동으로 균형을 유지하는 AVL 트리·레드블랙 트리(TreeMap·TreeSet)를 사용합니다.
python
from sortedcontainers import SortedList, SortedDict
# SortedList — 항상 정렬된 상태 유지 O(log n) 삽입
sl = SortedList([5, 3, 8, 1, 4])
sl.add(6) # O(log n) 삽입, 자동 정렬
sl.remove(3) # O(log n) 삭제
print(sl) # SortedList([1, 4, 5, 6, 8])
# 범위 쿼리 — 해시맵으로 불가능한 연산
idx_left = sl.bisect_left(4)
idx_right = sl.bisect_right(6)
print(sl[idx_left:idx_right]) # [4, 5, 6]
# 실무 예시: 리더보드 — 점수 범위 조회
leaderboard = SortedList(key=lambda x: -x[1]) # 점수 내림차순
leaderboard.add(("Alice", 1500))
leaderboard.add(("Bob", 1200))
leaderboard.add(("Charlie", 1800))
print(leaderboard[0]) # ('Charlie', 1800) — 최고 점수힙(Heap) / 우선순위 큐 — 최솟값·최댓값을 O(1)로
힙은 부모가 항상 자식보다 크거나(최대 힙) 작은(최소 힙) 완전 이진트리입니다. 최솟값 또는 최댓값을 항상 O(1)로 접근하고, 삽입·삭제는 O(log n)입니다.
python
import heapq
# Python heapq는 최소 힙
heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
print(heapq.heappop(heap)) # 1 — 항상 최솟값 O(log n)
print(heap[0]) # 1 — 최솟값 확인 O(1) (삭제 없음)
# 최대 힙 — 음수 부호 트릭
max_heap = []
for num in [3, 1, 4, 1, 5]:
heapq.heappush(max_heap, -num) # 음수로 저장
max_val = -heapq.heappop(max_heap) # 꺼낼 때 음수 복원
# 힙의 대표 사용 사례 1. K번째 큰 수
def find_kth_largest(nums, k):
min_heap = []
for num in nums:
heapq.heappush(min_heap, num)
if len(min_heap) > k:
heapq.heappop(min_heap) # k개만 유지
return min_heap[0] # 최솟값 = k번째 큰 수
# 힙의 대표 사용 사례 2. 작업 스케줄러(우선순위 기반)
import heapq
task_heap = []
heapq.heappush(task_heap, (1, "긴급 배포")) # (우선순위, 작업)
heapq.heappush(task_heap, (3, "문서 업데이트"))
heapq.heappush(task_heap, (2, "버그 수정"))
while task_heap:
priority, task = heapq.heappop(task_heap)
print(f"[우선순위 {priority}] {task} 처리")
# 힙의 대표 사용 사례 3. Dijkstra 최단 경로
def dijkstra(graph, start):
distances = {node: float("inf") for node in graph}
distances[start] = 0
pq = [(0, start)] # (거리, 노드)
while pq:
dist, node = heapq.heappop(pq)
if dist > distances[node]:
continue
for neighbor, weight in graph[node]:
new_dist = dist + weight
if new_dist < distances[neighbor]:
distances[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return distances트라이(Trie) — 문자열 탐색의 최강자
트라이는 문자열을 문자 단위로 트리에 저장하는 자료구조입니다. 길이 m인 문자열의 탐색·삽입이 O(m)으로, 문자열이 많아도 탐색 시간이 늘지 않습니다.
python
class TrieNode:
def __init__(self):
self.children = {}
self.is_end = False
class Trie:
def __init__(self):
self.root = TrieNode()
def insert(self, word): # O(m)
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.is_end = True
def search(self, word): # O(m)
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end
def starts_with(self, prefix): # O(m) — 자동완성 핵심
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
# 자동완성 시스템
trie = Trie()
words = ["apple", "application", "apply", "apt", "banana"]
for word in words:
trie.insert(word)
print(trie.search("apple")) # True
print(trie.starts_with("app")) # True — "app"으로 시작하는 단어 있음
print(trie.starts_with("xyz")) # False트리 기반 자료구조 선택 신호:
- BST/균형트리: 정렬 유지 + 범위 쿼리 + O(log n) 연산
- 힙: 최솟값·최댓값 반복 추출, 우선순위 기반 처리
- 트라이: 문자열 접두사 탐색, 자동완성, 사전 구현
5. 그래프와 고급 자료구조 — 언제 필요하고 어떻게 선택하는가
그래프는 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조로, 관계·경로·네트워크를 표현하는 데 가장 적합합니다.
그래프 표현 방식 — 인접 리스트 vs 인접 행렬
python
# 인접 리스트 — 희소 그래프(간선 적음)에 유리
# 공간복잡도 O(V + E)
from collections import defaultdict
graph_list = defaultdict(list)
edges = [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]
for u, v in edges:
graph_list[u].append(v)
graph_list[v].append(u) # 무방향 그래프
# 인접 행렬 — 밀집 그래프(간선 많음)나 두 정점 연결 여부 O(1) 확인에 유리
# 공간복잡도 O(V²)
V = 5
graph_matrix = [[0] * V for _ in range(V)]
for u, v in edges:
graph_matrix[u][v] = 1
graph_matrix[v][u] = 1
# 두 정점 연결 여부
print(graph_matrix[0][1]) # 1 (연결됨) — O(1)
print(graph_list[0]) # [1, 2] — O(degree)유니온 파인드(Union-Find) — 연결 관계 추적
python
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x): # 경로 압축
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y): # 랭크 기반 합치기
px, py = self.find(x), self.find(y)
if px == py:
return False # 이미 같은 집합 = 사이클
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def connected(self, x, y):
return self.find(x) == self.find(y)
# 사용 예시: 네트워크 연결 여부
uf = UnionFind(6)
uf.union(0, 1)
uf.union(1, 2)
uf.union(3, 4)
print(uf.connected(0, 2)) # True — 같은 컴포넌트
print(uf.connected(0, 3)) # False — 다른 컴포넌트그래프를 선택해야 하는 신호:
- 노드 간 관계·경로·네트워크를 표현한다(소셜 네트워크, 지도)
- 최단 경로(Dijkstra, BFS), 최소 신장 트리(Kruskal, Prim)가 필요하다
- 사이클 탐지, 위상 정렬(의존성 순서)이 필요하다
6. 자료구조 선택 의사결정 트리 — 상황별 최종 정리
지금까지 배운 내용을 실제 문제 상황에 적용하는 의사결정 프레임워크를 정리합니다.
자료구조 선택 플로우차트
[문제 시작]
│
▼
데이터 간 관계가 있는가? (노드-간선 구조)
├── YES → 그래프(Graph)
│ └── 연결 여부만? → 유니온 파인드
│
└── NO
│
▼
계층적 구조인가?
├── YES → 트리(Tree)
│ ├── 문자열 접두사 탐색? → 트라이(Trie)
│ ├── 최솟값/최댓값 반복 추출? → 힙(Heap)
│ └── 정렬+범위 쿼리? → BST/SortedList
│
└── NO (선형 데이터)
│
▼
키-값 매핑 또는 O(1) 탐색 필요?
├── YES → 해시맵(HashMap) / 해시셋(HashSet)
│
└── NO
│
▼
순서(LIFO/FIFO)가 중요한가?
├── LIFO(후입선출) → 스택(Stack)
├── FIFO(선입선출) → 큐(Queue)
│
└── NO (일반 시퀀스)
│
▼
인덱스 접근이 빈번한가?
├── YES → 배열(Array)
└── NO (삽입·삭제 빈번) → 연결리스트상황별 자료구조 선택 빠른 참조표
| 문제 상황 | 최적 자료구조 | 이유 |
|---|---|---|
| 중복 없는 방문 기록 추적 | HashSet | O(1) 멤버십 확인 |
| 빈도 카운팅 | HashMap(Counter) | O(1) 키 접근 |
| 최단 경로 탐색 | 그래프 + Dijkstra(힙) | 가중치 경로 탐색 |
| 자동완성 구현 | 트라이(Trie) | O(m) 접두사 탐색 |
| 작업 우선순위 처리 | 힙(우선순위 큐) | O(1) 최솟값 접근 |
| 실행 취소(Undo) | 스택 | LIFO 순서 보장 |
| 메시지 큐·BFS | 큐(deque) | FIFO 순서 보장 |
| 정렬 유지+범위 쿼리 | SortedList/TreeMap | O(log n) 삽입+범위 |
| 랜덤 인덱스 접근 | 배열 | O(1) 임의 접근 |
| 앞·중간 빈번한 삽입 | 연결리스트 | O(1) 삽입(위치 알 때) |
| 연결 컴포넌트 추적 | 유니온 파인드 | O(α(n)) ≈ O(1) 연산 |
| 캐시 구현(LRU) | HashMap + 연결리스트 | O(1) 접근+삽입 |
LRU 캐시 — 해시맵 + 연결리스트의 교과서적 조합
python
from collections import OrderedDict
class LRUCache:
"""
해시맵: O(1) 키 접근
연결리스트: O(1) 순서 변경 (OrderedDict가 내부적으로 구현)
"""
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key) # 최근 사용으로 갱신 O(1)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # 가장 오래된 항목 제거 O(1)
# 사용 예시
lru = LRUCache(3)
lru.put(1, "A")
lru.put(2, "B")
lru.put(3, "C")
lru.get(1) # 1 최근 사용
lru.put(4, "D") # 용량 초과 → 가장 오래된 2 제거
print(lru.get(2)) # -1 (제거됨)
print(lru.get(1)) # "A" (남아있음)추천 학습 도구와 자료
| 도구·자료 | 활용 목적 |
|---|---|
| VisuAlgo (visualgo.net) | 자료구조 동작 시각화 애니메이션 |
| Big-O Cheat Sheet (bigocheatsheet.com) | 자료구조별 시간·공간복잡도 빠른 참조 |
| LeetCode / 프로그래머스 | 자료구조별 실전 문제 풀이 훈련 |
| 《알고리즘 문제 해결 전략》 | 구종만 저, 국내 최고의 알고리즘 바이블 |
| 《Introduction to Algorithms (CLRS)》 | 자료구조·알고리즘 학술 표준 교재 |
| Python sortedcontainers | BST/TreeMap 기능을 Python에서 활용 |
결론
자료구조 선택 가이드의 핵심은 “가장 자주 수행하는 연산의 시간복잡도를 최소화하는 자료구조를 선택한다”는 단 하나의 원칙입니다. O(1) 탐색이 필요하면 해시맵, 최솟값 반복 추출은 힙, 정렬 유지+범위 쿼리는 균형트리, LIFO는 스택, FIFO는 큐, 관계 표현은 그래프로 시작점을 잡으면 90%의 문제는 해결됩니다. 나머지 10%는 LRU 캐시처럼 두 자료구조를 조합하여 각각의 강점을 결합하는 것입니다. 오늘 바로 LeetCode에서 자료구조별 태그로 문제를 필터링하고, 의사결정 트리를 적용해보는 연습부터 시작해 보세요.
답글 남기기