알고리즘 2 (BFS, 백 트래킹, 이진탐색)

1. 그래프(이전 글)

2. DFS(이전 글)

3. BFS

4. 백트래킹

5. 이진탐색

 

3. BFS: 인접한 노드 중 방문하지 않은 모든 노드들을 저장해두고, 순서대로 넣은 노드를 꺼내서 탐색.

큐가 BFS를 구현하는 것에 용이함

1. 루트 노드를 큐에 넣는다.

2. 현재 큐의 노드를 빼서 visited 에 추가한다.

3. 현재 방문한 노드와 인접한 노드 중 방문하지 않은 노드를 큐에 추가한다.

4. 2부터 반복한다.

5. 큐가 비면 탐색을 종료한다.

 

3-1. BFS 구현

from collections import deque

def bfs_queue(graph, 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

 

4. 백트래킹: 필요없는 경우에 수를 가지치기(pruning)하여 시간복잡도를 줄이는 방법

 

 

4-1 N-Queen 문제: 체스판 위에 n개의 퀸이 서로를 잡지 못하게 배치하는 문제(대표적인 백트래킹 문제)

                                퀸이 놓이면 다음 퀸이 이전 퀸의 같은 열과 행 및 대각선을 놓는 경우의 수는 필요없기 때문

 

자세한 내용은 주소 참조: https://zhelddustmq.tistory.com/61

 

 

5. 이진탐색: 배열이 정렬되어있을 경우, 절반씩 줄여나가면서 탐색하는 기법

23을 이진탐색으로 찾는 방법

 

1억 개 목록을 선형탐색할 때, 1억 번을 연산해야 하지만, 이진탐색으로 찾는다면, 27번 안에 찾을 수 있다.

import math

math.log2(100000000) # 26.575424759098897

오름차순으로 정렬된 정수 배열 nums와 정수 target이 주어졌을 때, nums에서 대상을 검색하는 함수를 작성합니다. 
대상이 존재하면 그 색인(인덱스)을 반환합니다. 그렇지 않으면 -1을 반환합니다.
시간복잡도가 O(log n)인 알고리즘을 작성해야 합니다.

Example 1:
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
​
Example 2:
Input: nums = [-1,0,3,5,9,12], target = 2
Output: -1

이진탐색 코드구현

#이진탐색 함수
def binary_search(nums, target):
    def bs(start, end):

        #비교를 다했음에도 불구하고 값이 없던 것
        if start > end:
            return -1

        mid = (start + end) // 2

        #가운데 값보다 크면 가운데서부터 끝 사이의 가운데를 비교
        if nums[mid] < target:
            return bs(mid + 1, end)
        #가운데 값보다 작으면 처음부터 가운데 사이의 가운데를 비교
        elif nums[mid] > target:
            return bs(start, mid - 1)
        #같은 값을 찾았으므로 가운데 값 반환
        else:
            return mid

    return bs(0, len(nums) - 1)