탐색 (Search)

탐색(Search)은 주어진 데이터 집합에서 특정 값을 찾거나 조건을 만족하는 값을 찾는 과정을 다룬다. 탐색 문제의 유형은 이진 탐색, 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)로 나눌 수 있다.

---

Binary Search

이진 탐색(Binary Search)은 정렬된 배열에서 특정한 값을 찾는 탐색 알고리즘이다. 이 알고리즘은 배열을 반으로 나누어 탐색 범위를 좁혀가는 방식으로 동작한다.

Baekjoon - Binary Search

이진 탐색 알고리즘은 다음과 같이 동작한다:

1. 시작과 끝을 초기화한다. 일반적으로 배열의 처음과 끝 인덱스를 사용한다. 이를 시작(start)와 끝(end)라고 부른다.

2. 시작과 끝을 이용하여 중간 인덱스를 계산한다.
   중간 인덱스(mid) = (start + end) / 2

3. 중간 원소와 찾고자 하는 값을 비교한다.

4. 다음 세 가지 경우로 나뉜다:

   • 중간 원소와 찾고자 하는 값이 일치하면, 탐색이 성공적으로 종료된다. 중간 인덱스(mid)가 찾고자 하는 값의 인덱스이다.
   • 중간 원소가 찾고자 하는 값보다 크다면, 찾고자 하는 값은 중간 원소의 왼쪽 반에 있을 가능성이 있으므로 검색 범위를 왼쪽 반으로 좁힌다. 따라서 검색 범위의 끝(end)를 mid - 1로 업데이트한다.
   • 중간 원소가 찾고자 하는 값보다 작다면, 찾고자 하는 값은 중간 원소의 오른쪽 반에 있을 가능성이 있으므로 검색 범위를 오른쪽 반으로 좁힌다. 따라서 검색 범위의 시작(start)를 mid + 1로 업데이트한다.

5. 시작(start)가 끝(end)보다 작거나 같을 때까지 위의 과정을 반복한다.

6. 시작(start)가 끝(end)보다 크다면, 원하는 원소가 배열에 존재하지 않는 경우이므로 탐색 실패로 처리한다.

bisect library

from bisect import bisect, bisect_left, bisect_right, insort

arr = [1, 3, 3, 3, 5]

index = bisect(arr, 3) # bisect_right와 같음
index = bisect_left(arr, 3) # 리스트에 데이터를 삽입할 가장 왼쪽 인덱스를 찾는 함수
index = bisect_right(arr, 3) # 리스트에 데이터를 삽입할 가장 오른쪽 인덱스를 찾는 함수

insort(arr, 2) # 배열에 값 넣기

bisect implementation

