[DFS/BFS] 큐 / 스택

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

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

• 삽입(Push) : 데이터를 삽입
• 삭제(Pop) : 데이터를 삭제한다.

---

스택 : 선입후출 (FILO) or 후입선출 구조 (LIFO)

stack = []

# 5 삽입 - 2 삽입 - 3삽입 - 7삽입 - 삭제 - 1 삽입 - 4 삽입 - 삭제
stack.push(5)
stack.push(2)
stack.push(3)
stack.push(7)
stack.pop()
stack.push(1)
stack.push(4)
stack.pop()

print(stack)  # 최하단 원소부터 출력
print(stack[::-1])  # 최상단 원소부터 출력

---

 

큐 : 선입선출 (FIFO)

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

 

• 파이썬으로 큐를 구현할 때는 collectios 모듈의 deque 를 활용
• deque : 스택과 큐의 장점을 모두 채택, 데이터 삽입삭제 속도가 리스트 자료형에 비해 효율적이고 queue 라이브러리보다 간단하다.
• deque 객체를 리스트 자료형으로 변경 : list(deque)

---

재귀함수 (Recursive Function) : 자기 자신을 다시 호출하는 함수

 

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

 

RecursionError : maximum resursion depth exceeded while pickling an object

: 재귀의 최대 깊이를 초과해서 나타나는 오류 => 무한대로 재귀 호출을 진행할 수 없다.

 

재귀함수의 종료 조건

• 종료 조건을 꼭 명시한다.

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

 

 

• 컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 사용한다. => 함수를 계속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의 함수 호출이 종료되기 때문
• DFS가 재귀 함수를 이용해서 간편하게 구현될 수 있는 대표적인 예
• 팩토리얼 : 대표적인 재귀함수 문제

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


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

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

 

 

 

팩토리얼을 수학적 점화식으로 표현하면

1. n이 0 혹은 1일 때 : factorial(n) = 1
2. n이 1보다 클 때 : factorial(n) = n * faxtorial(n-1)