[알고리즘] BFS, DFS, 이진 탐색

권나연·2025년 1월 6일

알고리즘

알고리즘_개념

목록 보기

1/9

선행 되어야 할 공부 : Stack, Queue, 인접 리스트

DFS : Stack

DFS 핵심 이론

특징

재귀 함수로 구현
Stack 자료구조 이용
시간 복잡도는 O(#node + #edge)
한 번 방문한 노드를 다시 방문하면 안 되므로 노드 방문 여부를 체크할 매열이 필요하고, 그래프는 인접 리스트로 표현한다.

DFS는 스택보다는 스택 성질을 갖는 재귀 함수로 많이 구현한다.

DFS를 시작할 노드를 정한 후 사용할 자료구조 초기화하기
스택에서 노드 꺼낸 후 꺼낸 노드의 인법 노드 다시 스택에 삽입
자료구조에 값이 없을 때까지 반복.

DFS 과정

Stack을 하나 만들고, 처음에는 Stack 안에 노드가 없으니까 시작할 노드를 선택한다.
child node를 stack에 넣을 때는 한번 담은 노드는 다시 넣지 않는다.

0번 노드를 꺼내 출력하고, 0번의 child node인 1번 노드를 Stack에 담기

1번 노드를 꺼내고, 1번의 child node 들 (2, 3번 노드)를 Stack에 담고, 1번 노드를 출력한다.

Stack에서 맨 위에 있는 3번 노드 꺼내고, child node들 (2, 4, 5번인데 2번은 이미 있으니까 4, 5번만 담음)을 Stack에 담고, 3번 노드 출력.

5번 꺼내고, 6, 7번 노드 담고, 출력하기

7번 꺼내고, child node없으므로 더 안 담고, 출력하기.

6번 꺼내고, child node 8번 노드 담고, 출력하기

8번 꺼내고, 4번 꺼내고, 2번 꺼내기

순회 종료.

DFS 예제

https://www.acmicpc.net/problem/11724
https://www.acmicpc.net/problem/2023
https://www.acmicpc.net/problem/13023

BFS : Queue

BFS 핵심 이론

특징

선입 선출 방식, Queue 자료구조 이용.
탐색 노드와 가까운 노드를 우선 탐색하므로 목표 노드에 도착하는 경로가 여러 개일 때 최단 경로를 보장한다.
DFS와 마찬가지로 방문한 노드를 체크하기 위한 배열, 그래프는 인접 리스트로 표현
시간 복잡도는 O(V + E)

BFS를 시작할 노드를 정한 후 사용할 자료구조 초기화
큐에서 노드를 꺼낸 후 꺼낸 노드의 인접 노드를 다시 큐에 삽입
큐 자료구조에 값이 없을 때까지 반복하기.

BFS 과정

Queue를 하나 만들고, 처음에는 노드가 없으니까 시작할 노드를 선택한다. DFS와 마찬가지로 Queue에 들어간 노드는 더 담지 않고, 위에서 아래 순서로 노드들을 꺼내고 출력한다.

0번 노드 담기

0번 꺼내고, child node 1번 노드 담고, 출력하기

1번 꺼내고, child node 들 (2, 3번 노드)을 담고, 1번 출력하기

2번 꺼내고, child node 4번 담고, 2번 출력하기

3번 꺼내고, child node 5번 담고, 3번 출력하기

4번 꺼내고, 없으니까 담지 않고 4번 출력하기

5번 꺼내고, child node 6, 7번 담고, 5번 출력하기

6번 꺼내고, child node 8번 담고, 6번 출력하기

7번 꺼내고 출력, 8번 꺼내고 출력

종료

BFS 예제

https://www.acmicpc.net/problem/2178
https://www.acmicpc.net/problem/1167

DFS 경로 : 0 > 1 > 3 > 5 > 7 > 6 > 8 > 4 > 2
BFS 경로 : 0 > 1 > 2 > 3 > 4 > 5 > 6 > 7 > 8

이진 탐색 : Binary Search

이진 탐색 핵심이론

이진 탐색이란 데이터가 정렬된 상태에서 원하는 값을 찾아내는 알고리즘이다.

대상 데이터의 중앙값, 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 줄이면서 대상을 찾는다. 주로 배열의 인덱스를 기준으로 배열 내의 값을 탐색하는데 사용되지만, 리스트, 트리 등에서도 사용할 수 있다.
하지만 모든 리스트, 트리에서 사용할 수 있는 것이 아니라 반드시 원소들이 일정한 순서(예를 들면 오름차순)로 정렬된 구조에서만 사용할 수 있다.
시간 복잡도는 O(logN)이다.
구현 및 원리가 비교적 간단하므로 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘이다.
"정렬된 자료", "최소를 구하시오 or 최대를 구하시오"

이진 탐색 과정

배열에서의 동작 방식

일정한 순서로 정렬된 데이터에서 다음 4가지 과정을 반복한다.

다음은 오름차순을 기준으로 하는 과정이며, 내림차순은 조건을 반대로 하여 과정을 반복하면 된다.

현재 데이터셋의 중앙값을 찾고, 타겟 데이터와의 값 비교
중앙값 > 타겟 데이터일 때, 중앙값 기준으로 왼쪽 데이터셋을 선택
중앙값 < 타겟 데이터 일때, 중앙값 기준으로 오른쪽 배열을 탐색
1~3을 반복하다가, 중앙값 == 타겟 데이터일 때 탐색을 종료.

트리에서의 동작 방식

트리에서 중간 노드를 찾는다.
찾으려는 값과 중간 노드와의 값을 비교
찾으려는 값이 중간 노드의 값보다 작으면, 왼쪽 하위 트리에서 탐색을 계속한다.
찾으려는 값이 중간 노드의 값보다 크면, 오른쪽 하위 트리에서 탐색을 계속한다.
탐색 범위가 없을때까지 위 과정 반복.

이진 트리 탐색 방식

이진 탐색 예제

1) 반복문 사용

