탐색

• 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
• 대표적인 그래프 탐색 알고리즘 : DFS, BFS

스택

• 먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)
• 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다
  ex. 박스

큐

• 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)
• 입구와 출구가 모두 뚫려 있는 터널과 같은 형태

from collections import deque

queue = deque()

queue.append()
queue.popleft()
queue.reverse() //역순으로 출력하기

• 리스트를 이용하면 popleft 를 할 때마다 순서를 전체적으로 조정해야 하니까 O(n)

재귀함수

• 자기 자신을 다시 호출하는 함수
• 단순한 형태의 재귀 함수 예제
• 종료조건을 반드시 명시해야 무한히 호출되지 않고 언젠가 멈출 수 있다
• 복잡 -> 간결 (but 이해하기 어려울 수 있다)
• 반복문을 이용하여 동일한 기능을 구현할 수 있다
• ㅔ재귀함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다
• 연속적으로 호출

def recursive_function(i):
	if i == 100:
    	return
	print(i, '호출')
    recursive_function(i+1)

recursive_function()

파이썬은 최대 호출 깊이가 정해져있어서 maximum recurstion depth exceeded 에러 메시지가 뜬다\
재귀함수는 스택과 같은 형태
그러므로 재귀함수를 사용할 때는 스택과 함께 사용하는 것이 좋음
while, for문 없이 반복을 할 수 있음

재귀함수 예시 : 팩토리얼

n! = 1 X 2 X 3 X ... X (n-1) X n

1. 반복적으로 구현한 n!

def factorial_iterative(n):
	result = 1
    for i in range(1, n+1):
    	result =*= i
    return result

2. 재귀적으로 구현한 n!

def factorial_iterative(n):
	if n <= 1:
    	return 1
    return n * factorial_recursive(n-1)

재귀함수 예시 : 최대공약수 계산 (유클리드 호제법)

• 두 개의 자연수에 대한 최대공약수를 구한다
• 유클리드 호제법
  - 두 자연수 A, B에 대하여 A를 B로 나눈 나머지를 R (A>B)
  • A와 B의 최대공약수 : B와 R의 최대공약수와 같다
    

dfs
깊이 우선 탐색
그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
스택 자료구조 혹은 재귀함수를 이용
1. 탐색 시작 노드를 스택에 삽입하고 방문 처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리합니다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냅니다
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복한다