코딩테스트 준비할 때 필수 개념! <기본 자료구조> 알아보기

이번에 알아볼 주제는 기존 자료구조이다. 기본 자료구조라고 하면 스택, 큐, 힙 등을 말하는데 코딩 테스트에서 출제되는 빈도는 보통 정도이다. 하지만 기본 자료구조는 다른 문제를 풀 때 기초가 되기에 꼭 알아야 한다. 스택이나 큐 같은 경우는 구현이나 DFS/BFS 문제를 해결할 때 자주 사용되고, 또 힙 같은 경우는 스택과 큐에 비해서 조금 생소하지만 모르면 못 푸는 문제들이 있기 때문에 꼭 알아둬야 한다.

 

사실 코딩 테스트에서 출제되는 문제들은 응시자가 기본 자료구조를 알고 있는지 확인하기 위해서 출제되는 것은 아니고, 기본 자료구조를 활용해서 어떤 아이디어로 어떻게 구현할지를 물어보는 문제가 대부분이다.

 

이번 포스팅에서는 기본 자료구조의 개념에 대해서 설명하기보다 파이썬에서 어떻게 기본 자료구조를 구현하고 활용하는지를 중점적으로 설명하겠다.

 

출제된 기본 자료구조 관련 문제

• 삼성 SW 역량 테스트 기출문제 "뱀"
• 2020 카카오 블라인드 채용 1차 "괄호 변환"
• 2019 카카오 블라인드 채용 1차 "무지의 먹방 라이브"
• 2020 카카오 블라인드 채용 1차 "문자열 압축"

 

꼭 알아둬야 할 Python 기본 자료구조 활용법

 

스택(Stack)

스택의 구조

스택은 한쪽 끝에서만 자료의 삽입(Push)과 삭제(Pop)가 일어나는 자료구조로 파이썬에서는 리스트(List)를 활용해 스택을 구현하기 때문에 스택을 위한 모듈이 따로 필요하지 않다.

 

# 스택

# 리스트를 활용해 스택을 생성
stack = []

# 자료의 삽입(Push)
# append() 메서드를 활용
stack.append(4) # [4]
stack.append(1) # [4, 1]
stack.append(3) # [4, 1, 3]

# 자료의 삭제(Pop)
# pop() 메서드를 활용
stack.pop() # 3
stack.pop() # 1
stack.pop() # 4

stack # []

# 스택의 최상단 자료의 확인
# 리스트 인덱싱[-1]을 활용한다.
stack.append(1) # [1]
stack[-1] # 1
stack.append(3) # [1, 3]
stack[-1] # 3

# 스택이 비어있는지 확인
# 조건문을 활용해 스택이 비어있는지 확인 할 수 있다.
if stack:
    # 스택이 비어있지 않은 경우
    pass
else:
    # 스택이 비어있는 경우
    pass
    
# 스택의 크기 확인
# len(stack)으로 확인
stack = [1, 2, 3, 4] # [1, 2, 3, 4]
len(stack) # 4
stack.pop() # 4
len(stack) # 3
    

 

큐(Queue)

큐는 먼저 집어넣은 자료가 먼저 나오는 자료형을 말하며, 일반적으로 우리가 볼 수 있는 표를 사기 위한 줄을 예시로 들 수 있다. 파이썬에는 queue라는 내부 라이브러리도 있지만, queue도 내부적으로는 collections.deque로 queue를 관리하기 때문에 collections.deque를 사용하는 것을 추천한다.

 

Deque는 덱이라고 불리는 자료구조인데 일반 큐와 달리 앞과 뒤 모두에서 데이터의 삽입과 삭제가 일어난다. 스택과 큐의 일반화된 경우라고 볼 수 있는데 연결 리스트로 구현되어있어 삽입과 삭제가 O(1) 안에 끝나 매우 빠르다.

 

# 큐
from collections import deque

# deque 생성
queue = deque()

# append
# 오른쪽에 데이터 추가
queue.append(3) # deque([3])
queue.append(5) # deque([3, 5])
queue.append(7) # deque([3, 5, 7])

# appendleft
# 왼쪽에 데이터 추가
queue.appendleft(2) # deque([2, 3, 5, 7])
queue.appendleft(4) # deque([4, 2, 3, 5, 7])

# pop
# 오른쪽에서 데이터 삭제
queue.pop() # 7
queue.pop() # 5

# popleft
# 왼쪽에서 데이터 삭제
queue.popleft() # 4
queue.popleft() # 2

queue # deque([3)

 

주의할 점이 파이썬 list를 활용해 큐를 만들면서 아래와 같이 insert를 활용해 자료를 추가하는 경우가 있는데, 이 경우 삽입할 때 list 내부에 있는 모든 원소를 한 칸씩 이동시켜야 하기 때문에 O(n)의 시간 복잡도를 가진다. 따라서 경우에 따라서는 시간 초과가 발생할 수 있다.

 

queue = []

queue.insert(0, 1) # [1]
queue.insert(0, 3) # [3, 1]
queue.insert(0, 5) # [5, 3, 1]

 

힙(Heap)

힙은 최댓값과 최솟값을 빠르게 찾아내기 위한 자료구조로써 우선순위 큐를 구현하기 위한 자료형으로 많이 쌓인다. 기본적으로 배열로 힙을 구현할 수 있지만, 한 번 정도만 본인 스스로 구현해보고 그냥 파이썬 heapq 모듈을 사용하는 것을 추천한다. heapq 모듈 사용법은 아래 링크를 참고하면 된다. 

 

heapq 모듈 사용법

 

함께 풀면 좋은 문제들

• 백준 2075번 문제 "N 번째 큰 수"
• 백준 2504번 문제 "괄호의 값"
• 백준 2696번 문제 "중앙값 구하기"
• 프로그래머스 "프린터"
• 프로그래머스 "디스크 컨트롤러"

 

코딩 테스트 준비할 때 필수 개념! 시리즈

• 코딩테스트 준비할 때 필수 개념! <문자열 처리> 알아보기
• 코딩테스트 준비할 때 필수 개념! <완전탐색> 알아보기