[알고리즘 공부] DFS/BFS

탐색 알고리즘 DFS/BFS

 

오늘은 지난 구현에 이어서 <이코테>의 내용을 바탕으로 DFS/BFS에 대해 알아보도록 하겠습니다. 우선 두 알고리즘은 그래프 또는 트리를 탐색하기 위한 기본적인 알고리즘으로서 이 둘을 알기 이전에 스택과 큐 그리고 재귀 함수를 알아야합니다. 일단 이번에는 DFS 그리고 BFS에 대해 간단히 알고 스택과 큐 그리고 재귀함수에 대한 코드를 살펴보도록 하겠습니다. 

 

 

DFS (Depth-First Search, 깊이 우선 탐색)

• 그래프의 깊은 부분을 우선적으로 탐색하는 알고리즘.
• 스택(또는 재귀 함수)을 사용하여 구현할 수 있다.
• 모든 가능한 경로를 탐색하고 싶을 때 유용하며 미로 탐색, 백트래킹 문제 등에 적합

 

BFS (Breadth-First Search, 너비 우선 탐색)

• 그래프의 가까운 노드를 우선적으로 탐색하는 알고리즘.
• 큐를 사용하여 구현할 수 있다.
• 최단 경로를 찾거나, 노드 간의 최소 거리를 구할 때 유용하며 레벨 별로 탐색을 진행하므로 계측적인 구조를 가진 문제에 적합

---

꼭 필요한 자료 구조 기초

 

 나동빈님의 <이코테> 저서에 따르면 일단 위에서 언급한 DFS/BFS를 하기 이전에 자료구조 기초를 먼저 설명하시는 데, 일단은 그것을 바탕으로 정리를 먼저 하도록 하겠습니다. 해당 파트 첫 장에는 탐색(Search)과 자료 구조(Data Structure)가 나오는 데 이 부분을 살펴보겠습니다. 

 

탐색(Search)

 먼저, 탐색이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미합니다. 프로그래밍에서는 그래프, 트리 등의 자료 구저안에서 탐색 문제를 다루는 데, 여기서 쓰이는 대표적인 탐색 알고리즘으로 DFS와 BFS를 꼽을 수 있습니다. 이 알고리즘들을 이해해야 코딩 테스트의 탐색 유형을 풀 수 있습니다. 하지만 이해를 하기 이전에 기본 자료 구조인 스택과 큐에 대한 이해가 전제되어야 합니다.

 

자료구조(Data Structure)

 자료 구조란, 데이터를 표현하고 관리하고 처리하기 위한 구조를 의미하며, 대표적으로 스택과 큐는 자료구조의 기초 개념으로 데이터를 삽입(PUSH)하고 삭제(Pop)하는 함수로 구성되어 있습니다. 하지만 실제로 스택과 큐를 사용할 때에는 삽입과 삭제 외에도 오버플로와 언더플로를 고민해야합니다. 

 

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

---

스택, 큐, 재귀 함수

 

 이번에는 프로그래밍에서 자주 사용되는 구조 및 개념으로서 스택, 큐 그리고 재귀함수에 대해서 알아보도록 하겠습니다. 정리를 하자면 스택과 큐는 자료를 저장하고 접근하는 방식에 차이가 있으며, 재귀 함수는 문제를 해결하는 데 있어 자기 참조적인 방식을 제공한다는 것입니다. 이들 각각은 특정 유형의 문제를 해결하는 데 매우 유용하게 사용됩니다. 그럼 각 구조 및 개념 그리고 코드를 통해서 확인해보도록 하겠습니다. 

 

스택 (STACK)
 스택은 박스 쌓기에 비유할 수 있으며, 흔히 박스는 아래에서부터 위로 차곡차곡 쌓는 방식을 사용합니다. 아래에 있는 박스를 치우기 위해서는 위에 있는 박스를 먼저 내려야하며 이러한 구조를 선입후출(First In Last Out) 또는 후입 선출(Last In First Out) 구조라고 합니다. 

 

# 스택 초기화
stack = []

# push 함수: 스택에 요소 추가
def push(element):
    stack.append(element)

# pop 함수: 스택의 최상단 요소 제거 및 반환
def pop():
    if not is_empty():
        return stack.pop()
    else:
        return "스택이 비어있습니다."

