5-1. 꼭 필요한 자료구조 기초

탐색이란?

많은 데이터 중에서 원하는 데이터를 찾는 과정

대표적인 그래프 탐색 알고리즘으로 DFS, BFS가 있는데 코딩테스트에서 자주 등장하는 유형

 

자료구조

스택 자료구조 ( = 선입후출)

stack = []

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()

print(stack) # 5 2 3 1

 

 큐 자료구조 ( = 선입선출)

from collections import deque

queue = deque() # 리스트말고 덱 라이브러리 생성하기 위해

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()

print(queue) # 3 7 1 4 (왼쪽에서 오른쪽으로 추가되므로 오른쪽 부터 읽은 것임)
queue.reverse() # 역순 바꾸기
print(queue) # 4 1 7 3

 

재귀 함수

자기 자신을 호출하는 함수

무한히 출력함 -> 문제풀이에서 사용할 때는 종료 조건을 반드시 명시하기

파이썬에서는 초과 메시지가 출력됨 

모든 재귀함수는 반복문을 이용해 동일한 기능을 구현할 수 있음

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