IT-garden

이진 탐색(Binary Search)은 리스트를 반으로 나눠 검색하며 원하는 값을 찾는 알고리즘입니다.

원하는 값은 key로 주어지고 탐색의 범위는 low와 high로 주어집니다.

리스트의 중앙에 있는 값을 확인해 찾고자 하는 key 값이 리스트의 중앙에 있는 값보다 작은지 큰지에 따라 검색 범위를 반으로 줄입니다.

- key 값이 리스트의 중간 요소와 일치하면 탐색을 끝냅니다.

- key 값이 리스트의 중간 요소보다 큰 경우 중간 요소 이후의 리스트만 탐색합니다.

- key 값이 리스트의 중간 요소보다 작은 경우 중간 요소 이전의 리스트만 탐색합니다.

이진 탐색을 하기 위해서는 리스트는 반드시 정렬되어 있어야 합니다.

이진 탐색은 이분 탐색이라고도 합니다.

a=[1, 3, 5, 7, 9, 11, 13]

def Binary_Search(key, low, high):

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

        if key == a[middle]:
            return middle

        elif key > a[middle]:
            low = middle + 1
            
        elif key < a[middle]:
            high = middle - 1
        
    return -1
        
# 출력>>6
print(Binary_Search(13, 0, 6))

# 출력>>-1
print(Binary_Search(10, 0, 6))

# 출력>>2
print(Binary_Search(5, 0, 4))

# 출력>>-1
print(Binary_Search(6, 0, 4))

함수 Binary_Search이 이진 탐색 알고리즘입니다.

Binary_Search(13, 0, 6)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 6까지에서 key가 13인 인덱스를 찾습니다.

Binary_Search(10, 0, 6)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 6까지에서 key가 10인 인덱스를 찾습니다.

Binary_Search(5, 0, 4)

low가 0이고 high가 4입니다. 리스트 a의 인덱스 0에서 4까지에서 key가 5인 인덱스를 찾습니다.

Binary_Search(6, 0, 4)

low가 0이고 high가 4입니다. 리스트 a의 인덱스 0에서 4까지에서 key가 6인 인덱스를 찾습니다.

a=[1, 3, 5, 7, 9, 11, 13]

def Binary_Search(key):
    low = 0
    high = len(a) - 1

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

        if key == a[middle]:
            return middle

        elif key > a[middle]:
            low = middle + 1
            
        elif key < a[middle]:
            high = middle - 1
        
    return -1
        
# 출력>>6
print(Binary_Search(13))

# 출력>>-1
print(Binary_Search(10))

탐색의 범위를 low와 high로 설정하지 않고 리스트 전체에서 key를 찾는 이진 탐색 알고리즘입니다.

가장 많이 사용하는 이진 탐색 알고리즘 코드입니다.

이진 탐색 알고리즘의 시간복잡도는 O(logN)입니다.

순차 탐색(Sequential Search)은 탐색 방법에서 가장 간단하고 직접적인 탐색 알고리즘입니다.

순차 탐색은 리스트의 요소를 처음부터 마지막까지 하나씩 검사해서 원하는 값을 찾는 방법입니다.

원하는 값은 key로 주어지고 탐색의 범위는 low와 high로 주어집니다.

탐색에 성공하면 원하는 값의 인덱스를 반환하고 그렇지 않으면 -1을 반환합니다.

순차 탐색은 선형 탐색(linear search)이라고도 합니다.

a=[1, 3, 5, 7, 2, 4, 6]

def Sequential_Search(key, low, high):

    for i in range(low, high+1):
        if a[i] == key:
            return i

    return -1

# 출력>>6
print(Sequential_Search(6, 0, 6))

# 출력>>-1
print(Sequential_Search(10, 0, 6))

# 출력>>0
print(Sequential_Search(1, 0, 3))

# 출력>>-1
print(Sequential_Search(2, 0, 3))

함수 Sequential Search이 순차 탐색 알고리즘입니다.

Sequential_Search(6, 0, 6)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 6까지에서 key 6의 인덱스를 찾습니다.

Sequential_Search(10, 0, 6)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 6까지에서 key 10의 인덱스를 찾습니다.

Sequential_Search(1, 0, 3)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 3까지에서 key 1의 인덱스를 찾습니다.