# peek 함수: 스택의 최상단 요소 반환
def peek():
    if not is_empty():
        return stack[-1]
    else:
        return "스택이 비어있습니다."

# is_empty 함수: 스택이 비어있는지 확인
def is_empty():
    return len(stack) == 0

# 스택 사용 예제
push(1)     # 스택에 1 추가
push(2)     # 스택에 2 추가
push(3)     # 스택에 3 추가
print(stack)  # 스택 출력: [1, 2, 3]
print(pop())  # 3 출력 및 스택에서 제거
print(peek())  # 2 출력 (스택 최상단 조회)
print(stack)  # 최종 스택 상태 출력: [1, 2]

 

 

---

 

큐(Queue)
 큐는 대기 줄에 비유할 수 있습니다. 놀이공원에 입장하기 위해 줄을 설 때, 먼저 온 사람이 먼저 들어가게 됩니다. 당연히 나중에 온 사람은 나중에 들어가기 때문에 이를 '공정한' 자료 구조라고 비유합니다. 이러한 구조를 선입선출(First In First Out) 구조라고 합니다.

 

# 큐 초기화
queue = []

# enqueue 함수: 큐의 끝에 요소 추가
def enqueue(element):
    queue.append(element)

# dequeue 함수: 큐의 앞에서 요소 제거 및 반환
def dequeue():
    if not is_empty():
        return queue.pop(0)
    else:
        return "큐가 비어있습니다."

# peek 함수: 큐의 맨 앞 요소 반환
def peek():
    if not is_empty():
        return queue[0]
    else:
        return "큐가 비어있습니다."

# is_empty 함수: 큐가 비어있는지 확인
def is_empty():
    return len(queue) == 0

# 큐 사용 예제
enqueue(1)   # 큐에 1 추가
enqueue(2)   # 큐에 2 추가
enqueue(3)   # 큐에 3 추가
print(queue)  # 큐 출력: [1, 2, 3]
print(dequeue())  # 1 출력 및 큐에서 제거
print(peek())  # 2 출력 (큐의 맨 앞 요소 조회)
print(queue)  # 최종 큐 상태 출력: [2, 3]

 

---

 

재귀 함수(Recursive Function)
 DFS와 BFS를 구현하려면 재귀 함수를 이해하고 있어야합니다. 재귀 함수란 자기 자신을 다시 호출하는 함수를 의미합니다. 재귀 함수는 종료 조건을 주지 않으면 무한하게 동작하기 때문에 재귀 함수가 언제 끝날지, 종료 조건을 꼭 명시해야합니다. 가장 간단한 예로 팩토리얼 함수를 재귀적으로 구현하는 방법이 있습니다. 팩토리얼 함수는 주어진 숫자 n에 대하여 n!을 계산하는 함수로, n! = n x (n-1) x (n-2) x ... x 1과 같이 정의됩니다. 특히 0! = 1입니다.

 

def factorial(n):
    # 기저 조건: n이 0이면 1을 반환
    if n == 0:
        return 1
    # n이 0보다 크면 n * (n-1)!을 반환
    else:
        return n * factorial(n - 1)

# 예제 사용
print(factorial(5))  # 5! = 5 * 4 * 3 * 2 * 1 = 120 출력

 

 

---

 

마무리 

 이번에는 DFS/BFS를 들어가기에 앞서 기본 자료 구조인 스택, 큐 그리고 재귀함수에 대해서 알아보았습니다. 솔직히 CS 전공이 아닌지라... 이런 부분을 굳이 해야하나? 하는 생각이 들지만... 기초부터 탄탄한 스터디를 위해서 마음을 바로 잡고 공부했던 것 같습니다. 하나씩 쌓여가는 알고리즘 공부를 하면서 전공의 근간(?)이 흔들리고 있는 경험을 하고 있지만 코딩 TEST가 어느 정도 잡히면 이제는 네트워크 부문도 조금씩 기초부터 탄탄하게 올라가려고 합니다. 어떤 과정이 있을지 모르는 상황이지만 계속해서 하다보면 좋은 결과가 있을 거라고 믿습니다. 그럼 이번 글은 여기서 마무리하도록 하겠습니다~!

 

 

 

참 고

2023.12.08 - [IT/관련 정보] - [코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬

[코딩 테스트] 이것이 취업을 위한 코딩테스트다 with 파이썬