늦은 프로그래밍 이야기
그래프, DFS & BFS, Dynamic Programming 본문
그래프
특징
- 연결되어 있는 정점과 정점간의 관계를 표현할 수 있는 자료구조.
- 노드와 노드 사이의 연결관계에 초점.
용어
- 노드(Node) : 연결 관계를 가진 각 데이터. 정점(vertex)
- 간선(Edge) : 노드 간의 관계를 표시한 선.
- 인접 노드(Adjacent Node): 간선으로 직접 연견한 노드(또는 정점)
종류
- 유방향 그래프(Directed Graph) : 방향이 있는 간선. 한 방향으로만 진행 가능.
- 무방향 그래프(Undirected Graph) : 방향이 없는 간선.
표현 방법
- 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현.
- 인접 리스트(Adjacency List) : 링크드 리스트로 그래프의 연결 관계를 표현.
- 시간
1) 인접 행렬 : 즉각적으로 연결되었는지 여부를 알 수 있음.
2) 인접 리스트 : 리스트를 돌아봐야 연결되었는지 여부를 알 수 있으므로 O(간선)만큼의 시간을 사용.
- 공간
1) 인접 행렬 : 모든 조합의 연결 여부를 저장해야 되기 때문에 O(노드^2)만큼의 공간을 사용.
2) 인접 리스트 : 모든 조합의 연결 여부를 저장할 필요가 없으므로 O(노드+간선)만큼의 공간을 사용.
DFS & BFS
DFS
특징
- 자료의 검색, 트리나 그래프를 탐색하는 방법. 한 노드를 시작으로 인접한 다른 노드를 재귀적으로 탐색하고 끝까지 탐색하면 다시 위로 와서 다음을 탐색하여 검색한다.
- 그래프를 끝까지 파고드는 것이라, 그래프의 최대 깊이만큼의 공간을 요구 (공간을 적게씀.)
- 최단 경로 탐색이 쉽지 않다.
구현
1) 재귀함수로 구현
- 시작 노드(루트 노드)인 1부터 탐색
- 현재 방문한 노드를 visited_array에 추가
- 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드에 방문
# 위의 그래프를 예시로 인접 리스트 방식으로 표현
graph = {
1: [2, 5, 9],
2: [1, 3],
3: [2, 4],
4: [3],
5: [1, 6, 8],
6: [5, 7],
7: [6],
8: [5],
9: [1, 10],
10: [9]
}
visited = [] # visited 배열을 생성
def dfs_recursion(adjacent_graph, cur_node, visited_array):
visited_array.append(cur_node) # 시작노드를 방문기록에 추가
for adjacent_node in adjacent_graph[cur_node]: # 그래프 내의 현재노드에 인접한 노드를 반복
if adjacent_node not in visited_array: # 탈출 조건 : 인접한 노드가 방문기록에 없는 경우 재귀로 반복
dfs_recursion(adjacent_graph, adjacent_node, visited_array)
return
dfs_recursion(graph, 1, visited) # 1 이 시작노드
print(visited) # [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]- 재귀함수로 구현하는 방법은 무한정 깊어지는 노드가 있는 경우 에러가 발생할 수 있다.
2) 스택으로 구현
- 시작 노드를 스택에 넣는다.
- 현재 스택의 노드를 빼서 visited 에 추가
- 현재 방문한 노드와 인접한 노드 중에서 방문하지 않은 노드를 스택에 추가
# 위의 그래프를 예시로 인접 리스트 방식으로 표현
graph = {
1: [2, 5, 9],
2: [1, 3],
3: [2, 4],
4: [3],
5: [1, 6, 8],
6: [5, 7],
7: [6],
8: [5],
9: [1, 10],
10: [9]
}
def dfs_stack(adjacent_graph, start_node):
stack = [start_node] # 시작노드를 스택에 넣는다.
visited = [] # 방문기록 배열을 생성
while stack: # 스택이 비어있지 않다면 반복
current_node = stack.pop() # 스택의 마지막에 있는 데이터를 current_node 변수에 담는다.
visited.append(current_node) # 방문기록에 현재 방문한 노드를 담는다.
for adjacent_node in adjacent_graph[current_node]: # 그래프 내의 현재 노드에 인접한 노드를 반복
if adjacent_node not in visited: # 방문기록에 없는 인접한 노드들을 스택에 담는다.
stack.append(adjacent_node)
return visited
print(dfs_stack(graph, 1)) # 1 이 시작노드
# [1, 9, 10, 5, 8, 6, 7, 2, 3, 4] 이 출력BFS
특징
- 한 노드를 시작으로 인접한 모든 정점들을 우선 방문하는 방법.
- 최단 경로를 쉽게 찾을 수 있다.
- 모든 분기되는 수를 다 저장하다 보니 공간을 많이씀.
- 모든 걸 다 보고 오다보니 시간이 더 오래걸릴 수 있음.
구현
1) 큐로 구현
- 시작 노드를 큐에 넣는다.
- 현재 큐의 노드를 빼서 visited 에 추가
- 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가
# 위의 그래프를 예시로 인접 리스트 방식으로 표현
graph = {
1: [2, 3, 4],
2: [1, 5],
3: [1, 6, 7],
4: [1, 8],
5: [2, 9],
6: [3, 10],
7: [3],
8: [4],
9: [5],
10: [6]
}
def bfs_queue(adj_graph, start_node):
queue = [start_node] # 시작 노드를 큐에 넣는다.
visited = [] # 방문기록 배열을 생성
while queue: # 큐가 비어있지 않다면 반복
current_node = queue.pop(0) # 큐의 맨앞 데이터를 뽑아 현재 노드 변수에 넣는다.
visited.append(current_node) # 현재 방문한 노드를 방문기록 배열에 넣는다.
for adjacent_node in adj_graph[current_node]: # 현재 노드에 인접한 노드를 반복
if adjacent_node not in visited: # 인접한 노드가 방문기록에 없다면 큐에 넣는다.
queue.append(adjacent_node)
return visited
print(bfs_queue(graph, 1)) # 1 이 시작노드
# [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 이 출력Dynamic Programming(동적 계획법)
피보나치 수열 (Fibonacci numbers)
특징
- 첫째 및 둘째 항이 1이며, 그 뒤의 모든 항은 바로 앞 두항의 합인 수열. 처음 여섯항은 각각 1, 1, 2, 3, 5, 8이다.
- Fibo(1)은 1, Fibo(2)도 1
- Fibo(3)부터는 이전 값 + 이전 이전 값. Fibo(3) = Fibo(2) + Fibo(1)
- 따라서 Fibo(n) = Fibo(n-1) + Fibo(n-2)로 표현
- 재귀함수로 구현.
구현
input = 20
# Fibo(N) = Fibo(N-1) + Fibo(N-2)
# Fibo(1) = Fibo(2) = 1
def fibo_recursion(n):
if n == 1 or n == 2: # 탈출 조건 : 첫째 항과 둘째 항은 1을 반환
return 1
return fibo_recursion(n - 1) + fibo_recursion(n - 2) # 재귀
print(fibo_recursion(input)) # 6765- input의 값이 커지면 연산이 너무 오래 걸려서 값이 나오지 않는다.
- 위 사진처럼 input이 커질수록 같은 작업을 계속 다시하게 된다.
- 동적 계획법(Dynamic Programming)을 사용하여 이미 했던 일을 기록하고 위의 문제점을 해결할 수 있다.
Dynamic Programming(동적 계획법)
특징
- 복잡한 문제를 간단한 여러개의 문제로 나누어 푸는 방법.
- 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용.
- 겹치는 부분 문제의 결과를 기록하고 이용한다.
용어
- 메모이제이션(memoization) : 결과를 기록하는 것
- 겹치는 부분 문제(Overlapping Subproblem) : 문제를 쪼갤 수 있는 구조
구현
* 재귀함수와 메모이제이션을 사용하여 구현
- 메모용 데이터를 만들고, 처음 값인 Fibo(1)과 Fibo(2)는 각각 1씩 넣어서 저장
- 만약 메모에 있으면 그 값을 바로 반환
- 없으면 아까 수식대로 구한다.
- 그리고 그 값을 다시 메모에 기록
input = 100
# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장
memo = {
1: 1,
2: 1
}
def fibo_dynamic_programming(n, fibo_memo):
if n in fibo_memo: 메모에 저장이 되어 있으면 그 값을 반환
return fibo_memo[n]
nth_fibo = fibo_dynamic_programming(n - 1, fibo_memo) + fibo_dynamic_programming(n - 2, fibo_memo) # 재귀함수
fibo_memo[n] = nth_fibo # n번째 Fibo 값을 메모에 저장
return nth_fibo
print(fibo_dynamic_programming(input, memo)) # 354224848179261915075
'내일배움캠프 > 자료구조 알고리즘' 카테고리의 다른 글
| 자바 알고리즘 (2차원 배열) (0) | 2022.12.06 |
|---|---|
| 알고리즘 타임어택 오답노트 (0) | 2022.11.16 |
| 해쉬 (0) | 2022.11.14 |
| 스택, 큐 (0) | 2022.11.11 |
| 정렬 (0) | 2022.11.10 |
