스택

입구와 출구가 같음.
선입후출

큐

왼쪽에서 들어오고 오른쪽으로 나감
선입선출

리스트로 물론 구현할 수 있지만, 리스트 사용 시, 시간 복잡도가 더 높아서 비효율적으로 동작할 수 있으므로
큐를 구현할 땐 꼭 deque 라이브러리를 사용하도록 한다.

하나의 deque 객체를 생성한 뒤에 삽입할땐, append, 삭제할 때는 popleft를 사용한다. 둘 다 시간 복잡도는 상수 시간으로, O(1)이다.

파이썬에서 리스트를 이용해서 특정 인덱스에 존재하는 원소를 꺼내기 위해, 팝 메소드를 호출하게 되면, 원소를 꺼낸 뒤에, 원소의 위치를 조정하는 과정이 필요하기 때문에, 원소를 꺼내는 연산 자체가, O(K)만큼의 시간 복잡도가 요구된다. 그렇기에, 리스틀 이용하지 않고 deque을 이용해서 큐를 구현하자!!

재귀함수

재귀함수란 자기 자신을 다시 호출하는 함수를 말한다.
ex)

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

'재귀 함수를 호출합니다.' 문자열을 무한히 출력하게 되며,
어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력된다.

파이썬에서는 재귀를 호출하는 과정에서 깊이 제한이 있기 때문에, 별다른 설정을 하지 않고 함수를 재귀적으로 호출하게 되면 오류메시지가 나타남.

재귀 함수의 종료 조건

• 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다.
• 종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다.
  • 종료 조건을 포함한 재귀 함수 예제
    def recursive_function(i):
    #100번째 호출을 했을 때 종료되도록 종료 조건 명시
    if i == 100:
    return
    print(i, '번째 재귀 함수에서'. i+1, '번째 재귀함수를 호출합니다.')
    recursive_function(i+1)
    print(i, '번째 재귀함수를 종료합니다.')recursive_function(1)

팩토리얼 구현 예제

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

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

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

최대공약수 계산(유클리드 호제법) 예제

192와 162의 최대공약수가 12와 6의 최대 공약수와 같다는 것을 알 수 있다.
12는 6의 배수이므로, 6을 최대 공약수라고 말할 수 있다.
더 작은 수로 식의 형태를 바꾸는 형태가 반복적이며 동일한 구조를 가지고 있기 때문에 재귀적으로 직관적으로 코드로 옮길 수 있다.

dfs에서는 재귀함수를 이용하기 때문에 재귀함수를 잘 알아두어야 함.