탐색 알고리즘(BFS, DFS, 이진탐색)

• 탐색은 주어진 데이터에서 자신이 원하는 데이터를 찾아내는 알고리즘을 말함

5-1 깊이 우선 탐색

• 깊이우선 탐색 (DFS, depth-first search)은 그래프 완전 탐색 기법중 하나.
• 그래프 시작 노드에서 출발하여 탐색할 한쪽 분기를 정하여 최대 깊이까지 탐색을 마친 후 다른쪽 분기로 이동하여 다시 탐색을 수행하는 알고리즘.
• 시간 복잡도 O(V+E)
  • V : 노드개수
  • E : 에지개수

# import sys
# input = sys.stdin.readline

n,m = map(int, input().split() )
a = [[]for _ in range(n+1)]
visited= [False] * (n+1)

def DFS(v):
    visited[v] = True
    for i in a[v]:
        if not visited[i]:
            DFS(i)
for _ in range(m):
    s, e = map(int, input().split())
    # 양방향 에지라서 양쪽으로 에지 더하기
    a[s].append(e)
    a[e].append(s)

count = 0

for i in range(1, n+1):
    if not visited[i]:
        count += 1
        DFS(i)
print(count)

5-2 너비 우선 탐색

• 너비우선 탐색(BFS, breadth-first search)
• 시작노드에서 출발해 시작노드에서 가까운 노드는 먼저 방문하면서 탐색하는 알고리즘.
• 시간복잡도 O(V+E)
  • V : 노드개수
  • E : 에지개수
• 선입선출 방식으로 탐색하므로 큐를 이용해 구현
• 목표노드에 도착하는 경로가 여러개일 때 최단경로를 보장함.

from collections import deque
n, m, start = map(int, input().split())
a = [[] for _ in range(n+1)]

for _ in range(m):
    s, e = map(int, input().split())
    a[e].append(s)
    a[s].append(e)

for i in range(n+1):
    a[i].sort()

def dfs(v):
    print(v, end=' ')
    visited[v] = True
    for i in a[v]:
        if not visited[i]:
            dfs(i)
visited = [False]* (n+1)
dfs(start)

def bfs(v):
    queue = deque()
    queue.append(v)
    visited[v] = True
    while queue:
        now_node = queue.popleft()
        print(now_node, end=' ')
        for i in a[now_node]:
            if not visited[i]:
                visited[i] = True
                queue.append(i)

print()
visited = [False] * (n+1)
bfs(start)

5-3 이진탐색

• 이진 탐색(binary search) : 데이터가 정렬돼 있는 상태에서 원하는 값을 찾아내는 알고리즘
• 대상 데이터의 중앙값과 찾고자 하는 값을 비교해 데이터의 크기를 절반씩 주이면서 대상을 찾음
• 시간복잡도 (O(logN))
• 정렬 데이터에서 원하는 데이터를 탐색할 때 사용하는 가장 일반적인 알고리즘.
• 구현 및 원리가 간단하여 많은 코데에서 부분문제로 요구하는 영역
• 핵심이론
  1. 데이터의 중앙값 선택
  2. 중앙값 > 타깃데이터 일 때, 중앙값 기준으로 왼쪽 데이터 셋을 선택
  3. 중앙값 < 타깃데이터 일 때, 중앙값 기준으로 오른쪽 데이터 셋을 선택
  4. 과정 1~3을 반복하다 중앙값 == 타깃데이터 일 때 탐색을 종료

n = int(input())
n_list = sorted(list(map(int, input().split())))

m = int(input())
m_list = list(map(int, input().split()))

for i in m_list:
    find = False
    target = i

    start = 0
    end = len(n_list)-1

    while start <= end:
        midi = int((start + end)/2)
        midv = n_list[midi]

        if midv > target:
            end = midi-1
        elif midv < target:
            start = midi+1
        else:
            find = True
            break
    if find :
        print(1)
    else :
        print(0)