print(Sequential_Search(2, 0, 3)

low가 0이고 high가 6입니다. 리스트 a의 인덱스 0에서 3까지에서 key 2의 인덱스를 찾습니다.

a=[1, 3, 5, 7, 2, 4, 6]

def Sequential_Search(key):
    for i in range(len(a)):
        if a[i] == key:
            return i

    return -1

# 출력>>6
print(Sequential_Search(6))

# 출력>>-1
print(Sequential_Search(10))

탐색의 범위를 low와 high로 설정하지 않고 리스트 전체에서 key를 찾는 순차 탐색 알고리즘입니다.

가장 많이 사용하는 순차 탐색 알고리즘 코드입니다.

정렬된 리스트와 정렬되어 있지 않은 리스트에 모두 사용 가능합니다.

순차 탐색은 탐색에 성공하면 평균 (n+1)/2번 비교하고 탐색에 실패하면 n번 비교합니다.

순차 탐색 알고리즘의 시간 복잡도는 O(n)입니다.

만약 리스트가 정렬되어 있다면 위의 코드는 오랜 시간이 걸려서 비효율적인 방법입니다.

그래서 정렬되어 있는 리스트에서는 좀 더 간단하게 순차 탐색을 할 수 있습니다.

정렬된 리스트는 순차 탐색을 실행하는 도중 key 값보다 큰 항목을 만나면 그 뒤의 항목들은 모두 key 값이 아니라는 점을 기억해야 합니다.

a=[1, 3, 5, 7, 9, 11, 13]

def Sequential_Search(key):
    for i in range(len(a)):
        if a[i] > key:
            return -1
        
        if a[i] == key:
            return i

    return -1
# 출력>>2
print(Sequential_Search(5))

# 출력>>-1
print(Sequential_Search(10))

# 출력>>-1
print(Sequential_Search(17))

리스트에 key 값이 존재하거나 key 값이 리스트의 맨 마지막 요소보다 큰 경우 위의 순차 탐색과 같습니다.

하지만 해당 항목이 리스트에 존재하지 않고 리스트의 맨 마지막 요소보다 작아서 비교 횟수가 반이 됩니다.

그러나 시간 복잡도는 O(n)으로 동일합니다.

깊이 우선 탐색(DFS : Depth First Search)은 시작점으로부터 갈 수 있는 점 중 한 곳을 가서 그 곳에서 또 방문할 수 있는 점을 가서 방문할 수 있는 점이 없을 때까지 깊게 갔다 나오는 탐색 방법입니다.

깊이 우선 탐색은 크게 2가지 문제에서 자주 사용됩니다.

1. 그래프를 모두 탐색하는 문제

2. 특정 조합을 뽑는 문제

깊이 우선 탐색의 방법은
1. 하나의 점을 방문하고
2. 하나의 점과 연결 되어 있는 곳을 모두 방문하고 나옵니다.

깊이 우선 탐색에서는 재귀 함수를 이용합니다.

위와 같은 그래프가 있다고 가정하고 깊이 우선 탐색을 실시해보겠습니다.

시작점은 1로 생각하고 모든 그래프를 탐색하려고 합니다.

점을 방문할때는 더 작은 순서로 방문하도록 하겠습니다.

방문했는지 확인하기 위한 배열에 모든 값을 0으로 초기화합니다.

기존 그래프에서 1을 처음 방문합니다.

방문 완료를 배열의 1 자리의 값을 1로 바꾸는 것을 통해 알려줍니다.

1과 연결된 점은 2와 3이 있는데 작은 것을 먼저 방문하기로 했으니 2를 방문합니다.

배열의 2 자리의 값을 1로 바꿔줍니다.

2과 연결된 점은 4와 5가 있는데 작은 것을 먼저 방문하기로 했으니 4를 방문합니다.

배열의 4 자리의 값을 1로 바꿔줍니다.

4와 연결된 점은 2인데 2는 이미 방문을 했고 더이상 방문할 점이 없습니다.

4번에서 직전에 방문한 점인 2로 되돌아옵니다.

그 후 2에서 방문하지 않은 5를 방문합니다.

배열의 5 자리의 값을 1로 바꿔줍니다.

5와 연결된 점은 2인데 2는 이미 방문을 했습니다.

2와 연결된 점은 1, 4, 5가 있는데 모두 방문을 했습니다.

그럼 1로 돌아갑니다.

1과 연결된 점은 2와 3인데 방문하지 않은 3으로 가서 방문을 합니다.

배열 3 자리의 값을 1로 바꿔줍니다.

3과 연결된 점 중 방문하지 않은 6을 방문합니다.

6과 연결된 점 중 방문하지 않은 점이 없으므로 3으로 돌아갑니다.

3에서도 방문하지 않은 점이 없기 때문에 1로 돌아갑니다.

1번에서도 방문할 점이 없습니다.

그럼 모든 점들의 방문이 끝나 탐색이 종료됩니다.

위의 그래프에서 깊이 우선 탐색의 방문 순서는 1 → 2 → 4 → 5 → 3→ 6 입니다.

재귀 함수를 이용한 깊이 우선 탐색의 파이썬 코드입니다.

n = 6 #정점의 수 : 6 (1, 2, 3, 4, 5, 6)
v = 1 #시작점
b = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 6]]

a = [[] for i in range(n+1)]

for i in range(len(b)):
    x, y = b[i]
    a[x].append(y)
    a[y].append(x)
    
for i in a: # 작은 수부터의 방문을 위해 정렬
    i.sort()

