Stack, Queue, Recursive Function

" 그래프를 탐색하기 위한 대표적인 두 가지 알고리즘 "

탐색(Search)이란???

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

- 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다.

- DFS / BFS를 제대로 이해하려면 기본 자료구조인 stack과 queue에 대한 이해가 전제되어야함

 

자료구조(Data Structure)란???

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

- Stack과 Queue는 자료구조의 기초 개념으로 다음의 두 핵심적인 함수로 구성됨

## Python에서 스택을 이용할 때에는 별도의 라이브러리 사용할 필요가 없다.
why??
append(), pop() 메서드를 이용하면 스택 자료구조와 동일하게 동작한다.

* 삽입(Push) : 데이터 삽입 = append(), 리스트의 가장 뒤쪽에 데이터를 삽입
* 삭제(Pop) : 데이터 삭제 = pop(), 리스트의 가장 뒤쪽에서 데이터를 꺼냄

- Stack과 Queue를 사용할 때 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야한다

오버플로(Overflow) 
- 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생
즉, 저장 공간을 벗어나 데이터가 넘쳐흐를 때 발생

언더플로(Underflow)
- 특정한 자료구조에 데이터가 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전혀 없는 상태이기 때문에 발생

스택 Stack - First In Last Out or Last In First Out(선입후출 or 후입선출)

- 박스는 아래에서부터 위로 차곡차곡 쌓는다(append).

- 아래에 있는 박스를 치우기 위해서는 위에 있는 박스를 먼저 내림(pop)

-  함수의 호출이 완료되면 소멸

 

큐 Queue - First In First Out(선입선출)

- 줄을 설 때, 머넞 온 사람이 먼저 들어간다(물론 새치기는 없다고 가정)

- 나중에 온 사람일수록 나중에 들어가기 때문에 흔히 '공정한' 자료구조라고 비유된다.

참조(deque, 덱)

https://cord-ai.tistory.com/142

Python 내장함수 및 라이브러리

deque.popleft() 가 list.pop(0) 빠른 이유 = 확인하기

list에서 pop을 활용하면 성능면에서 떨어지는 단점 why???

재귀 함수 Recursive Function

- 자기 자신을 호출하는 함수

def recursive_func():
    print("재귀 함수 호출")

    # 함수 재 호출
    recursive_func()

recursive_func()

RecursionError: maximum recursion depth exceeded while calling a Python object

= Stack Overflow 

- 재귀 함수 호출 문자열을 무한히 호출하게 됨

- 정의한 함수가 자기 자신을 계속해서 추가로 불러오기 때문

- 어느 정도 출력하다가 해당 에러가 발생함

=> 재귀(recursion)의 최대 깊이를 초과했다는 내용

보통 파이썬 인터프리터는 호출 횟수 제한이 있는데 이 한계를 벗어났기 때문
따라서, 무한대로 재귀 호출을 진행할 수는 없다 = 종료 조건을 명시해야함
* 프로그래밍 대횡서는 재귀 함수를 스택을 이용한 함수처럼 동작하도록 자동으로 변경해주는 라이브러리를 사용하기도 한다. = 내부적(=컴퓨터 내부)으로 스택 자료구조와 동일

So, 스택 자료구조를 활용해야하는 상당 수 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있다 DFS

* Factorial이 대표적인 예제 *

 

* 스택Stack 이란???
- 함수가 호출될 때마다 사용되는 임시 저장 메모리 FILO, LIFO

 

프랙털Fractal 구조

- 시에르핀스키의 삼각형(= 프랙털 구조의 대표적인 이미지)

- 이러한 프랙털 이미지를 출력하는 프로그램을 작성할 때 재귀 함수를 이용한다.

* 재귀함수 종료 조건

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

 

반복문 대신 재귀 함수를 사용했을 때 이점

# 1. 반복적으로 구현한 방식
def factorial_normal(n):
    num = 1
    for i in range(1, n+1):
        num *= i
    return num


# 2 . 재귀적으로 구현한 방식(= 수학의 점화식)
def factorial_recur(n):
    # 종료 조건
    # 수학적으로 0!, 1!의 값은 1로 같다는 성질을 이용
    # n이 1 이하가 되었을 때 
    if n <= 1: 
        return 1

    # n! = n * (n-1)!을 그대로 코드로 작성
    return n * factorial_recur(n-1)
    
'''
n이 1 이하가 되었을 때 or n이 음수일 때
재귀 함수에서 특정 조건일 때 더 이상 재귀적으로 함수를 호출하지 않고 종료하도록 if 문을
이용하여 꼭 종료 조건을 구현해주어야 한다.
'''

- 코드 간결해짐 Why???

- 재귀 함수가 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 때문

* 팩토리얼 점화식 *

1. n이 0 혹은 1일 때 : Factorial(n) = 1     # 점화식의 종료 조건

2. n이 1보다 클 때 : Factorial(n) = n X Factorial(n-1)

 

점화식이란???

- 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미.. 뭔말???

==> "다이나믹 프로그래밍"