알고리즘을 공부하는데 집중이 잘 안되서 기록하면서 공부해보자

수학에서 좀 더 구체적으로 그래프 이론에서 그래프란 객체의 일부 쌍들이 연관되어 있는 객체 집합 구조를 말한다.

오일러 경로 aka '한붓 그리기'

모든 간선을 한 번씩 방문하는 유한 그래프

오일러 정의

모든 정점이 짝수 개의 차수를 갖는다면 간선을 한번 씩만 지나서 목표에 도달할 수 있다.

해밀턴 경로

각 정점을 한 번씩 방문하는 무항 또는 유항 그래프 경로

해밀턴 순환

원래의 출발점으로 돌아오는 경로

그래프 순회 aka 그래프 탐색

각 정점을 방문하는 과정이다.

깊이 우선 탐색(Depth First Search)

대부분 DFS를 사용한다고 한다.

DFS는 주로 스택으로 구현하거나 재귀로 구현한다. 백트래킹을 사용하면 뛰어난 효용을 보인다.

너비 우선 탐색(Breadth First Search)

BFS는 주로 큐로 구현한다. 최단 경로를 구하는 문제에 사용된다.

그래프 표현 방법

그래프를 표현하는 방법에는 인접 행렬 , 인접 리스트 두 가지 방법이 있다.

인접 리스트로 표현하기

위의 그래프를 인접 리스트로 표현하면 다음과 같다.

grapth = {
  1: [2,3,4],
  2: [5],
  3: [5],
  4: [],
  5: [6,7],
  6: [],
  7: [3]
}

위의 딕셔너리를 DFS, BFS로 탐색해보자

깊이 우선 탐색(DFS)

1. 막다른 곳까지 도달할 때 까지 왼쪽 노드로 이동한다. 1 -> 2 -> 5 -> 6
2. 막다른 곳 한칸 위에서 오른쪽 노드가 있는지 체크하고 없으면 또 위로 올라간다. 7 -> 3 , 4

재귀로 구현한 DFS

def recursive_dfs(v, discovered=[]):
  discovered.append(v)
  for w in graph[v]:
    if not w in discovered:
      discovered = recursive_dfs(w, discovered)
  return discovered

스택으로 구현한 DFS

def iterative_dfs(start_v):
  discovered = []
  stack = [start_v]
  while stack:
    v = stack.pop()
  
    if v not in discovered:
      discovered.append(v)
      for w in graph[v]:
        stack.append(w)
  return discovered

너비 우선 탐색

1. 인접 노드를 우선으로 탐색한다. 1
2. 더이상 인접 노드가 없으면 왼쪽 자식 노드로 이동하여 인접노드를 탐색한다. 2 -> 3 -> 4
3. 반복한다.

큐로 구현한 BFS

def iterative_vfs(start_v):
  discovered = [start_v]
  queue = [start_v]
  while queue:
    v = queue.pop(0)
    for w in graph[v]:
      if w not in discovered:
        discovered.append(w)
        queue.append(w)
  return discovered

백트래킹

백트래킹은 해결책에 대한 후보를 구축해 나아가다 가능성이 없다고 판단되는 즉시 후보를 포기(백트랙)해 정답을 찾아가는 범용적인 알고리즘으로 제약 충족 문제에 특히 유용하다.

백트래킹은 DFS를 다룰 때 항상 딸려 나오는 단어라고 한다. 백트래킹은 DFS보다 더 넓은 의미를 가진다.

백트래킹의 유래는 탐색을 하다가 더 갈 수 없으면 왔던 길을 되돌아가 다른 길을 찾는다는 데서 유래했다.

백트래킹은 DFS와 같은 방식으로 탐색하는 모든 방법을 뜻하며 DFS는 백트래킹의 골격을 이루는 알고리즘이다.

백트래킹은 주로 재귀로 구현하며 알고리즘마다 DFS 변형이 조금씩 일어나지면 기본적으로 모두 DFS의 범주에 속한다.

직접 경험해보고 포기해야하는 방법이기 때문에 최악의 경우 브루트 포스와 같은 성능을 내기도 한다. 동작방식도 같기도 하다.

브루트 포스로는 위의 트리를 모두 탐색해야한다.

백트래킹을 활용하면 조건이 충족하면 바로 아래의 노드를 잘라낸다. 이것을 가지치기라고 부른다.

제약 충족 문제(Constraint Satisfaction Problems : CSP)

제약 충족 문제란 수 많은 제약 조건을 충족하는 상태를 찾아내는 수학 문제를 일컫는다.

백트래킹은 제약 충족 문제를 풀이하는 데 필수적인 알고리즘이다. 트리 가지치기를 통해 제약 충족 문제를 최적화할 수 있다.

제약 충족 문제는 인공지능이나 경영 과학 분야에서도 심도 있게 연구되고 있으며, 합리적인 시간 내에 문제를 풀기 위해 휴리스틱과 조합 탐색 같은 개념을 함께 결합해 문제를 풀이한다.

제약 충족 문제는 대표적으로 스도쿠처럼 1에서 9까지 숫자를 한 번만 넣는(제약 조건 충족) 정답(상태)을 찾아내는 모든 문제 유형을 말한다.

스도쿠는 백트래킹을 하면서 가지치기를 통해 최적화하는 형태로 풀이한다. 스도쿠 외에도 십자말 풀이, 8퀸 문제, 4색 문제 같은 퍼즐 문제와 배낭 문제, 문자열 파싱, 조합 최적화 문제 등이 모두 제약 충족 문제에 속한다.