DFS/BFS - 꼭 필요한 자료구조 기초

1. DFS/BFS: 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘

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

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

 

스택과 큐는 삽입(Push)과 삭제(Pop) 함수로 구성

 

오버플로: 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생

언더플로: 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행할 때 발생

스택

선입후출(First In Last Out) 구조 or 후입선출(Last In First Out)

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]) # 최상단 원소부터 출력

[5, 2, 3, 1] [1, 3, 2, 5]

 

큐

대기줄에 비유할 수 있다. 먼저 온 사람이 먼저 들어감. '공정한' 자료구조 선입선출(First In First Out)

from collections 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) # 나중에 들어온 원소부터 출력

deque([3, 7, 1, 4]) deque([4, 1, 7, 3])

 

collections 모듈에서 제공하는 deque 구조

deque는 스택과 큐의 장점을 모두 채택한 것. 

데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적

 

deque 객체를 리스트 자료형으로 변경할 때 -> list() 메서드 이용 ex) list(queue)

 

재귀 함수

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

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

recursive_function()

RecursionError: maximum recursion depth exceeded

재귀 함수의 최대 깊이를 초과했다는 내용.

무한대로 재귀 호출을 진행할 수는 없다.

 

재귀 함수의 종료 조건

무조건 종료 조건을 명시해야 한다.

def recursive_function(i):
  # 100번째 출력했을 때 종료되도록 종료 조건 명시
  if i == 100:
    return
  print(i, '번째 재귀 함수에서', i + 1, '번째 재귀 함수를 호출합니다.')
  recursive_function(i+1)
  print(i, '번째 재귀 함수를 종료합니다.')

recursive_function(1)

재귀 함수는 내부적으로 스택 자료구조와 동일 -> DFS는 재귀 함수를 이용해서 구현 가능

 

재귀 함수를 이용하는 대표적인 예제 - 팩토리얼 문제

# 반복적으로 구현한 n!
def factorial_iteratve(n):
  result = 1
  # 1부터 n까지의 수를 차례대로 곱하기
  for i in range(1, n+1):
    result *= i
  return result

# 재귀적으로 구현한 n!
def factorial_recursive(n):
  if n <= 1: # n이 1 이하인 경우 1을 반환
    return 1 
  # n! = n(n-1)!를 그대로 코드로 작성하기
  return n * factorial_recursive(n-1)

# 각각의 방식으로 구현한 n! 출력(n = 5)
print('반복적으로 구현:', factorial_iteratve(5))
print('재귀적으로 구현:', factorial_recursive(5))

반복적으로 구현: 120 재귀적으로 구현: 120

재귀 함수의 코드가 더 간결 -> 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 때문 : 다이나믹 프로그래밍의 중요한 개념

---

[출처] 나동빈, 『 이것이 취업을 위한 코딩 테스트다 with 파이썬 』, 한빛미디어(2020), p.124-133.