Post

[알고리즘] DFS & BFS 이해를 위한 사전 지식

Posted
By JIHWAN PARK 11 min read

이것이 취업을 위한 코딩 테스트다. with 파이썬 책을 참고하여 정리한 내용입니다.

탐색(Search)

탐색(Search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다. 프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색을 하는 문제를 자주 다룬다. 대표적인 탐색 알고리즘으로는 DFS & BFS가 있는데, DFS, BFS를 제대로 이해하려면 기본 자료구조인 스택과 큐에 대해 이해해야한다.

자료구조(Data Structure)

자료구조(Data Structure)란 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미한다. 스택과 큐는 자료구조의 기초 개념으로 두 핵심적인 함수로 구성된다.

  • 삽입(Push) : 데이터를 삽입한다.
  • 삭제(Pop) : 데이터를 삭제한다.

실제 사용 시 오버플로(Overflow)와 언더플로(Underflow)를 고민해야한다.

  • 오버플로(Overflow) : 특정한 자료구조가 수용할 수 있는 데이터의 크기를 이미 가득 찬 상태에서 삽입 연산을 수행할 때 발생
  • 언더플로(Underflow) : 특정한 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 수행할 때 발생

스택(Stack)

스택(Stack)은 아래서부터 위로 차곡차곡 쌓는 형태로 박스 쌓기에 비유할 수 있다. 아래의 박스를 치우기 위해선 위의 박스를 먼저 내려야 한다. 이러한 구조를 선입후출(First in Last Out) 구조 또는 후입선출(Last In First Out) 구조라고 한다. 파이썬에서는 스택을 이용할 때 별도의 라이브러리 사용할 필요 없이 기본 리스트에서 append()와 pop()을 사용하면 스택 구조와 동일하다.

큐(Queue)

큐(Queue)는 대기 줄에 비유할 수 있다. 먼저 온 사람이 먼저 들어가고, 나중에 온 사람일수록 나중에 들어가기 때문에 흔히 ‘공정한’ 자료구조라고 비유된다. 이러한 구조를 선입선출(First in First Out) 구조라고 한다.

파이썬으로 큐를 구현할 때는 collections 모듈에서 제공하는 deque 자료구조를 활용한다. deque는 스택과 큐의 장점을 모두 채택한 것이며, 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue 라이브러리를 이용하는 것 보다 더 간단하다. 코딩테스트에서는 collections 모듈과 같은 기본 라이브러리 사용을 허용하므로 안심하고 사용해도 된다. list로 변환할 때는 list(queue)로 변환하면 된다.

1
2
3
4
5
6
7
8
9

from collections import deque
queue = deque()
queue.append(5)
queue.append(2)
queue.popleft()
queue.append(1)
print(queue)    # 먼저 들어온 순서대로 출력
queue.reverse() # 역순으로 바꾸기
print(queue)    # 나중에 들어온 원소부터 출력

재귀 함수(Recursive Function)

재귀 함수(Recursive Function)란 자기 자신을 다시 호출하는 함수를 의미한다. 프랙털(Fractal) 구조와 흡사하다. 재귀 함수를 문제 풀이에서 사용할 때는 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야 한다(잘못하면 무한 호출 됨). 컴퓨터 내부에서 재귀 함수의 수행은 스택 자료구조를 이용한다. 따라서, 스택 자료구조를 활용해야하는 상당수 알고리즘은 재귀 함수를 이용해서 간편하게 구현될 수 있다. DFS가 대표적인 예이다.

재귀 함수의 대표적인 예제로 팩토리얼(Factorial) 문제가 있다. n! = 1 x 2 x ··· x (n-1) x n, 0!과 1!은 1로 같다는 성질을 이용하여 n이 1이하가 되었을 때 종료하는 재귀함수 형태로 구현 가능하다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 반복적으로 구현한 n!
def factorial_iterative(n):
  result = 1
  # 1부터 n까지의 수를 차례대로 곱하기
  for i in range(1, 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)

수학의 점화식을 그대로 소스코드로 옮겼기 때문에 재귀 함수의 코드가 더 간결하다. 점화식은 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것을 의미하는데, 8장의 ‘다이나믹 프로그래밍’으로 이어지는 개념으로 중요하다. 팩토리얼을 수학적 점화식으로 표현하면 다음과 같다.

1
2

1) n이 0 혹은 1일 때 : factorial(n) = 1
2) n이 1 보다 클 때 : factorial(n) = n x factorial(n-1)

그래프(Graph)의 기본 구조

노드(Node)와 간선(Edge)으로 표현되며, 이때 노드를 정점(Vertex) 이라고도 말한다. image

두 노드가 간선으로 연결되어 있다면 ‘두 노드는 인접하다(Adjacent)`라고 표현한다.

그래프의 표현 방식으로는 두가지가 있다.

인접 행렬(Adjacency Matrix)

image

2차원 배열로 그래프의 연결 관계를 표현하는 방식이다. 파이썬에서는 2차원 리스트로 구현 가능하다. 연결이 되어 있지 않은 노드끼리는 무한(Infinity)의 비용이라고 작성한다.

1
2
3
4
5
6
7

INF = 999999999

graph = [
  [0, 7, 5],
  [7, 0, INF],
  [5, INF, 0]
]

인접 리스트(Adjacency List)

image

모든 노드에 연결된 노드에 대한 정보를 차례대로 연결하여 저장한다. 인접 리스트는 ‘연결 리스트’라는 자료구조를 이용해 구현하는데, 파이썬에서는 리스트 자료형이 append()와 메소드를 제공하므로, 단순히 2차원 리스트를 이용하면 된다는 점을 기억하면 된다.

1
2
3
4
5
6
7
8
9
10
11
12

# 행(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))

이 두 방식의 차이

메모리 측면

  • 인접 행렬 방식은 모든 관계를 저장하므로 노드 개수가 많을 수록 메모리가 불필요하게 낭비.
  • 반면, 인접 리스트방식은 연결된 정보만을 저장하기 때문에 메모리를 효율적으로 사용.

하지만 이러한 속성 때문에 인접 리스트 방식은 인접 행렬 방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다. 인접 리스트 방식에서는 연결된 데이터를 하나씩 확인해야 하기 때문.

다른 예시로, 한 그래프에서 노드 1과 노드 7이 연결되어 있는 상황에서 인접 행렬 방식에서는 graph[1][7]만 확인하면 된다. 하지만, 인접 리스트 방식에서는 노드 1에 대한 인접 리스트를 앞에서 부터 차례대로 확인해야 한다.

그러므로, 특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우 인접 리스트 방식이 인접 행렬 방식에 비해 메모리의 공간의 낭비가 적다.

Coding Test, Algorithm
Coding Test Algorithm DFS BFS 탐색 자료구조 스택 큐 재귀 함수
This post is licensed under CC BY 4.0 by the author.

[알고리즘] 구현(Implementation)

[알고리즘] DFS & BFS