프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색하는 문제가 많다.
=>여기에는 대표적인 탐색 알고리즘인 DFS/BFS가 많이 쓰인다.
DFS/BFS 를 이해하기 위해서는 기본 자료구조인 스택과 큐에 대한 이해가 필요하다.
스택 : 쌓아 올리는 것, 이는 박스 쌓기로 비유할 수 있다. 먼저 쌓은 것은 가장 나중에 치울 수 있고, 가장 최근에 쌓은 것은 맨 처음으로 치울 수 있다. 이러한 구조를 선입후출 구조(First In Last Out) 또는 후입선출 구조(Last In First Out)라고 한다.
큐 : 줄, 이는 식당에서 줄서는 것에 비유할 수 있다. 먼저 줄을 선 사람은 먼저 식당으로 들어가고, 나중에 줄을 선 사람은 나중에 식당에 들어간다. 이러한 구조를 선입선출 구조(Fisrt In First Out)이라고 한다.
#재귀 함수 기본 코드
def recursive_function():
print('재귀 함수를 호출합니다.')
recursive_function()
recursive_function()
위의 코드를 실행하면 문자열이 계속 출력되다가 아래 경고문과 함께 멈춘다.
RecursionError: maximum recursion depth exceeded with pickling an object
재귀 함수에서 호출을 너무 많이 하게 되면 스택 메모리 영역에 너무 많은 공간을 할당하게 되어 스택 오버플로가 발생할 수 있다는 점을 주의해야 한다.
재귀함수는 함수를 게속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의함수 호출이 종료된다. 따라서 재귀 함수 내에서 특정 조건일 때 더 이상 재귀적으로 함수를 호출하지 않고 종료하도록 if문을 이용하여 꼭 종료 조건을 구현해야한다.
# 팩토리얼 코드
# 반복적으로 구현한 n!
def factorial_iterative(n):
result = 1
# 1부터 n까지의 수를 차례대로 곱하기
for i in range(i, n+1):
result *= i
return result
# 재귀적으로 구현한 n!
def factorial_recursive(n):
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))
위 코드의 결과는 120으로 동일하다.
하지만 재귀함수를 쓴 코드가 더 간결한 데, 이 이유는 재귀함수가 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 때문이다.
재귀함수를 이용하여 팩토리얼을 구현하기 위해 고려할 것
1) n이 1 이하인 경우 - 재귀함수가 무한히 반복되어 결과가 출력이 안된다.
2) n이 음수인 경우 - 입력 법위 오류로 오류메세지가 떠야한다.
=> 재귀함수 내에서 특정 조건일 때 더 이상 재귀적으로 함수를 호출하지 않고 종료하도록 if문을 이용하여 꼭 종료 조건을 구현해야한다.
깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
DFS를 이해하기 위해서는 그래프를 알아야한다.
그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다' 라고 표현한다.
위의 그림을 예시로 들자.
#인접 행렬 방식 예제
INF = 999999999 # 무한의 비용 선언
#2차원 리스트를 이용해 인접 행렬 표현
graph = [
[0, 7, 5],
[7, 0, INF],
[5, INF, 0]
]
print(graph)
인접 행렬방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다.
연결되어 연결되어 있는 노드끼리는 간선을 작성하고, 있지 않은 노드끼리는 무한이라고 한다. 이때 INF는 99999999이라고 초기화해줘야한다.
# 인접 리스트 방식 예제
# 행(Row)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]
# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))
# 노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0, 7))
# 노드 2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append((0, 5))
print(graph)
인접 리스트 방식은 '연결 리스트'라는 자료구조를 이용해 구현하는 데, 파이썬의 경우 기본 자료형인 리스트 자료형이 append()와 메소드를 제공해 단순하게 2차원 리스트를 이용하면 된다.
1) 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2) 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노들를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3) 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.
+'방문 처리'는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문처리를 함으로써 각 노드를 한번씩만 처리할 수 있다.
너비 우선 탐색으로 가까운 노드부터 탐색하는 알고리즘으로 선입선출 방식인 큐 자료구조를 이용한다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진햏하게 된다.
1) 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2) 큐에서 노드를 껀내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽힙하고 방문처리를 한다.
#) 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.