알고리즘 › 알고리즘 간단 복습(Week14_day1)

오늘부터 잠시 내려놓았던 알고리즘을 틈틈히 복습한다.

재귀함수

자기자신을 다시 호출하는 함수로 파이썬에서 최대 깊이가 정해져있다(스택 프레임에 쌓여서 마지막 부터 처리가 되는데, 메모리는 무한하지 않으니까).

재귀함수가 무한하게 하고 싶은게 아니라면 반드시 종료조건을 명시 해햐한다.

def recursive_function(i):
  if i == 100:
    return
  print(i)
  recursive_function(i+1)
  print(i)

recursive_function(1)

마치 스택에 데이터를 넣었다가 꺼내는 것처럼 각 함수에 대한 정보가 스택 프레임에 담겼다가 마지막에 호출한 것부터 종료되면서 첫 번째 호출 함수가 종료된다.

이 같은 특성 때문에 스택을 사용해야 할 때 스택 라이브러리 대신에 재귀 함수를 이용하는 경우가 많다(ex. dfs).

팩토리얼

def factorial_recursive(n):
  if n <= 1:
    return 1
  return n * factorial_recursive(n-1)

최대공약수(Greatest Common Divisor)

유클리드 호제법

두 자연수 A, B(A > B)에 대해 A를 B로 나눈 나머지를 R이라고 하면, A, B의 최대공약수는 B, R의 최대공약수와 같다.

def GCD(A, B):
  if !(A % B):
    return B
  else:
    return GCD(B, A % B)

DFS(Depth-First Search)

이름 그대로 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘이다.

• 탐색 시작 노드를 스택에 삽입하고 방문 처리
• 스택의 최상단 노드에 방문하지 않은 인접 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문처리, 없으면 스택에서 최상단 노드 꺼내기
• 위 과정이 불가능 할 때까지 반복

인접 노드가 복수일 때는 어디부터 갈 지 기준이 있어야 하는데 보통 번호가 낮은 거부터 라는 전제를 자주 쓴다.

그래프

파이썬에서는 주로 그래프를 이차원 배열로 나타내는 경우가 많다.

graph = [
  [],
  [2, 3, 8],
  [1, 7],
  [1, 4, 5],
  [3, 5],
  [3, 4],
  [7],
  [2, 6, 8],
  [1, 7]
]

보통 노드의 번호가 1번부터인 경우가 많으니 0번 인덱스는 비워두고 인접 노드의 리스트를 받는다.

각 노드의 방문 정보는 1차원 리스트를 통해 관리한다.

visited = [False] * 9     //  1 ~ 8 0 번은 뺀 값 => 9

def dfs(graph, v, visited):
  visited[v] = True
  print(v, end=' ')

  for i in graph[v]:
    if not visited[i]:
      dfs(graph, i, visited)

이렇게 현재 방문 하는 노드를 방문 처리를 하고, 현재 노드와 연결 된 인접 노드들 중, 방문하지 않는 노드가 있다면 그 노드에 대해 다시 재귀적으로 방문 처리를 한다.

BFS(Breadth-First Search)

너비 우선 탐색이라고 부르며, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. Queue(큐) 자료구조를 사용하며, 특정 조건(각 간선의 비용이 같은 상황)에서의 최단거리를 찾는데 자주 이용된다.

• 탐색 시작 노드를 큐에 삽입하고 방문처리를 한다.
• 큐에서 노드를 꺼낸 뒤에, 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리한다.
• 위 단계가 불가능할 떄까지 반복한다.

from collections import deque

def bfs(graph, start, visited):
  queue = deque([start])
  visited[start] = True

  while queue:
    v = queue.popleft()
    print(v, end=' ')

    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i] = True