이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저) 의 책과 강의를 보고 정리한 글입니다.
강의 출처 : https://www.youtube.com/channel/UChflhu32f5EUHlY7_SetNWw
그래프 탐색 알고리즘: DFS/BFS
탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말한다.
스택 자료구조
먼저 들어 온 데이터가 나중에 나가는 형식(선입후출)의 자료구조. 입구와 출구가 동일한 형태로 스택을 시각화할 수 있다. ex) 박스 쌓기
파이썬에서는 리스트가 스택 자료구조를 만족하는 append와 pop을 지원하기 때문에 리스트를 스택과 같이 사용할 수 있다. 또한 append와 pop은 시간 복잡도가 상수시간(O(1))이기 때문에 스택 자료구조로 활용하기 적합하다.
stack = []
stack.append(5)
stack.append(2)
stack.pop()
stack.append(3)
print(stack[::-1]) # 최상단 원소부터 출력 [3, 5]
print(stack) # 최하단 원소부터 출력 [5, 3]큐 자료구조
먼저 들어 온 데이터가 먼저 나가는 형식(선입선출)의 자료구조이다. 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화할 수 있다.
from collections import deque
# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()
queue.append(5)
queue.append(2)
queue.popleft()
queue.append(1)
print(queue) # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue) # 나중에 들어온 원소부터 출력
재귀함수
재귀함수(Recursive Function)란 자기 자신을 다시 호출하는 함수이다.
- 예제
'재귀 함수를 호출합니다'라는 문자열 무한 출력
어느 정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력된다.
def recursive_function():
print('재귀 함수를 호출합니다.')
recursive_function()
recursice_function()-
재귀함수의 종료 조건
재귀 함수를 문제 풀이에서 사용할 때에는 재귀 함수의 종료 조건을 반드시 명시해야 한다.
종료 조건을 제대로 명시하지 않으면 함수가 무한히 호출될 수 있다. -
종료 조건 예제
def recursive_function(i):
# 100번째 호출을 했을 때 종료되도록 종료 조건 명시
if i == 100:
return
print(i, '번째 재귀 함수에서', i + 1, '번째 재귀 함수를 호출합니다.')
recursive_function(i + 1)
print(i, '번째 재귀함수를 종료합니다.')
recursive_function()각각의 함수에 대한 정보가 마치 스택의 데이터를 넣었다가 꺼내는 것과 비슷하게 나타난다.
팩토리얼 구현 예제
- 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):
if n <= 1: # n이 1 이하인 경우 1을 반환
return 1
# n! = n * (n-1)!를 그대로 코드로 작성하기
return n * factorial_iterative(n-1)
# 각각의 방식으로 구현한 n! 출력(n=5)
print("반복적으로 구현:", factorial_iterative(5))
print("재귀적으로 구현:", factorial_recursive(5))최대공약수 계산 (유클리드 호제법) 예제
두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘
- 두 자연수 A, B에 대하여 (A>B) A를 B로 나눈 나머지를 R이라고 한다.
- A와 B의 최대공약수는 B와 R의 최대공약수와 같다.
재귀함수로 작성
a, b = map(int, input("").split())
def GCD(a, b):
temp = a % b
if temp == 0:
return b
else:
return GCD(b, temp)
gcd = GCD(a, b)
print(type(gcd))
print(f"두 수의 최대공약수 : {gcd}")
print(f"두 수의 최소공배수 : {a * b / gcd}")유의 사항
- 재귀 함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있지만 이해하기 어려운 형태의 코드가 될 수 있으므로 신중하게 사용해야 한다.
- 모든 재귀 함수는 반복문을 이용하여 동일한 기능을 구현할 수 있다.
- 재귀 함수가 반복문보다 불리한 경우도 있다.
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다. 따라서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다.
anaooauc1236@naver.com