# 리스트에 데이터를 삽입할 가장 왼쪽 인덱스를 찾는 함수
def bisect_left(arr, x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if arr[mid] < x:
            lo = mid + 1
        else:
            hi = mid
    return lo

# 리스트에 데이터를 삽입할 가장 오른쪽 인덱스를 찾는 함수
def bisect_right(arr, x):
    lo, hi = 0, len(arr)
    while lo < hi:
        mid = (lo + hi) // 2
        if x < arr[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

binary search implementation

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1

    while low <= high:
        mid = (low + high) // 2

        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1

    return -1  # 찾는 값이 배열에 없는 경우

---

Breadth-First Search(BFS) & Depth-First Search(DFS)

Breadth-First Search

너비 우선 탐색(Breadth-First Search, BFS)는 그래프나 트리와 같은 자료 구조에서 루트 노드(또는 시작 노드)에서부터 목표 노드까지 가장 가까운 노드부터 탐색하는 알고리즘이다.

Baekjoon - Breadth-first Search

너비 우선 탐색 알고리즘은 다음과 같이 동작한다:

1. 큐(Queue)를 사용: BFS는 큐 자료 구조를 사용하여 정점을 저장하고 탐색한다. 시작 정점을 큐에 넣고 시작한다.

2. 레벨 순서 탐색: BFS는 레벨 순서로 탐색한다. 즉, 시작 정점에서부터 한 레벨씩 아래로 내려가면서 탐색한다. 같은 레벨에 있는 정점들은 거리가 동일하다.

3. 방문 표시: 각 정점을 방문할 때, 그 정점을 방문했음을 표시하여 중복 방문을 방지한다. 이 방문 표시는 정점을 큐에 넣을 때 이루어진다.

4. 큐가 빌 때까지 반복: 큐에서 정점을 하나씩 꺼내어 해당 정점과 인접한 아직 방문하지 않은 정점을 큐에 추가하고 방문 표시를 한다. 이러한 과정을 반복하면서 모든 정점을 탐색한다.

from collections import deque

'''
edge 정보를 담은 graph
key는 node1, value는 node1과 연결된 모든 node2
양방향의 graph일 경우, 한 edge에 연결된 두 node(key)에 모두 edge(value) 정보를 넣음
'''
graph = {1: [3, 4],
         2: [3, 4, 5],
         3: [1, 5],
         4: [1],
         5: [2, 6],
         6: [3, 5]}

root = 1

def bfs(graph, root):
    visited = [False] * (len(graph) + 1)
    queue = deque([root])
    visited[root] = True
    result = []

    while queue:
        node = queue.popleft()
        result.append(node)
        for i in graph[node]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

    return result

result = bfs(graph, root) # [1, 3, 4, 5, 2, 6]

from collections import deque

'''
edge 정보를 담은 graph
key는 node1, value는 node1과 연결된 모든 node2
양방향의 graph일 경우, 한 edge에 연결된 두 node(key)에 모두 edge(value) 정보를 넣음
'''
graph = {1: [3, 4],
         2: [3, 4, 5],
         3: [1, 5],
         4: [1],
         5: [2, 6],
         6: [3, 5]}

root = 1

def bfs(graph, root):
    visited = [False] * (len(graph) + 1)
    queue = deque([root])
    result = []

    while queue:
        node = queue.popleft()
        if not visited[node]:
            visited[node] = True
            result.append(node)
            for i in graph[node]:
                if not visited[i]:
                    queue.append(i)
    return result
    
result = bfs(graph, root) # [1, 3, 4, 5, 2, 6]

Depth-First Search

깊이 우선 탐색(Depth-First Search, DFS)는 그래프나 트리와 같은 자료 구조에서 루트 노드(또는 시작 노드)에서부터 가장 깊은 노드까지 탐색하는 알고리즘이다.

Baekjoon - Depth-first Search

깊이 우선 탐색 알고리즘은 다음과 같이 동작한다:

1. 스택(Stack) 또는 재귀 호출 사용: DFS는 스택 자료 구조를 사용하거나 재귀 함수 호출을 통해 구현된다. 시작 정점을 스택에 넣거나 재귀 함수를 호출하여 시작한다.

2. 깊이 순서 탐색: DFS는 한 정점에서 시작하여 최대한 깊이 탐색한다. 즉, 현재 정점에서 모든 가능한 인접 정점을 탐색하고 나서 다시 이전 정점으로 돌아가서 다른 경로를 탐색한다.

3. 방문 표시: DFS에서도 각 정점을 방문할 때 방문 표시를 한다. 이를 통해 중복 방문을 방지한다.

4. 재귀 함수 또는 스택을 사용한 반복: DFS는 재귀 함수를 사용하거나 스택을 사용하여 구현된다. 현재 정점에서 다음 정점으로 이동한 후, 그 정점에서 다시 깊이 우선 탐색을 진행한다.

'''
edge 정보를 담은 graph
key는 node1, value는 node1과 연결된 모든 node2
양방향의 graph일 경우, 한 edge에 연결된 두 node(key)에 모두 edge(value) 정보를 넣음
'''
graph = {1: [3, 4],
         2: [3, 4, 5],
         3: [1, 5],
         4: [1],
         5: [2, 6],
         6: [3, 5]}

root = 1
visited = [False] * (len(graph) + 1)
result = []

def dfs(graph, node, visited, result):
    visited[node] = True
    result.append(node)

    for i in graph[node]:
        if not visited[i]:
            dfs(graph, i, visited, result)

dfs(graph, root, visited, result) # result = [1, 3, 5, 2, 4, 6]

from collections import deque

'''
edge 정보를 담은 graph
key는 node1, value는 node1과 연결된 모든 node2
양방향의 graph일 경우, 한 edge에 연결된 두 node(key)에 모두 edge(value) 정보를 넣음
'''
graph = {1: [3, 4],
         2: [3, 4, 5],
         3: [1, 5],
         4: [1],
         5: [2, 6],
         6: [3, 5]}

root = 1

def dfs(graph, root):
    visited = [False] * (len(graph) + 1)
    stack = deque([root])
    result = []

    while stack:
        node = stack.pop()
        if not visited[node]:
            visited[node] = True
            result.append(node)
            for i in graph[node][::-1]:
                if not visited[i]:
                    stack.append(i)
    return result
    
result = dfs(graph, root) # [1, 3, 5, 2, 4, 6]