[이것이 취업을 위한 코딩 테스트다 with 파이썬] (한빛미디어, 나동빈) Chapter5(1). DFS/BFS

 포스팅 개요

 '혹시나 책에 있을 모든 실수와 오류는 온전히 제 책임이며, 책에 실린 좋은 아이디어와 표현은 모두 리뷰어님들의 조언 덕분입니다. 정말 고맙습니다.'라는 지은이의 글은 나동빈 저자님의 인품을 느낄 수 있는 한 줄이었습니다.

 

 저도 저런 마인드를 가진 사람이 되겠다고 다짐하며 책과의 여정을 떠나보겠습니다.

 

이것이 취업을 위한 코딩 테스트다

---

 포스팅 본문

  이번 Chapter는 예제가 많기에 DFS/BFS의 개념 부분과 실전 문제 부분을 나눠서 포스팅하겠습니다.

 

  탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정이다. 탐색에서는 DFS와 BFS 알고리즘이 대표적이다.

이 알고리즘의 이해를 위해서는 기본 자료구조인 스택과 큐에 대한 이해가 필요하다. (자료구조란 데이터를 표현하고

관리하고 처리하기 위한 구조를 의미)

 

 그렇기에 이번 포스팅에서는 그 개념부터 익혀보는 시간을 가지겠습니다.

 

 본 코드는 모두 제 Github에 올려두었습니다. (https://github.com/herjh0405/Coding_Test)

---

5-1. 스택 예제

 스택은 선입 후출(First In Last Out) 구조이다. 흔히 박스 쌓기에 비유할 수 있습니다.

stack = []
stack.append(5) # [5]
stack.append(2) # [5, 2]
stack.append(3) # [5, 2, 3]
stack.pop() # [5, 2]
stack.append(1) # [5, 2, 1]
stack.append(4) # [5, 2, 1, 4]
stack.pop() # [5, 2, 1]

print(stack) # [5, 2, 1]
print(stack[::-1]) # [1, 2, 5]
# list[A:B:C] : A부터 B까지 C의 간격으로, None이면 처음부터 할 수 있는 데까지 한 칸씩, C가 음수이면 역순

파이썬에서는 append()와 pop() 메서드가 있기 때문에 별도의 라이브러리를 사용할 필요가 없다. 스택에 대해 가볍게 받아들일 수 있었습니다.

---

5-2. 큐 예제

 큐는 선입 선출(First In First Out) 구조입니다. 흔히 대기 줄에 비유할 수 있습니다. 

from collections import deque

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

queue.append(5) # deque([5])
queue.append(2) # deque([5, 2])
queue.append(3) # deque([5, 2, 3])
queue.popleft() # deque([2, 3])
queue.append(1) # deque([2, 3, 1])
queue.append(4) # deque([2, 3, 1, 4])
queue.popleft() # deque([3, 1, 4])

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

 파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용하자. deque는 스택과 큐의 장점을 모두 채택한 것인데 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것보다 더 간단하다. 스택과 큐에 대해 알아봤으니 재귀 함수에 대해서도 배워보겠습니다.

---

5-3. 재귀 함수 예제

 DFS와 BFS를 구현하려면 재귀 함수도 이해하고 있어야 합니다. 재귀 함수란 자기 자신을 다시 호출하는 함수를 의미합니다.

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

recursive_function()

 위의 코드를 작동시키면 '재귀 함수를 호출합니다.'라는 문장이 무한히 반복되다가, 'RecursionError: maximum recursion depth exceeded while pickling an object' 오류 메시지를 출력하고 멈춥니다. 재귀 함수는 종료 조건을 걸어두지 않으면 무한히 반복되고, 파이썬 인터프리터는 호출 횟수 제한이 있기 때문입니다. 

 위와 같은 현상을 방지하고자 재귀 함수를 사용할 때는 종료 조건을 꼭 명시해주어야 합니다. 다음의 예제를 보겠습니다.

 

---

5-4. 재귀 함수 종료 예제

# 재귀 함수는 종료 조건을 꼭 명시해야 한다. 잘못하면 무한 호출될 수 있기 때문
def recursive_function(i):
    # 100번째 출력했을 때 종료되도록 종료 조건 명시
    if i == 100 :
        return
    print(i, '번째 재귀 함수에서', i+1, '번째 재귀 함수를 호출합니다.')
    recursive_function(i+1)
    print(i, '번째 재귀 함수를 종료합니다.')

recursive_function(1)

 재귀 함수가 반복되어 실행되다가 명시한 종료 조건인 100 번째에서 호출을 멈추는 것을 확인할 수 있었습니다.

컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다. 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야  그 앞의 함수 호출이 종료되기 때문이다. 

 따라서 스택 자료구조를 활용해야 하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있다. DFS가 대표적인 예이다.

---

 5-5. 2가지 방식으로 구현한 팩토리얼 예제

 재귀 함수를 이용하는 대표적 예제로는 팩토리얼 문제가 있습니다. 그 문제를 반복적으로 구현한 방식과 재귀적으로 구현한 방식 두 가지로 비교해보겠습니다.

# 반복적으로 구현한 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 : # n이 1 이하인 경우 1을 반환
        return 1
    # n! = n*(n-1)!인 코드를 그대로 작성
    return n * factorial_recursive(n-1)

print('반복적으로 구현:', factorial_iterative(5)) # 반복적으로 구현: 120
print('재귀적으로 구현:', factorial_recursive(5)) # 재귀적으로 구현: 120

 실행 결과는 동일합니다. 그렇다면 반복문 대신에 재귀 함수를 사용했을 때 얻을 수 있는 장점은 무엇일까요?

재귀 함수의 경우 수학의 점화식을 그대로 소스코드로 옮겼기 때문에 코드가 훨씬 간결해집니다. ( 점화식이란 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것)

 재귀 함수란 늘 신박하지만 이걸 내가 적용할 수 있을까라는 걱정이 들게하는 친구입니다. 

---

 이전 Chapter들에 비해 조금씩 난도가 높아지는 느낌입니다. DFS/BFS는 정말 중요한 Chapter인 만큼 확실히 이해하고 넘어가도록 하겠습니다. 

 

 기본 개념을 숙지했으니 그것을 응용하는 Chapter5(2)에서 뵙겠습니다. :)