[Python] 이코테 2021 DFS/BFS (1)

탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 말합니다.

대표적인 그래프 탐색 알고리즘으로는 DFS와 BFS가 있습니다.

DFS/BFS는 코딩테스트에서 매우 자주 등장하는 유형이므로 반드시 숙지해야 합니다.

스택 자료구조

• 먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조입니다.
• 입구와 출구가 동일한 형태로 스택을 시각화할 수 있습니다.

stack = []

stack.append(5)
stack.append(6)
stack.append(2)
stack.pop()

print(stack)
# [5,6]

 

큐 자료구조

• 먼저 들어온 데이터가 먼저 나가는 형식(선입선출)의 자료구조입니다.
• 큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화할 수 있습니다.

from collections import deque

# 큐(Queue) 구현을 위해 deque 라이브러리 사용
queue = deque()

# 삽입(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([3, 7, 1, 4])
# 실행결과 deque([4, 1, 7, 3])

파이썬에서 라이브러리를 사용하지 않고 list를 이용해서 queue를 구현할 수도 있지만, 시간복잡도가 더 늘어나기 때문에 queue 자료구조를 이용할 때는 반드시 deque를 이용해주자.

 

 

재귀함수

• 재귀 함수란 자기 자신을 다시 호출하는 함수를 의미합니다.
• 단순한 형태의 재귀 함수 예제
•  - 재귀 함수를 호출합니다. 라는 문자열을 무한히 출력합니다.
•  - 어느정도 출력하다가 최대 재귀 깊이 초과 메시지가 출력됩니다.

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

recursive_function()

 

팩토리얼을 재귀함수로 구현

def factorial_iterative(n):
    if n <= 1: #n이 1이하인 경우 1을 반환
        return 1
    # n! = n * (n-1)!를 그대로 코드로 작성하기
    return n*factorial_iterative(n-1)

print(factorial_iterative(5))

 

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

• 두 개의 자연수에 대한 최대공약수를 구하는 대표적인 알고리즘으로는 유클리드 호제법이 있습니다.
• 유클리드 호제법
•  - 두 자연수 A,B 에 대하여 (A> B) A를 B로 나눈 나머지를 R이라고 합시다.
•  - 이때 A와 B의 최대공약수는 B와 R의 최대공약수와 같습니다.
• 유클리드 호제법의 아이디어를 그대로 재귀 함수로 작성할 수 있습니다.
•  - 예시 : GCD(192, 162) (GCD는 최대 공약수를 의미)