[이코테-3] DFS/BFS (1): 스택, 큐, 재귀함수

 

탐색

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

대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있고, 이 둘은 코테에서 매우 자주 등장하는 유형이다.

 

자료구조

우선, DFS와 BFS를 바로 다루기 전에 자료구조부터 짚고 넘어가야 된다. 여기서는 그 중에서 스택과 큐를 다룰 것이다.

스택

스택은, 먼저 들어온게 나중에 나가는 자료구조이다. 흔히, LIFO(Last In First Out)라고 부른다. 스택할 때에는 아래부터, 내릴 때는 위부터 한다. 파이썬의 경우, list의 자료형에서 사용하는데, append()를 통해 추가, pop()을 통해 삭제할 수 있다. 이때, 시간복잡도는 상수이다. 자바스크립트의 경우, 리스트에서 push()와 pop() 메서드를 이용하여 구현한다.

// 자바스크립트 stack
const stack = [];

// Push: 요소 추가
stack.push(1);
stack.push(2);
stack.push(3);

// Pop: 마지막 요소 제거 및 반환
const last = stack.pop(); // 3

console.log(stack); // [1, 2]
console.log(last);  // 3

 

#파이썬 스택
stack = []

# Push: 요소 추가
stack.append(1)
stack.append(2)
stack.append(3)

# Pop: 마지막 요소 제거 및 반환
last = stack.pop()

print(stack)  # [1, 2]
print(last)   # 3

스택 자료구조

큐

큐는 스택과는 반대로, 먼저 들어온 데이터가 먼저 나간다. 따라서 FIFO (First In First Out)라고 부른다. 파이썬에서는 리스트에서 삽입은 동일하게 append()를 사용하지만, 삭제의 경우 가장 먼저 들어간 데이터를 삭제해야되기에 popleft()를 이용한다.

자바스크립트에서는 push()와 shift()를 사용하여 구현한다.

# 파이썬 queue
from collections import deque 

queue = deque()

# Enqueue: 요소 추가
queue.append('A')
queue.append('B')
queue.append('C')

# Dequeue: 첫 요소 제거 및 반환
first = queue.popleft()

print(queue)  # deque(['B', 'C'])
print(first)  # 'A'

// 자바스크립트 queue
const queue = [];

// Enqueue: 요소 추가
queue.push('A');
queue.push('B');
queue.push('C');

// Dequeue: 첫 요소 제거 및 반환
const first = queue.shift(); // 'A'

console.log(queue); // ['B', 'C']
console.log(first); // 'A'

큐 자료구조

 

재귀함수

재귀함수는 자기 자신을 다시 호출하는 함수이다.

모든 재귀함수는 반복문을 이용하여 동일한 기능을 구현할 수 있는데, 이때 반복문과 재귀함수는 상황에 따라 유불리가 다를 수 있다. 

컴퓨터는 함수를 연속적으로 호출할 때 스택 프레임이라는 메모리 구조에 쌓아 올리므로 스택 자료구조와 밀접한 연관이 있다. 실제로 스택을 사용하는 문제 (DFS 등)를 풀 때 스택 라이브러리 대신 재귀 함수를 사용하는 경우가 많다.

다만, 재귀 함수 사용시에 주의해야될 것이 있는데, 반드시 종료 조건을 명시해야 한다. 만약 그렇지 않으면 함수는 무한히 호출되어 스택 오버플로우가 발생한다. 파이썬은 재귀 호출 깊이에 제한이 있다. 

예시 1- 팩토리얼

• n!=1×2×3×...×(n−1)×n
• 수학적으로 0!과 1!의 값은 1

# 방법1. 반복적으로 구현한 n!
def factorial_iteration(n):
	result = 1
    # 1부터 n까지의 수를 차례대로 곱하기
    for i in range(1, n+1):
    	result *= 1
    return result
    
# 방법2. 재귀적으로 구현한 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_iteratvie(5))
print('재귀적으로 구현:', factorial_recursive(5))

 

예시2 - 최대공약수 계산

유클리드 호제법: 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘

• 두 자연수 A,B에 대해 (A>B) A를 B로 나눈 나머지를 R이라고 한다.
• 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같다.
• 예를들어, A = 30, B= 18일 때, 
  
  1. 30 ÷ 18 = 1 나머지 12
  2. 18 ÷ 12 = 1 나머지 6
  3. 12 ÷ 6 = 2 나머지 0
  따라서 최대공약수는 나머지가 0이 되었을 때의 B값인 6이다.

이것도 반복문 혹은 재귀함수로 표현할 수 있다.

# 반복문
def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

        
# 재귀함수

def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)