[내일배움캠프 4-2일] DFS, BFS, 알고리즘 스쿼드 과제

DFS

DFS(Depth First Search)는 깊이 우선 탐색.

말 그대로 하나의 루트를 최대한 깊숙하게 들어가며 탐색하고 다시 돌아가 다른 루트로 탐색하는 방식.

자식 노드들을 순서대로 탐색한다고 생각하면 된다.

이러한 그래프가 있다고 했을 때 DFS를 두가지 방법으로 구현할 수 있다.

 

1. 재귀함수로 구현
[1, 2, 5, 6, 7, 3, 4] 순서로 탐색, 왼쪽 먼저 가는 깊이 우선 탐색이라고 생각하면 된다.

def dfs_recursive(node, visited):
    # 방문처리
    visited.append(node)

    # 인접 노드 방문
    for adj in graph[node]:
        if adj not in visited:
            dfs_recursive(adj, visited)

    return visited

2. stack으로 구현
[1, 4, 3, 5, 7, 6, 2] 순서, 오른쪽 먼저 가는 깊이 우선 탐색.

def dfs_stack(start):
    visited = []
    # 방문할 순서를 담아두는 용도
    stack = [start]

    # 방문할 노드가 남아있는 한 아래 로직을 반복한다.
    while stack:
        # 제일 최근에 삽입된 노드를 꺼내고 방문처리한다.
        top = stack.pop()
        visited.append(top)
        # 인접 노드를 방문한다.
        for adj in graph[top]:
            if adj not in visited:
                stack.append(adj)

    return visited

---

BFS

BFS(Breadth First Search)는 너비 우선 탐색.

한 노드를 기준으로 인접한 노드들을 우선으로 탐색하는 방식.

 

BFS는 큐로 구현한다.

def bfs_queue(start):
    visited = [start]
    q = deque([start])

    while q:
        node = q.popleft()
        for adj in graph[node]:
            if adj not in visited:
                q.append(adj)
                visited.append(adj)

    return visited

assert bfs_queue(1) == [1, 2, 3, 4, 5, 6, 7]

---

수 찾기

# 시간초과 실패
N = int(input())
N_list = list(map(int, input().split()))
M = int(input())
M_list = list(map(int, input().split()))

for m in M_list:
    if m in N_list:
        print(1)
    else:
        print(0)

당연히 이걸 바라고 낸 문제가 아니겠지만 일단 풀어본 방법.

역시나 시간초과로 오답.

모든 M에 대해 모든 N을 탐색하게 되며, 시간 복잡도 측면에서 상당히 비효율적이다.

 

# 이진 탐색 사용
import sys
input = sys.stdin.readline

def binary_search(target, arr):
    start = 0
    end = len(arr) - 1

    while start <= end:
        # 중간 인덱스를 계산하여 mid 변수에 할당
        mid = (start + end) // 2
        # mid 가 찾는 값(target)인 경우 True 반환
        if target == arr[mid]:
            return True
        # 찾는 값이 mid보다 작을 경우 중간 기준 왼쪽에 있기 때문에 end를 당겨온다
        # mid보다 작기 때문에 -1 한 인덱스까지 범위를 지정
        elif target < arr[mid]:
            end = mid - 1
        # 찾는 값이 mid보다 큰 경우 start를 당겨온다
        else:
            start = mid + 1
    # 다 탐색 후 값이 없다면 False 반환
    return False

N = int(input())
N_list = list(map(int, input().split()))
M = int(input())
M_list = list(map(int, input().split()))

# 이진탐색은 범위의 인자들이 크기의 순서대로 정렬되어있다는 전제 하에 진행
N_list.sort()

for m in M_list:
    # 값이 존재하면, 즉 return True인 경우
    if binary_search(m, N_list):
        print(1)
    # 아닌경우
    else:
        print(0)

이진 탐색으로 해결. 개념 자체는 쉽다.

우선 숫자 크기 순서대로 리스트를 정렬한 뒤, 중간값 기준 왼쪽에 있을지 오른쪽에 있을지 탐색하는 방법.

이진 탐색을 통해 시간 복잡도를 O(log N)으로 유지할 수 있음.

---

오늘의 회고

2주차 강의를 들어갔다. 역시나 이해하고 구현하는데 시간이 오래걸림. 그래도 긴 시간 집중력을 유지했다..

오늘자 과제는 하나밖에 못풀었다. 내일 세개 푸는걸로.

답을 제출하는게 중요한게 아니라고 생각해야 할 듯. 이해가 가장 중요한 것 같다.

 

내일의 목표는 과제 세개 마무리 + 2주차 강의 진도 빼기