🙂TIL from lecture

---

탐색(Search)

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

• 대표적인 그래프 탐색 알고리즘 - BFS / DFS

자료구조

• 스택(Stack)

먼저 들어온 데이터가 나중에 나가는 형식 (선입후출, FILO)

⇒ 입구와 출구가 동일한 형태

삽입, 삭제 연산 _ append/pop/list 사용

👏 리스트를 거꾸로 출력하고 싶을 때 사용하는 slicing → a[::-1] / .reverse()

• 큐(Queue)

먼저 들어온 데이터가 먼저 나가는 형식 (선입선출, FIFO)

⇒ 입구와 출구가 뚫려있는 형태 (터널)

큐 연산 _ from collections import deque

→ 리스트 연산에서는 pop 연산 뒤에 원소의 위치를 조정하는 연산이 필요하기 때문: $O(k)$ 요구

• 삽입/삭제 _ append/popleft

• 재귀함수(Recursive function)

자기 자신을 다시 호출하는 함수

👏 RecursionError: maximum recursion depth exceeded while calling a python object

→ 컴퓨터 시스템 상, 스택 프레임 안 재귀함수가 메모리에 계속 쌓이므로 컴퓨터 자체의 메모리가 가득찰 수 있다. 이로 인해 문제가 발생할 수 있으므로 제한을 두는것

$\therefore$ 종료 조건을 반드시 명시해야 한다

• 대표적인 예시 : 최대 공약수계산 유클리드 호제법
  • 두 자연수 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)

• 모든 재귀함수는 반복문을 이용하여 구현이 가능하다 → 반복문보다 유리한 경우도, 불리한 경우도 둘 다 존재한다.
  
• 컴퓨터가 함수를 연속적으로 호출하면, 컴퓨터 메모리 내부의 스택 프레임에 쌓아짐
  • 스택을 사용해야 할 경우, 스택 자료구조 대신 재귀함수 이용