알고리즘) 탐색 - 스택, 큐, 재귀함수, 팩토리얼

탐색

탐색은 많은 양의 데이터에서 원하는 데이터를 찾는 과정
대표적인 그래프 탐색 알고리즘에는 dfs와 bfs가 있다

• 굉장히 자주 등장하는 유형

스택

• 선입 후출
• 입구와 출구가 동일한 형태

먼저 입력된 자료가 나중에 출력된다

-> 박스를 쌓는다

삽입과 삭제가 주요 작업

파이썬은 리스트에서

append(), pop() 을 이용하여 쉽게 구현 가능

stack[::-1] -> 최상단 원소부터

stack -> 최하단 원소부터

큐

• 대기열
• 선입 선출
• 한 쪽은 입구 한 쪽은 출구인 형태

que는 list로도 기능은 구현가능하지만 비효율적

from collections import deque

queue = deque()

queue.append(원소)
queue.popleft()

queue.reverse() ## 역순으로 

재귀함수

• 함수가 자기 자신을 다시 호출
• 종료 조건이 없으면 최대 깊이 초과 오류 메시지를 출력하게됨

사용자 정의 함수는 stack에 쌓이기 때문에

재귀함수 실행 시 외부 함수가 모두 실행 후

stack의 데이터를 빼내듯 내부 함수가 역순으로 실행된다

팩토리얼

n! = 1 * 2 * 3 * 4 * ... * n
수학적으로 0! 과 1!의 값은 1이다

유클리드 호제법
-> 두 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘
두 자연수 A, B에 대하여 (A > B) A를 B를 나눈 나머지를 R이라고 할 때,
A와 B의 최대 공약수는 B와 R의 최대 공약수와 같다

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

재귀함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성 가능
모든 재귀함수는 반복문으로
모든 반복문은 재귀함수로 가능

경우에 따라 어떤 것이 유리한지 달라질 수 있음
사용자 정의 함수는 스택에 계속 쌓인다
-> 스택 라이브러리 대신에 재귀함수를 이용하는 경우가 많다