DFS/BFS

쥰쥰·2023년 5월 10일
0

코딩 테스트

목록 보기
4/4
post-thumbnail

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

프로그래밍에서는 그래프, 트리 등의 자료구조 안에서 탐색하는 문제가 많다.
=>여기에는 대표적인 탐색 알고리즘인 DFS/BFS가 많이 쓰인다.

DFS/BFS 를 이해하기 위해서는 기본 자료구조인 스택과 큐에 대한 이해가 필요하다.


자료구조 : 데이터를 표현하고 관리하고 처리하기 위한 구조

스택 : 쌓아 올리는 것, 이는 박스 쌓기로 비유할 수 있다. 먼저 쌓은 것은 가장 나중에 치울 수 있고, 가장 최근에 쌓은 것은 맨 처음으로 치울 수 있다. 이러한 구조를 선입후출 구조(First In Last Out) 또는 후입선출 구조(Last In First Out)라고 한다.

: 줄, 이는 식당에서 줄서는 것에 비유할 수 있다. 먼저 줄을 선 사람은 먼저 식당으로 들어가고, 나중에 줄을 선 사람은 나중에 식당에 들어간다. 이러한 구조를 선입선출 구조(Fisrt In First Out)이라고 한다.

스택과 큐의 공통점

  • 자료구조의 기초 개념으로 두 핵심적인 함수, 삽입(Push)과 삭제(Pop)로 구성된다.
  • 오버플로 - 특정한 자료구조가 수용할 수 있는 데이터의 크기가 이미 가득 찬 상태에서 삽입 연산을 수행할때 발생하는 것으로 특정 범위를 넘어서서 다시 최솟값부터 시작하는 것으로 조심해야한다.
  • 언더플로 - 특정한 자료구조에 데이터가 전혀 들어있지 않은 상태에서 삭제 연산을 수행하면 데이터가 전형 없는 상태로 최댓값부터 다시 시작하는 것으로 조심해야한다.

재귀함수(Recursive Function) : 자기 자신을 다시 호출하는 함수

#재귀 함수 기본 코드

def recursive_function():
	print('재귀 함수를 호출합니다.')
    recursive_function()
    
recursive_function()

위의 코드를 실행하면 문자열이 계속 출력되다가 아래 경고문과 함께 멈춘다.

RecursionError: maximum recursion depth exceeded with pickling an object

재귀 함수에서 호출을 너무 많이 하게 되면 스택 메모리 영역에 너무 많은 공간을 할당하게 되어 스택 오버플로가 발생할 수 있다는 점을 주의해야 한다.

재귀함수의 종료 조건

재귀함수는 함수를 게속 호출했을 때 가장 마지막에 호출한 함수가 먼저 수행을 끝내야 그 앞의함수 호출이 종료된다. 따라서 재귀 함수 내에서 특정 조건일 때 더 이상 재귀적으로 함수를 호출하지 않고 종료하도록 if문을 이용하여 꼭 종료 조건을 구현해야한다.

재귀함수 예제

# 팩토리얼 코드

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

위 코드의 결과는 120으로 동일하다.
하지만 재귀함수를 쓴 코드가 더 간결한 데, 이 이유는 재귀함수가 수학의 점화식(재귀식)을 그대로 소스코드로 옮겼기 때문이다.

  • 수학에서 점화식 : 특정한 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현한 것
  • 팩토리얼의 수학적 점화식 표현
    1) n이 0혹은 1일 때: factorial(n) =1
    2) n이 1보다 클 때: factorial(n) = n * factorial(n-1)

재귀함수를 이용하여 팩토리얼을 구현하기 위해 고려할 것
1) n이 1 이하인 경우 - 재귀함수가 무한히 반복되어 결과가 출력이 안된다.
2) n이 음수인 경우 - 입력 법위 오류로 오류메세지가 떠야한다.
=> 재귀함수 내에서 특정 조건일 때 더 이상 재귀적으로 함수를 호출하지 않고 종료하도록 if문을 이용하여 꼭 종료 조건을 구현해야한다.


깊이 우선 탐색이라고 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘

DFS를 이해하기 위해서는 그래프를 알아야한다.

그래프 : 노드(Node)와 간선(Edge)로 표현하며 이때 노드를 정점(Vertex)라고도 말한다.

그래프 탐색 : 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다. 또한 두 노드가 간선으로 연결되어 있다면 '두 노드는 인접하다' 라고 표현한다.

그래프의 표현 방식

  • 인접 행렬(Adjacency Matrix): 2차원 배열에 각 노드가 연결된 관계를 표현하는 방식
  • 인접 리스트(Adjacency List): 리스트로 그래프의 연결 관계를 표현하는 방식


위의 그림을 예시로 들자.

#인접 행렬 방식 예제

INF = 999999999  # 무한의 비용 선언

#2차원 리스트를 이용해 인접 행렬 표현
graph = [
	[0, 7, 5],
	[7, 0, INF],
	[5, INF, 0]
]
print(graph)

인접 행렬방식은 2차원 배열에 각 노드가 연결된 형태를 기록하는 방식이다.
연결되어 연결되어 있는 노드끼리는 간선을 작성하고, 있지 않은 노드끼리는 무한이라고 한다. 이때 INF는 99999999이라고 초기화해줘야한다.

# 인접 리스트 방식 예제

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

print(graph)

인접 리스트 방식은 '연결 리스트'라는 자료구조를 이용해 구현하는 데, 파이썬의 경우 기본 자료형인 리스트 자료형이 append()와 메소드를 제공해 단순하게 2차원 리스트를 이용하면 된다.

인접 행렬과 인접 리스트의 차이점

  • 속도: 인접 행렬이 빠름 - 인접 리스트의 경우 연결된 데이터를 하나씩 확인해야함.
  • 메모리: 인접 리스트가 유리 - 인접 행렬의 경우 모든 관계를 저장해 노드 개수가 많을수록 메모리가 낭비됨.

DFS가 스택 자료구조를 이용하며 구체적인 동작 과정

1) 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2) 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노들를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3) 2번의 과정을 더이상 수행할 수 없을 때까지 반복한다.
+'방문 처리'는 스택에 한번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것을 의미한다. 방문처리를 함으로써 각 노드를 한번씩만 처리할 수 있다.

DFS 특징

  • 스택 자료구조에 기초하여 구현이 간단하다.
  • 데이터의 개수가 N개인 경우 O(N)의 시간이 소요된다.

너비 우선 탐색으로 가까운 노드부터 탐색하는 알고리즘으로 선입선출 방식인 큐 자료구조를 이용한다. 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어, 가까운 노드부터 탐색을 진햏하게 된다.

BFS의 동작 과정

1) 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2) 큐에서 노드를 껀내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽힙하고 방문처리를 한다.
#) 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

BFS 특징

  • 큐 자료주조에 기초하여 구현이 간단하다.
  • deque 라이브러리를 사용하는 것이 좋으며 탐색을 수행함에 있어 O(N)의 시간이 소요된다.
  • 일반적인 경우 실제 수행 시간은 DFS보다 좋다.
profile
꾸준한 쥰을 위하여!

0개의 댓글