ch = [0] * (n+1)

def dfs(node):
    ch[node] = 1
    print(node, end=' ')

    for i in a[node]:
        if ch[i] != 1:
            dfs(i)

dfs(v)

# 최종 출력>>1 2 4 5 3 6 

너비 우선 탐색(BFS : Breadth First Search)은 시작점으로부터 가까운 점을 먼저 방문하고 멀리 떨어져 있는 점을 나중에 방문하는 탐색 방법입니다.

특징은 시작점으로부터 거리가 가까운 점의 순서로 탐색이 진행됩니다.

거리의 의미는 시작점으로부터 어느 점까지의 경로 중 가장 짧은 경로의 길이를 의미합니다.

즉, 거리가 a인 점들을 모두 방문하고 거리가 a + 1인 점들을 모두 방문합니다.

너비 우선 탐색은 크게 2가지 문제에서 자주 사용됩니다.

1. 그래프를 모두 탐색하는 문제

2. 특정 그래프에서 가중치가 모두 같을 때 최단거리를 찾는 문제

너비 우선 탐색의 방법은

1. 큐에서 하나를 꺼내 제거하고(제거 하는 것이 방문한 점)

2. 해당 점과 연결되어 있는 점들 중 방문하지 않은 점을 모두 큐에 넣습니다.

너비 우선 탐색에서는 큐를 사용합니다.

큐는 방문한 점들을 저장하고 제거하는데 사용하고 큐가 공백이 될 때까지 탐색이 계속됩니다.

위와 같은 그래프가 있다고 가정하고 너비 우선 탐색을 실시해보겠습니다.

시작점은 1로 생각하고 모든 그래프를 탐색하려고 합니다.

점을 방문할때는 더 작은 순서로 방문하도록 하겠습니다.

기존 그래프에서 1을 큐에 넣어줍니다. 1이 시작점이기 때문입니다.

그리고 1을 방문하여 큐에서 1을 제거하고 1과 연결되어 있는 점들 중 방문하지 않은 점인 2와 3을 큐에 넣습니다.

큐에서 다음으로 2를 방문하여 큐에서 2를 제거하고 2와 연결되어 있는 점들 중 방문하지 않은 점을 모두 큐에 넣습니다.

여기서 1은 이미 방문했기 때문에 큐에 넣지 않고 4와 5를 넣습니다.

다음으로 3를 방문하여 큐에서 3를 제거하고 3와 연결되어 있는 점들 중 방문하지 않은 점을 모두 큐에 넣습니다.

여기서 1은 이미 방문했기 때문에 6만 큐에 넣습니다.

큐에서 4를 방문하며 4를 제거합니다. 이때 4에 연결된 점들 중 방문하지 않은 점이 없기 때문에 큐에 값을 넣어주지 않습니다.

마찬가지로 5도 방문하고 큐에서 제거해줍니다.

마지막으로 6도 방문하고 큐에서 제거해줍니다.

그럼 모든 점들의 방문이 끝나 탐색이 종료됩니다.

위의 그래프에서 너비 우선 탐색의 방문 순서는 1 → 2 → 3 → 4 → 5→ 6 입니다.

큐를 이용한 너비 우선 탐색의 파이썬 코드입니다.

import queue

n = 6 # 정점의 수 : 6 (1, 2, 3, 4, 5, 6)
v = 1 # 시작점
b = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 6]]

a = [[] for i in range(n+1)]

for i in range(len(b)):
    x, y = b[i]
    a[x].append(y)
    a[y].append(x)
    
for i in a: # 작은 수부터의 방문을 위해 정렬
    i.sort()

ch = [0] * (n+1)

def bfs(start):
    q = queue.Queue()
    q.put(start)
    ch[start] = 1

    while not q.empty():
        now = q.get()
        print(now, end=' ')
        for i in a[now]:
            if ch[i] != 1:
                ch[i] = 1
                q.put(i)
                
bfs(v)

# 최종 출력>>1 2 3 4 5 6

덱을 이용한 너비 우선 탐색의 파이썬 코드입니다.

from collections import deque

n = 6 #정점의 수 : 6 (1, 2, 3, 4, 5, 6)
v = 1 #시작점
b = [[1, 2], [1, 3], [2, 4], [2, 5], [3, 6]]

a=[[] for i in range(n+1)]

for i in range(len(b)):
    x, y = b[i]
    a[x].append(y)
    a[y].append(x)
    
for i in a: # 작은 수부터의 방문을 위해 정렬
    i.sort()

ch = [0] * (n+1)

def bfs(start):
    de = deque()
    de.append(start)
    ch[start] = 1 

    while len(de) != 0:
        now = de.popleft()
        print(now, end=' ')
        for i in a[now]:
            if ch[i] != 1:
                ch[i] = 1
                de.append(i)
                
bfs(v)

# 최종 출력>>1 2 3 4 5 6