[코딩 공부] DFS/BFS (1) - 자료구조 기초 상식

안녕하세요 너무 오랜만에 돌아온 코알라입니다. 사실 그동안 시험 기간이기도 했고 회사 업무가 너무 바빠서 블로그 글 작성에 너무 소홀했던 것이 아닌가 싶습니다. 앞으로 더 열심히 글을 작성해볼까 합니다. 

 

오늘 공부한 부분은 DFS/BFS 인데요 사실 이 부분은 그래프를 탐색하기 위한 대표적인 두가지 알고리즘으로 대학교 수업에서도 가장 앞에 나오는 문제들이라고 볼 수 있습니다. 

 

탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미합니다. 프로그래밍에서는 주로 그래프나 트리 등의 자료 구조 안에서 탐색하는 문제를 주로 다루게 됩니다. 대표적으로는 이 블로그 글의 제목인 DFS/BFS가 있는데 이 두 알고리즘의 경우 가장 기초적인 알고리즘이어서 이 두 알고리즘의 원리를 제대로 이해해야 코딩을 제대로 할 수 있다고 생각됩니다(이 책에서도 제시되어  있구요) 

 

그렇다면 우선, 자료 구조에 대해서 설명드릴텐데, 자료구조란 '데이터를 표현하고 관리하고 처리하기 위한 구조'를 의미합니다. 아마도 컴퓨터공학이나 통계학, 데이터 분석등 아마 코딩을 다루는 많은 분야에서 코딩 수업의 가장 기초적으로 다루는 시간 이나 1,2학년 수업에서 다루고 있을 것 같습니다.

 

이 책에서는 가장 핵심적인 스택과 큐를 다루기 위해서 두 가지 함수 를 제시하고 있습니다.

 

삽입 (push) : 데이터를 삽입한다.

 

삭제(pop) : 데이터를 삭제한다.

 

* 실제 스택이나 큐를 오버플로와 언더플로를 고민해야한다. 오버플로는 특정한 자류구조가 수용할 수 있는 데이터의 크기가 넘어섰을 때 연산을 수행하는 경우 발생하고 언더플로는 오버플로와 반대로 전혀 들어 있지 않은 상태에서 삭제 연산을 수행하는 경우 발생한다. 

 

스택이란 ?

 

박스 쌓기에 비유가 주로 되고 있는데 즉 선입 후출, 후입 선출 구조이다. A -> B -> C -> D 순서로 들어왔다면 D -> C -> B -> A 순서로 나가게된다. 

 

큐란?

 

스택과 반대로 선입 선출의 구조다 A-> B -> C-> D 로 들어가면 A-> B -> C -> D의 순서로 나오게 된다. 

* deque 라이브러리 필요 

from collections import deque

queue = deque()

 

마지막으로 DFS/BFS를 구현하기 위해서는 재귀 함수에 대한 이해가 있어야한다. 

 

재귀함수란?

 

자기 자신을 다시 호출하는 함수를 의미한다. 

 

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

 

예시는 위와 같은데, 이럴 경우 끝나지 않는 문제가 발생한다. 그렇기 때문에 이를 종료시킬 수 있는 조건을 반드시 포함하여야 한다. 

 

아래는 두가지를 모두 응용한 팩토리얼 예제이다.

 

#반복적으로 구현 팩토리얼
def factorial_iterative(n):
	result = 1
    for i in range(1, n+1):
    	result = result * i
    return result
    
#재귀적으로 구현한 팩토리얼
def factorial_recursive(n):
	if n <= 1:
    	return 1
    return n * factorial_recursive(n-1)

 

여기서 볼수 있듯이 잘짜여진 재귀함수는 반복문으로 짜여진 함수보다 훨씬 더 간결하게 작성할 수 있다.