DFS/BFS에 대해 - 스택, 큐, 재귀함수란 ?

DFS, BFS는 알고리즘 문제의 핵심으로, 탐색 문제를 풀기 위해 필수적이다.

이에 대해 알아보기 전에, 우선 필요한 기본 지식을 정리해보자

 

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

대표적인 탐색 알고리즘 = DFS, BFS

 

DFS와 BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대한 이해가 전제되어야 한다.

 

자료구조 (Data Structure)

• 데이터를 표현하고 관리하고 처리하기 위한 구조
• 훨씬 다양한 종류가 있지만, 우선 이번에는 큐와 스택에 대해 정리해보자
• 스택과 큐는 삽입(Push), 삭제(Pop)이라는 핵심적인 함수로 구성되고, 오버플로와 언더플로를 주의해야 함
  • 오버플로 (Overflow) : 수용할 수 있는 데이터의 크기가 이미 가득 찬 상태에서 Push를 수행할 때 발생
  • 언더플로 (Underflow) : 데이터가 전혀 들어 있지 않은 상태에서 Pop을 수행할 때 발생

스택 (Stack)

• FILO (First In Last Out) : 선입후출 구조 / LIFO (Last In First Out) : 후입선출 구조
• 마지막에 들어간 것이 먼저 나오는 구조
• 뒤에서부터 Pop 하는 구조
• Python의 기본 배열이 스택구조이다.
•  
  • Push -> list.append()
  • Pop -> list.pop()

arr = []

arr.append(1) 	# Push
arr.pop()	# Pop

큐 (Queue)

• FIFO (First In First Out) : 선입선출
• 먼저 들어간 것이 먼저 나오는 구조
• 앞에서부터 Pop 하는 구조
• 대기 줄에 비유할 수 있다
• Python에서 구현할 때는 collections 모듈에서 제공하는 deque를 활용한다.
  • deque는 스택과 큐의 장점을 모두 채택한 것
  • 속도가 list에 비해 효율적이며, queue 라이브러리를 이용하는 것보다 더 간단함
  • collections와 같은 기본 라이브러리는 코딩테스트에서도 허용한다

from collections import deque

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

queue.append(1) # Push
queue.popleft() # Pop

 

재귀함수 (Recursive Function)

• 자기자신을 다시 호출하는 함수
• DFS와 BFS를 구현하려면 재귀함수도 이해해야 한다

def recursive_function():
	print('Hello World')
    recursive_function()

recursive_function()

 

• 재귀함수의 종료 조건 
  • 재귀함수는 종료 조건을 반드시 명시해야 한다
  • 종료 조건이 없다면, 함수가 무한 호출될 수 있다

# 재귀함수의 종료 예제
def recursive_function_end(i):
	# 100번째 출력했을 때 종료되도록
    if i== 100:
    	return
    recursive_function_end(i+1) # i씩 증가하도록
    
recursive_function_end()

 

재귀 함수는 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료된다.

컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조와 유사하다. 

➡️ 따라서, 스택 자료구조를 활용해야 하는 알고리즘의 경우 재귀 함수를 이용해서 간편하게 구현될 수 있다.

➡️ (Ex. DFS)

 

팩토리얼 예제를 통해 재귀함수에 대해 자세히 알아보자

# 2가지 방식으로 구현한 팩토리얼 예제
def factorial_iterative(n):
	result = 1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n+1):
    	result *= i
    return result
    

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

# 동일한 결과가 나온다

 

재귀함수를 사용했을 때 얻는 장점은?

• 코드가 더 간결하다 ⬅️ 점화식을 그대로 옮겼기 때문에