[이.코.테] DFS/BFS 사전 학습 -- 스택, 큐, 재귀 함수

 

DFS/BFS 는 대표적인 탐색 알고리즘이다.

탐색이란, 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다.

그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다루기 때문에

기본 자료구조인 스택과 큐에 대해 제대로 이해하고 있어야 한다.

 

자료구조란, 데이터를 표현하고 관리하고 처리하기 위한 구조이다. 

스택과 큐의 자료구조는 삽입(Push), 삭제(Pop), 오버플로, 언더플로 등을 고려해야 한다.

** 오버플로 - 수용 크기가 가득 찬 상태에서 삽입 연산 수행시 발생

** 언더플로 - 데이터가 전혀 없는 상태에서 삭제 연산 수행시 발생

 

1. 스택 (Stack)

- 선입후출, 후입선출 (ex. 박스 쌓기)

 

stack = []

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

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

 

 

 

2. 큐 (Queue)

- 선입선출 (FIFO) (ex. 대기줄)

- 기존 list 를 활용해서 구현할 수 있지만, 그러면 시간복잡도가 높아서 꼭 deque 라이브러리를 사용해 구현하도록 한다.

 

from collections import deque

queue = deque()

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

print(queue)	# 먼저 들어온 순서대로 출력	# deque([3, 7, 1, 4])
queue.reverse()	# 역순 변경
print(queue)	# 나중에 들어온 원소부터 출력	# deque([4, 1, 7, 3])

 

 

 

3. 재귀함수 (Recursive Function)

- 자기 자신을 다시 호출 (스택 방식)

-- 컴퓨터가 함수를 연속 호출하며 메모리 내부의 스텍 프레임에 쌓인다.

--- 그래서 스택 알고리즘을 구현할 때 재귀함수를 이용하는 경우가 많다!

 

- 재귀 함수의 종료 조건을 반드시 명시해야 한다. (무한호출 -> 오류발생)

 

- 코드가 더 간결하고 반복문 없이 같은 효과를 낼 수 있음.

- 다만, 경우에 따라 재귀함수가 반복문보다 유리하거나 불리할 수 있어서 신중히 사용해야 한다.

 

# 반복문으로 구현한 n!
def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
    	result *= i
    return result

# 재귀적으로 구현한 n!
def factorial_recursive(n):
    if n <= 1 :			# 0! == 1! == 1
    	return 1
    return n * factorial_recursive(n - 1)

# 최대공약수 계산 (유클리드 호제법)
def gcd(a, b)
    if a % b == 0:
    	return b
    else:
    	return gcd(b, a % b)