# 반복문 방식
def binary_search_iterative(target, data_list):
    left = 0
    right = len(data_list) - 1

    while left <= right:
        mid = (left + right) // 2

        if data_list[mid] == target:  # 중간 값이 검색 값과 같은 경우
            return mid
        elif data_list[mid] < target:  # 중간 값이 검색 값보다 작을 경우
            left = mid + 1
        else:  # 중간 값이 검색 값보다 클 경우
            right = mid - 1

    return -1  # 찾는 값 없음

elif data_list[mid] < target : target이 오른쪽에 있다는 의미이므로, 탐색 범위를 오른쪽으로 좁히기 위해 left값 변경
else :target이 왼쪽에 있다는 의미이므로, 탐색 범위를 왼쪽으로 좁히기 위해 left값 변경
left가 right보다 크면, 탐색 범위가 없다는 의미이므로, -1 return

2) 재귀 사용

def binary_search_recursive(target, data_list, left, right):
    if left > right:  # 찾는 값 없음
        return -1

    mid = (left + right) // 2

    if data_list[mid] == target:  # 중간 값이 검색 값과 같은 경우
        return mid
    elif data_list[mid] < target:  # 중간 값이 검색 값보다 작을 경우
        return binary_search_recursive(target, data_list, mid + 1, right)
    else:  # 중간 값이 검색 값보다 클 경우
        return binary_search_recursive(target, data_list, left, mid - 1)

elif data_list[mid] < target : target이 오른쪽에 있다는 의미이므로, 탐색 범위를 오른쪽으로 좁혀서 ,mid + 1부터 right까지 다시 재귀 호출
else :target이 왼쪽에 있다는 의미이므로, 탐색 범위를 왼쪽으로 좁혀서 ,left부터 mid-1까지 다시 재귀 호출
left가 right보다 크면, 탐색 범위가 없다는 의미이므로, -1 return