- 이것이 취업을 위한 코딩테스다 with 파이썬(이코테 2021) 유튜브 영상을 보면서 공부한 자료입니다.
- https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC
그래프 탐색 알고리즘 : DFS / BFS
- 탐색이란, 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.
- 대표적인 그래프 탐색 알고리즘으로는, DFS와 BFS가 있다.
- DFS / BFS 는 코딩 테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 한다.
스택 자료구조
- FIFO(First In First Out)
- 먼저 들어온 데이터가 나중에 나가는 형식의, 선입 후출 자료구조이다.
- 입구와 출구가 동일한 형태로 스택을 다음과 같이 시각화 할 수 있다.
- 박스를 스택한다고 생각하자
stack = []
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
stack.append(5)
stack.append(2)
stack.append(3)
stack.append(7)
stack.pop()
stack.append(1)
stack.append(4)
stack.pop()
# 최상단 원소부터 출력
print(stack[::-1])
# 최하단 원소부터 출력
print(stack)
- LIST.append() : 삽입
- LIST.pop() : 최상단 원소를 Return
큐 자료구조
- LIFO(Last In First Out)
- 먼저 들어온 데이터가 먼저 나가는 형식의, 선입선출의 자료구조이다.
- 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 할 수 있다.
- 큐 동작 예시는 다음과 같다.
- 파이썬에서는, 큐를 위해 deque 라이브러리를 사용한다.
from collections import deque
# Queue 구현을 위해 deque 라이브러리 사용
queue = deque()
# append() : 오른쪽에서 삽입된다고 생각
# 삽입(5) - 삽입(2) - 삽입(3) - 삽입(7) - 삭제() - 삽입(1) - 삽입(4) - 삭제()
queue.append(5)
queue.append(2)
queue.append(3)
queue.append(7)
queue.popleft()
queue.append(1)
queue.append(4)
queue.popleft()
# 먼저 들어온 순서대로 출력
print(queue)
# 역순으로 바꾸기
queue.reverse()
# 나중에 들어온 원소부터 출력
print(queue)- DEQUE.append() : 오른쪽으로 삽입
- DEQUE.popleft() : 왼쪽에서 pop
- DEQUE.reverse() : 역순으로 정렬
재귀 함수
- 자기 자신을 다시 호출하는 함수를 말한다
- 단순한 형태의 재귀 함수는 다음과 같다.
def recursive_function():
print('재귀 함수를 호출합니다.')
recursive_function()
recursive_function()- '재귀 함수를 호출합니다.'라는 문자열을 무한히 출력한다.
- 어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력된다.
재귀 함수의 종료 조건
- 재귀 함수를 문제 풀이에서 사용할 때는, 재귀 함수의 종료 조건을 반드시 명시해야 한다.
- 종료 조건을 제대로 명시하지 않으면, 위와 같이 함수가 무한히 호출될 수 있기 때문이다.
- 종료 조건을 포함한 재귀 함수 예제는 다음과 같다.
def recursirve_function(i):
# 100번째 호출을 했을 때, 종료되도록 종료 조건 명시
if i == 100:
return
print(i, '번째 재귀함수에서', i+1, '번째 재귀함수를 호출합니다.')
recursirve_function(i + 1)
print(i, '번째 재귀함수를 종료합니다.')
recursirve_function(1)팩토리얼 구현 예제
- n! = 1 x 2 x 3 x ... x (n-1) x n
- 0!과 1!의 값은 1이다.
# 반복적으로 구현한 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):
# n이 1이하인 경우 1을 반환
if n <= 1:
return 1
# n! = n * (n - 1)!를 그대로 코드로 작성하기
return n * factorial_recursive(n - 1)
# 각각의 방식으로 구현한 n! 출력(n = 5)
print('반복적으로 구현:', factorial_iterative(5))
print('재귀적으로 구현:', factorial_recursive(5))
최대 공약수 계산(유클리드 호제법)
def gcd(a, b):
if a % b == 0:
return b
else:
return gcd(b, a % b)
print(gcd(192, 162))
재귀 함수 사용의 유의 사항
- 모든 재귀 함수는, 반복문을 이용하여 동일한 기능을 하게끔 구현할 수 있다.
- 재귀 함수가 반본문보다 유리한 경우도 있고, 불리한 경우도 있다.
- 컴퓨터가 함수를 연속적으로 호출하면, 함수가 컴퓨터 메모리 내부의 스택 프레임에 쌓이게 된다.
- 그래서 스택을 사용해야 할 때, 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.
안녕하세요.