코딩 테스트를 위한 '자료 구조'

자료구조는 데이터를 효율적으로 저장하고 관리하는 방식 또는 방법이다. 코딩 테스트에서는 각 자료 구조의 특성을 이해하고, 문제에 맞게 선택하는 것이 중요하다...는 말은 진부하고 안 까먹게 적어라도 둔다.

 

---

1. 리스트 (List)

리스트는 순서가 있는 데이터를 저장하는 자료 구조로, 인덱스를 사용하여 빠르게 데이터에 접근할 수 있다. 파이썬에서 가장 많이 사용되는 자료 구조임.

• 시간 복잡도: 인덱스 접근 O(1), 삽입/삭제 O(n) (중간에 삽입/삭제 시)
• 사용 사례: 순차적인 데이터 저장, 인덱스 기반 접근, 리스트의 끝에 데이터를 추가하거나 제거할 때 유용

# 리스트 생성
arr = [1, 2, 3]

# 리스트에 요소 추가
arr.append(4)  # O(1)

# 인덱스를 통한 요소 접근
print(arr[2])  # 3

# 리스트에서 마지막 요소 제거
arr.pop()  # O(1)

# 리스트에서 중간에 요소 삽입
arr.insert(1, 5)  # O(n)

# 리스트에서 요소 삭제
arr.remove(2)  # O(n)

print(arr)  # [1, 5, 3]

 

2. 딕셔너리 (Dictionary)

딕셔너리는 키-값 쌍으로 데이터를 저장하는 해시 테이블 기반 자료 구조. 주어진 키를 통해 데이터를 빠르게 검색할 수 있어 매우 효율적이다.

• 시간 복잡도: 평균 O(1) (검색, 삽입, 삭제 모두)
• 사용 사례: 키 기반 검색이 필요한 문제, 빈도수 계산, 데이터 그룹화 등

# 딕셔너리 생성
d = {'a': 1, 'b': 2}

# 키를 통해 값에 접근
print(d['a'])  # 1

# 새로운 키-값 쌍 추가
d['c'] = 3

# 키 삭제
del d['b']

print(d)  # {'a': 1, 'c': 3}

# 키가 존재하는지 확인
if 'a' in d:
    print("Key 'a' exists")

 

3. 튜플 (Tuple)

튜플은 불변(immutable) 자료 구조로, 한 번 생성된 후에는 값을 변경할 수 없다. 해시 가능한 특성을 가져 딕셔너리의 키로 사용할 수 있다.

• 시간 복잡도: 인덱스 접근 O(1)
• 사용 사례: 불변 데이터 저장, 해시 테이블의 키로 사용

# 튜플 생성
t = (1, 2, 3)

# 인덱스를 통한 요소 접근
print(t[1])  # 2

# 튜플은 변경 불가
# t[0] = 5  # 오류 발생

 

4. 집합 (Set)

집합은 중복을 허용하지 않으며, 순서가 없는 자료 구조이다. 집합 연산(합집합, 교집합 등)을 사용할 수 있어 편리하다.

• 시간 복잡도: 삽입/삭제/검색 O(1)
• 사용 사례: 중복 제거, 집합 연산, 특정 요소의 존재 여부 확인

# 집합 생성
s = {1, 2, 3}

# 요소 추가
s.add(4)

# 요소 삭제
s.remove(2)

# 중복된 요소는 자동으로 제거됨
s.add(1)

# 집합 내에 특정 요소가 있는지 확인
if 3 in s:
    print("3 is in the set")

print(s)  # {1, 3, 4}

 

5. 스택 (Stack)

스택은 후입선출(LIFO) 방식으로 데이터를 처리하는 자료 구조이다. 가장 마지막에 들어온 데이터를 먼저 처리하는 방식으로, 재귀적 문제 해결이나 DFS에서 사용된다.

• 시간 복잡도: 삽입/삭제 O(1)
• 사용 사례: 괄호 짝 맞추기, 후위 표기식 계산, 깊이 우선 탐색(DFS)

# 스택 구현
stack = []

# 스택에 요소 추가
stack.append(1)  # O(1)
stack.append(2)

# 스택에서 요소 제거
print(stack.pop())  # 2
print(stack.pop())  # 1

 

6. 큐 (Queue)

큐는 선입선출(FIFO) 방식으로 데이터를 처리하는 자료 구조로, 먼저 들어온 데이터를 먼저 처리한다. 주로 BFS나 작업 스케줄링에서 사용된다.

• 시간 복잡도: 삽입/삭제 O(1)
• 사용 사례: 너비 우선 탐색(BFS), 작업 스케줄링, 프로세스 관리

from collections import deque

# 큐 구현
queue = deque()

# 큐에 요소 추가
queue.append(1)  # O(1)
queue.append(2)

# 큐에서 요소 제거
print(queue.popleft())  # 1
print(queue.popleft())  # 2

 

7. 힙 (Heap)

힙은 우선순위 큐를 구현하는 자료 구조이다. 최소 힙(Min Heap) 또는 최대 힙(Max Heap)으로 구현될 수 있는데, 부모 노드가 자식 노드보다 우선순위가 높다.

• 시간 복잡도: 삽입/삭제 O(log n)
• 사용 사례: 우선순위 처리, 다익스트라 알고리즘, 힙 정렬

import heapq

# 최소 힙 구현
heap = []

# 힙에 요소 추가
heapq.heappush(heap, 3)  # O(log n)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)

# 힙에서 가장 작은 값 꺼내기
print(heapq.heappop(heap))  # 1
print(heapq.heappop(heap))  # 2