그래프 알고리즘

• 탐색 : 많은 양의 데이터 중 원하는 데이터를 찾는 과정

스택 자료구조

• LIFO

• 시간복잡도 : O(1)

• list로 -> append(), pop()으로 스택 구현 가능

큐 자료구조

• FIFO
• deque()로 큐 구현 => append(), popleft() 사용 => 가장 왼쪽에 있는 것 꺼내기
• deque를 사용하는 것이 시간복잡도가 더 효율적임!!

---

재귀함수

• 자기 자신을 다시 호출하는 함수
• 종료조건 반드시 명시하기 => if i==100: return

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

• A를 B로 나눈 나머지를 R
  A와 B의 최대공약수는 B와 R의 최대공약수이다

def gcd(a, b):
    if a%b == 0:
        return b
    else:
        return gcd(b, a%b)

def lcm(a, b):
    return (a*b) // gcd(a,b)

print(gcd(192, 162))
print(lcm(192, 162))

• 컴퓨터가 함수 연속적으로 호출 => 컴퓨터 메모리 내부의 스택 프레임에 쌓임 => 스택 라이브러리 대신 재귀함수 사용하는 경우 많음

DFS

• 깊이 우선탐색
• 스택자료구조(재귀함수) 이용

1. 탐색 시작 노드를 스택에 삽입하고 방문처리
2. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 있으면 그 노드를 스택에 넣고 방문 처리. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 2번 수행할 수 없을 때까지 반복

출처

# DFS 메서드
def dfs(graph, v, visited):
#     현재 노드 방문 처리
    visited[v] = True
    print(v, end=' ')

#     현재 노드와 연결된 다른 노드를 재귀적으로 방문
# 2 3 8
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, i, visited)

graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2, 6, 8],
    [1, 7],
]
# 0 1 0 0 0 0 0 0
visited = [False] * 9

dfs(graph, 1, visited)

BFS

• 너비 우선탐색
• 가까운 노드부터 우선적으로 탐색
• 큐 자료구조 이용

1. 탐색 시작 노드를 큐에 삽입하고 방문처리
2. 큐에서 노드를 꺼낸 후 해당 노드의 인접 노드 중에서 방문 하지 않은 노드를 모두 큐에 삽입하고 방문
3. 2 수행못할때까지 반복

출처

from collections import deque

# DFS 메서드
def bfs(graph, start, visited):

    queue = deque([start])

    # 현재 노드 방문처리
    visited[start] = True

#     큐가 빌때까지 반복
    while queue:
#         큐에서 하나의 원소를 뽑아 출력하기
#       1 => 2 3 8
        v = queue.popleft()
        print(v, end=' ')
#         아직 방문하지 않은 인접한 원소들을 큐에 삽입
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True


graph = [
    [],
    [2,3,8],
    [1,7],
    [1,4,5],
    [3,5],
    [3,4],
    [7],
    [2, 6, 8],
    [1, 7],
]
# 0 1 0 0 0 0 0 0
visited = [False] * 9

bfs(graph, 1, visited)