[DFS / BFS] 스택자료구조, 큐자료구조, 재귀함수

그래프 탐색 알고리즘에 있어 대표적인 알고리즘 DFS와 BFS를 알아보기 전에 선행되어야 할 개념이 있다.

바로 스택(stack)자료구조와 큐(Queue)자료구조가 그것이다. 

 

Stack 자료구조

마치 책을 쌓아 놓고 위에서부터 꺼내는 방식의 알고리즘이라고 생각하면 쉽다.

FILO 즉, 선입후출의 방식인 것이다. 

예를 들어 삽입을 5 - 2 - 7 - 삭제 - 1 - 4  삭제의 과정이 있다면 

stack을 출력하면, 5 2 1 만 밑에서부터 남게 될 것이다. 

 

이를 파이썬 코드로 표현하자면 append와 pop으로 구현할 수 있다. 

stack = [] 

stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)

stack.pop()

stack.append(1)

stack.pop()

stack.append(4)


print(stack)
>>> [5, 2, 3, 4]

 

큐 자료구조 

큐는 마치 파이프에서 물이 빠지듯이 나가는 구조라고 생각하면 된다. 

선입후출 (FIFO) 방식으로 먼저 들어온 정보가 먼저 빠져나가는 알고리즘이다. 

 

이를 파이썬 코드로 작성하게 된다면, deque라는 내부라이브러리를 사용할 수 있다. 

파이썬 코드로 구현이 가능하지만 deque로 구현하는 것이 더 효율적이라고한다. 

from collections import deque

queue = deque()

queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)

queue.popleft()

queue.append(1)
queue.append(4)

#먼저 들어온 순서부터 
queue.reverse()
print(queue)
>>> deque([4, 1, 7, 3, 2])

#나중에 들어온 순서부터
print(queue)
>>> deque([2, 3, 7, 1, 4])

 

재귀함수

재귀함수란 자기함수를 다시 호출하는 함수로 반복해서 자기를 호출하는 경우 사용한다,

영어로는 Recursive Function이라고 하는데, 반드시 종료조건을 넣어야 멈추게 되는 함수라는 걸 잊지 말아야 한다. 

예를 들어보자.

#재귀함수
def recursive_function(i):
    if i == 10:
        return 
    print(i,'번째', i+1, '번째 호출')
    recursive_function(i+1)
    print(i, '종료')

recursive_function(1)

1 번째 2 번째 호출
2 번째 3 번째 호출
3 번째 4 번째 호출
4 번째 5 번째 호출
5 번째 6 번째 호출
6 번째 7 번째 호출
7 번째 8 번째 호출
8 번째 9 번째 호출
9 번째 10 번째 호출
9 종료
8 종료
7 종료
6 종료
5 종료
4 종료
3 종료
2 종료
1 종료

함수를 호출하는 로직을 살펴보면

- 1번 호출하고 2번째 자기함수를 호출하다가 

- 10번째 호출이 되고나서 차례대로 9번째 호출한 것이 종료되고, 8번째 호출한 것이 종료되고

- 마지막으로 1번째가 종료되는 것을 알 수 있다. 

 

마치 스택에서 데이터를 꺼내는 것과 같이 작동하는 것을 알 수 있다. 

이를 토대로 팩토리얼과 최대공약수를 구현할 수 있다! 

팩토리얼 구현

이를 토대로 팩토리얼을 구현하자면

n! = 1 * 2 * 3 * (n-1) * n 

0 ! = 1 ! = 1 이라는 사실은 알아두고 구현하자. 

# 팩토리얼 구현예제
def factorial_recursive(n):
    if n <= 1:
        return 1
    return n * factorial_recursive(n-1)

이를 반복문으로도 구현할 수 있지만, 재귀함수를 통해서 구현할 수 있으며, 시간복잡도 또한 반복문보다 낮은 평가를 받을 수 있어 효율적이다. 

최대공약수 구현 (유클리드 호제법)

두개의 자연수에 대한 최대공약수를 찾으려면 두가지 전제조건을 만족시켜야한다.

 

-  두 자연수 A, B (A>B)에 대해서 A를 B로 나눈 나머지가 R

-  이때, A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다 

 

예를 들어 GCD(192,162)를 구한다고 해보자.

여기서 GCD는 최대공약수를 뜻한다. 

A	B
192	162
162	30	-> R
30	12	-> R
12	6	-> R

정리하면, 192와 162 최대공약수와 12와 6의 최대공약수가 같다는 것이므로 

6 이 최대 공약수인 것이다. 

# 재귀함수 
def gcd(a,b):
    # a와 b가 나눴을 때 0이란 말은 a가 b의 배수라는 뜻이다. 전제조건이 (a>b)이기 때문에! 
    if a % b == 0:
        return b
    else:
        # b와 a를 b로 나눈 나머지 R의 최대공약수
        return gcd(b, a % b)

gcd(192, 162)

>>> 6

 

참고문헌

이것이 취업을 위한 코딩테스트다 동영상을 공부하고 TIL입니다