[Algorithm] DFS/BFS(1) - DFS/BFS를 이해하기 위한 자료구조
이 유형은 코딩 테스트에서 거의 필수적으로 출제되는 유형이다. 저번에 코테를 봤을때도 DFS/BFS는 무조건 한 문제씩은 출제 되었으며, 이 문제는 어려운 난이도에 속해 합격 여부를 판가름 하는 중요한 유형이다.
DFS/BFS는 알고리즘을 한번이라도 공부 해 본 사람은 알겠지만 각각 차례로 깊이 우선 탐색 / 너비 우선 탐색 이다. 먼저 곧바로 깊이/너비 우선 탐색을 공부하기 전에, 꼭 필요한 자료구조 기초부터 알아보자.
📚 꼭 필요한 자료구조 기초
- 탐색(Search)이란 많은 양의 데이터 중, 원하는 데이터를 찾는 과정을 말한다. 대표적인 탐색 알고리즘으로 DFS/BFS를 꼽을 수 있는데, 이 알고리즘을 이해하려면 먼저 기본 자료구조인 스택과 큐에 대해 알고 있어야 한다.
우선, 스택과 큐는 다음 두개의 핵심적인 함수들로 동작한다.
- 삽입(Push) : 데이터를 삽입한다.
- 삭제(Pop) : 데이터를 삭제한다. - 📍스택(Stack)
스택은 이름부터 직관적인 자료구조이다. 접시 쌓기를 생각하면 이해하기 더 쉬울 것이다. 넓은 접시를 정리해 찬장에 도로 넣는 상황을 생각 해 보자. 접시를 아래서부터 위로 쌓아야 한다. 그리고 접시를 꺼낼때는 위에 있는 접시부터 차례로 꺼낸다. 여기서 스택 자료구조의 특징인 '선입후출'이 등장한다. 즉, 먼저 스택에 들어간 요소는 가장 나중에 나온다. 라고 이해 할 수 있다. 생각을 해 보자. 맨 아래부터 10개의 접시를 차례대로 쌓았다고 생각해 보자. 이때, 맨 아래에 있는 1번 접시를 빼려면 10번 접시부터 차례로 10번을 빼야 비로소 1번 접시를 뺄 수 있다. 아래는 스택의 연산을 도식화 한 것이다. 초기 단계에서 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()를 수행하는 연산이다.
파이썬은 스택을 이용할 때에는 별도의 라이브러리를 사용할 필요가 없다. 기본 리스트에서 append()와 pop()을 이용하면 스택 자료구조와 동일하게 동작한다.
- 📍큐(Queue)
큐는 은행의 손님 대기열과 같다고 생각하면 편하다. 예를 들어보자. 은행에 도착을 했는데 이미 앞에 5명의 사람들이 대기중이였다. 여기서 내가 대기 번호표를 뽑으면 나는 큐의 6번째 자리에 위치 하고있고, 1번 손님이 불려 나간다면 2번 손님이 1번으로 가고, 3번이 2번... 이렇게 해서 내가 1등이 될 때까지 기다려야 한다. 이는 위에서 언급한 스택과는 반대되는 개념인 '선입선출'이 등장한다. 즉, 큐에서는 먼저 큐에 들어간 사람이 먼저 나오며, 스택과 같이 뒤에서부터 큐가 쌓인다.
다음은 큐의 연산을 도식화 한 것이다. 연산의 순서는 [삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()] 이러하다.
아래는 위의 과정들을 소스코드로 표현한 것이다.
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) # 나중에 들어온 원소부터 출력
파이썬에서 큐를 구현 할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하자. deque는 스택과 큐의 장점을 모두 채택한 것인데, 삽입, 삭제에 탁월하며, queue 라이브러리를 이용하는 것보다 더 간편하다.
- 📍재귀 함수(Recursion)
자료구조, 알고리즘을 공부하다 보면 여러 학생들의 고통을 불러 일으킨다는 재귀 함수이다. 나도 강의에서 처음 재귀를 접했을때 머리가 어지러웠다. 이해도 안 되었고, 재귀문이 깊어지면 깊어 질수록 내 머리를 더 아프게 했다.
거두절미 하고, 재귀 함수란 자기 자신을 여러번 호출하는 함수이다. 가장 간단한 재귀 함수는 다음과 같다.
def recursion():
print("RECURSION")
recursion()
이 함수를 실행하면 끊임없이 "RECURSION"이 출력 될 것이다.
이 재귀 함수에서는 꼭 포함 되어야 할 것이 있다.
종료 조건문(base case)
- 이 종료 조건문은 재귀 함수가 종료되어야 할 조건이며, 이 조건에 부합하면 더이상 재귀 함수를 호출하지 않고 끝내야 한다. 이 종료 조건 문이 필수인 이유는 무한대로 재귀 함수를 호출하지 않기 위해서 이다. 위의 소스코드를 예로 들어보자. 위에서 언급했듯 저 함수를 호출 하면 너무 재귀문의 깊이가 깊어(무한대) 오류가 발생 할 것이다. 이때, 재귀문이 종료 될 조건을 포함 시켜 주어야 한다. 아래 예시를 보자.
def recursion(count=0):
if count >= 10:
return
print("RECURSION")
recursion(count + 1)
recursion()
여기서는 if count >= 10 이 종료 조건이다. 카운트를 하나씩 늘려가며 함수를 호출하지만, 10번의 카운트가 끝나면 더이상 호출되지 않고 return 문을 통해 함수가 끝나야 한다. 컴퓨터 내부에서 재귀함수의 수행은 스택 자료구조를 이용한다. 따라서 스택 자료구조를 활용해야 하는 상당수의 알고리즘은 재귀 함수를 이용해서 간단히 구현 할 수 있다. DFS가 대표적인 예 이다.
아래 코드를 살펴보자. 재귀를 배울때 가장 많이 등장하는 factorial함수를 재귀적, 비재귀적으로 구현한 코드이다.
# 반복적으로 구현한 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:
return 1
return n * factorial_recursive(n - 1)
# 두가지 방식으로 구현한 n! 출력 (n = 5)
print('반복적으로 구한:', factorial_iterative(5))
print('재귀적으로 구한:', factorial_recursive(5))
위 코드의 결과는 똑같이 120이 찍힐 것이다. 그렇다면 반복문 대신 재귀 함수를 사용 했을때의 장점은 무엇일까? 먼저, 코드의 길이가 더 짧다. 간결한 코드는 좋은 코드를 쓰기 위함의 일부이며, 개발자들은 최대한 코드를 간결하고 깨끗하게 유지하는 습관을 길러야 한다. 이렇게 간결해진 이유는 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 때문이다. 수학에서 점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수의 관계로 표현한 것을 의미한다. 이 개념은 추후에 DP와 이어지기 때문에 중요하다.
팩토리얼을 수학적 점화식으로 표현하면 다음과 같다.
- n이 0 혹은 1일 때: factorial(n) = 1
- n이 1보다 클 때: factorial(n) = n * factorial(n-1)
일반적으로 우리는 수학적 점화식에서 재귀 함수의 종료 조건을 쉽게 찾을 수 있다. 여기서는 1번이 종료 조건이다. 여기서 n이 1 이하의 경우를 생각 해내지 못하면 재귀 함수가 무한히 반복 될 것이므로 종료 조건을 파악하는 과정은 중요한 대목이다. 이 점화식과 위의 소스 코드를 비교해 보면, 점화식과 소스 코드는 닮아 있다는 것을 알 수 있다.
이처럼 DFS/BFS를 이해하기 전에 필요한 자료구조, 알고리즘을 알아 보았다. 다음 포스팅에는 실제로 DFS/BFS가 뭔지 자세하게 알아 보도록 하겠다.