Stack & Queue

그래프를 탐색하기 위한 대표적인 2가지 알고리즘

탐색 Search

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

e.g. DFS, BFS

 

자료구조 Data Structure

- 데이터를 표현하고 관리하고 처리하기 위한 구조

- 스택과 큐는 자료구조의 기초 개념

- push, pop으로 구성됨

* 삽입 Push

삭제 Pop

오버플로우 Overflow

특정 자료구조가 수용할 수 있는 데이터의 크기를 가득 찬 상태에서 삽입 연산 수행 시 발생 (저장 공간 벗어나 데이터가 넘쳐흐를 때)

언더플로우 Underflow

특정 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산 수행 시 발생

 

스택 Stack

박스 쌓기

선입후출 First In Last Out

후입선출 Last In First Out

파이썬에서는 append()와 pop() 메서드를 이용하면 됨

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

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

 

큐 Queue

대기 줄

선입선출 First In First Out

큐를 구현하려면 deque 라이브러리 사용하면 됨

from collections import deque

queue = deque()

queue.append(5)
queue.popleft()

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

# deque 객체를 리스트 자료형으로 바꾸고자 할 때
list(queue)

 

재귀 함수 Recursive Function

자기 자신을 다시 호출하는 함수

def recursive_function():
	print("재귀 함수")
    recursive_function()
    
recursive_function()

종료 조건을 꼭 명시해야 함

재귀함수는 스택 자료구조와 동일함

스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현 가능 e.g. DFS

def factorial(n):
	if n<=1:
    	return 1
    return n*factorial(n-1)