꼭 필요한 자료구조 기초

탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

=> 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색하는 문제를 자주 다룸

 

자료구조 : 데이터를 표현, 관리, 처리하기 위한 구조

=> 스택이나 큐는 자료구조의 기초 개념으로 핵심적인 두 함수로 구성됨

삽입(Push) : 데이터를 삽입함

삭제(Pop) : 데이터를 삭제함

 

- 실제로 스택과 큐를 사용할 때에는 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야한다.

오버플로(Overflow) : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생(저장 공간을 벗어나 데이터가 넘처 흐를 떄)

언더플로(Underflow) : 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태이므로 언더플로 발생

 

스택(Stack)

선입후출(First In Last Out) 또는 후입 선출(Last In First Out) 구조로 마지막에 삽입한 내용이 가장 먼저 pop된다

- 파이썬에서 스택을 사용할 경우 별도의 라이브러리를 사용할 필요 없이 기본 리스트에서 append() 와 pop() 메서드를 사용하면 스택 자료구조와 동일하게 작용함.

append() : 리스트의 가장 뒤쪽에 데이터를 삽입

pop() : 리스트의 가장 뒤쪽에서 데이터를 꺼냄

예시

stack = []

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack) # 최하단 원소부터 출력
print(stack[::-1]) # 최상단 원소부터 출력

큐(Queue)

대기 줄이라고 생각하면 쉬움. 나중에 온 사람일수록 나중에 들어가기 때문에 '공정한' 자료구조라고 비유됨. 이런 구조를

선입선출(First In First Out) 구조라고 함

 

- 파이썬에서 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용해볼 것. deque는 스택과 큐의 장점을 모두 채택한 것으로 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며, queue 라이브러리를 사용하는 것 보다 간단.

 

예시

from collection import deque

#큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 다음 출력을 위해 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력

 

 

재귀함수(Recursive Function)

재귀함수 : 자기 자신을 다시 호출하는 함수를 의미함.

 

예제

def recursive_function():
	print('재귀 함수를 호출합니다.')
    recursive_function()

reverse_function()

- 제귀 함수를 사용할 때에는 언제 끝날지 종료 조건을 꼭 명시해야함. 만약 종료 조건을 명시하지 않을 경우 함수가 무한 호출되어 문제가 생길 수 있음

 

대표적인 예로 팩토리얼 문제가 있음