📍 그래프 탐색 알고리즘 - DFS / BFS
탐색(Search)이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정이다.
대표적인 그래프 탐색 알고리즘으로 DFS, BFS가 있다.
DFS, BFS는 코딩 테스트에서 매우 자주 등장하는 유형이다. (특히 국내 대기업 공채)
이 DFS, BFS를 배우기전에 알고가야할 자료구조를 알아보자.
📍 알고가기 1 - 스택 자료구조
스택은 먼저 들어 온 데이터가 나중에 나가는 형식 (선입후출) 의 자료구조이다.
입구와 출구가 동일한 형태로 스택을 시각화할 수 있다.
append( )와 pop( )의 시간복잡도는 상수시간 O(1)이다.
stack = []
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) # 최하단 원소부터 출력 (선입선출)📍 알고가기 2 - 큐 자료구조
큐는 먼저 들어 온 데이터가 먼저 나가는 형식 (선입선출) 의 자료구조이다.
큐는 입구와 출구가 모두 뚫려 있는 더널과 같은 형태로 시각화 할 수 있다.
큐 구현을 위해서는 deque 라이브러리를 사용해야하므로 from collection import deque 를 한다.
append( )와 popleft( )의 시간복잡도는 상수시간 O(1)이다.
from collection import deque
# 큐(Queue) 구현위해 deque 라이브러리 사용
queue = deque()
queue.append(5) # 5 삽입
queue.append(2) # 2 삽입
queue.append(3) # 3 삽입
queue.append(7) # 7 삽입
queue.popleft() # 삭제
queue.append(1) # 1 삽입
queue.append(4) # 4 삽입
queue.popleft() # 삭제
print(queue) # 먼저 들어온 원소부터 출력 (선입선출)
# 실행 결과 : deque([3, 7, 1, 4])
queue.reverse() # 역순
print(queue) # 나중에 들어온 원소부터 출력 (후입선출)
# 실행 결과 : deque([4, 1, 7, 3])deque 라이브러리는 스택과 큐의 장점을 합친 자료구조다.
📍 알고가기 3 - 재귀 함수
재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수이다.
재귀 함수는 DFS를 구현할 때 자주 사용되는 방법 중 하나이므로 꼭 알고가자.
def recursive_function():
print('재귀 함수를 호출합니다.')
recursive_function()
recursive_function()
• '재귀 함수를 호출합니다.' 라는 문자열을 무한히 출력한다.
• 어느정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력된다.재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수의 종료 조건을 반드시 명시해야 한다.
종료 조건을 제대로 명시하지 않으면 함수가 무한 호출 될 수 있다.
아래는 종료 조건을 포함한 재귀 함수 예제이다.
def recursive_function(i):
if i == 100:
return
print(i, '번째 재귀 함수에서', i+1, '번째 재귀함수를 호출합니다.')
recursive_function(i+1)
print(i, '번째 재귀함수를 종료합니다.')
>
recursive_function(1)그렇다면 재귀 함수를 이용한 예제를 살펴보자.
📌 재귀함수 예제 1) 팩토리얼 구현
반복문으로 표현할 때보다 재귀 함수를 이용했을 때 코드가 간결하고 직관적이다.
# 반복적으로 구현한 n!
def factorial_iterative(n):
result = 1
for i in range(1, n+1): # 1부터 n까지의 수를 차례대로 곱하기
result *= i
return result
# 재귀적으로 구현한 n!
def factorial_recursive(n):
if n <= 1:
return 1
return n * factorial_recursive(n-1) # n! = n * (n-1)
# 각각의 방식으로 구현한 n! 출력
print("반복적으로 구현: ", factorial_iterative(5))
print("재귀적으로 구현: ", factorial_recursive(5))📌 재귀함수 예제 2) 최대공약수 (유클리드 호제법)
두 개의 자연수에 대한 최대공약수(GCD)를 구하는 대표적인 알고리즘으로는 유클리드 호제법이 있다.
유클리드 호제법이란 두 자연수 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)
print(gcd(192, 162)) # 192와 162의 최대공약수: 6⭐️ 재귀 함수 사용의 유의 사항
- 재귀함수를 잘 활용하면 복잡한 알고리즘을 간결하게 작성할 수 있다.
(단, 오히려 다른 사람이 이해하기 어려운 형태의 코드가 될 수도 있으므로 신중하게 사용해야 한다.) - 모든 재귀 함수는 반복문을 이용해 동일한 기능을 구현할 수 있다.
- 재귀 함수가 반복문보다 유리한 경우도 있고 불리한 경우도 있다.
- 컴퓨터가 함수를 연속적으로 호출하면 컴퓨터 메모리 내부의 스택 프레임에 쌓인다.
- 따라서 스택을 사용해야 할 때 구현상 스택 라이브러리 대신 재귀 함수를 이용하는 경우가 많다.
(대표적으로 DFS를 더욱 간결하고 짧은 코드로 작성하기 위해 재귀 함수를 이용해 구현한다.)
🙏 참고
