[알고리즘] 선형검색, 이진검색, 트리구조(BFS, DFS)

220930 작성

<본 블로그는 "가장 쉬운 독학_알고리즘 첫걸음편 python 편"의 서적를 참고해서 공부하며 작성하였습니다>

 

 

 

1️⃣선형검색

: 데이터를 리스트에 저장하고 해당 리스트의 맨 앞부터 끝까지 순서대로 조사하여 원하는 데이터 찾기

: 값을 찾을 떄까지 모든 데이터를 검색해야 하므로, 데이터 수가 증가하면 처리에 시간이 걸린다

 

• 데이터 수 n이라 하면 비교횟수의 평균은 (n+1) / 2
• O(n)

# 선형검색
# 원하는 값 찾기

num_list = [23, 12, 55, 32, 45, 76, 88, 52]

def linear (n) :
    for i in num_list :
        if i == n :
            return True
    return False

print(linear(5))

# result
# False

 

 

2️⃣ 이진검색

: 데이터 수가 늘어나도 빠른 속도로 검색을 처리하기

: 검색 범위를 앞이나 뒤의 절반으로 나눠 검색하는 것을 반복

: 리스트의 왼쪽 끝과 오른쪽 끝에서부터 찾는 위치를 절반으로 좁히면서 검색

 

• 데이터 수가 증가했을 때 비교 횟수로 나타남
• 처리 속도는 더 빠르지만, 사전에 데이터를 오름차순, 내림차순으로 정렬할 필요가 있음
• O(logn)

# 이진검색
# 리스트의 왼쪽 끝과 오른쪽 끝에서부터 찾는 위치를 절반으로 좁히면서 검색


data = [10, 15 , 22, 26, 38, 42, 56, 61]
def binary_search (data, value) :
    left = 0
    right = len(data) - 1

    while left <= right :
        mid = (left + right) // 2

        if data[mid] == value :
            return mid
        
        elif data[mid] < value :
            left = mid + 1
        
        else :
            right = mid - 1
    return False

print(binary_search(data, 61))

# result
# 7

 

 

3️⃣ 트리구조 탐색

: 리스트에 저장된 간단한 데이터뿐만 아니라 계층 구조의 데이터를 검색

: 트리구조란, 원과 선을 사용해 계층 구조의 분기를 표현! 가지가 벋어있는 것처럼 보이므로 트리 구조라 불림

: 각 원을 노드 (node), 선을 에지 (edge)

https://medium.com/quantum-ant/%ED%8A%B8%EB%A6%AC-tree-cec69cfddb14

• 너비 우선 탐색 (breadth - first search)
  • 탐색을 시작하는 곳에서부터 가까운 것을 나열하고 각각을 자세히 조사해나가는 방법
  • 탐색할 조건에 부합되는 것은 하나만 얻으면 되며, 결과를 발견된 시점에 처리 종료 할 수 있어 처리속도 빠름

# 너비우선 탐색
# 트리에 있는 노드 각각을 리스트로 표현
# 리스트의 인덱스를 순서대로 출력 -> 트리 구조를 위에서부터 차례대로 탐색한 것임

tree = [[1, 2], [3, 4], [5, 6], [7, 8], [ 9, 10], [11, 12], [13, 14],
[], [], [], [], [], [], [], []]     # 빈 리스트는 각 노드의 탐색 결과를 저장할 영역을 확보하려는 것

data = [0]

while len(data) > 0 :
    pos = data.pop(0)   # pop : 맨 앞에서 꺼내기
    print(pos, end = " ")
    for i in tree[pos] :
        data.append(i)  # 끝에 추가

# result
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

 

• 깊이 우선 탐색 (depth - first search)
  • 원하는 방향으로 탐색을 진행하다가 더 진행되지 않으면, 이전 위치로 돌아가는 방법
  • 백트랙(backtrack) 이라고도 불리며, 문제의 모든 답을 찾을 때 자주 사용
  • 재귀를 사용하는 경우가 많음
  • 모든 답을 찾지 않고 정해진 깊이가지 탐색하는 방법에도 많이 사용
    • 전위 순회 (pre-order traversal)
    • 중위 순위 (in-order traversal))
    • 후위 순위 (post-order traversal)

https://hanamon.kr/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%ED%83%90%EC%83%89-tree-traversal-%ED%8A%B8%EB%A6%AC-%EC%88%9C%ED%9A%8C/

# 깊이 우선 탐색
# 주로 재귀 사용

# 1) 전위 순회를 이용한 탐색
tree = [[1, 2], [3, 4], [5, 6], [7, 8], [ 9, 10], [11, 12], [13, 14],
[], [], [], [], [], [], [], []]     # 빈 리스트는 각 노드의 탐색 결과를 저장할 영역을 확보하려는 것

def search(pos) :
    print(pos, end = " ")       # 자식 노드를 탐색하기 전에 현재 노드 출력
    for i in tree[pos] :        # 자식 노드 탐색
        search(i)               # 재귀 탐색

search(0)

# result
# 0 1 3 7 8 4 9 10 2 5 11 12 6 13 14

# 2) 후위 순회를 이용한 탐색
tree = [[1, 2], [3, 4], [5, 6], [7, 8], [ 9, 10], [11, 12], [13, 14],
[], [], [], [], [], [], [], []]     # 빈 리스트는 각 노드의 탐색 결과를 저장할 영역을 확보하려는 것

def search(pos) :
    for i in tree[pos] :        # 자식 노드 탐색
        search(i)               # 재귀 탐색
    print(pos, end = " ")       # 자식 노드 탐색 후 출력        

search(0)

# result
# 7 8 3 9 10 4 1 11 12 5 13 14 6 2 0

# 3) 중위 순회를 이용한 탐색
tree = [[1, 2], [3, 4], [5, 6], [7, 8], [ 9, 10], [11, 12], [13, 14],
[], [], [], [], [], [], [], []]     # 빈 리스트는 각 노드의 탐색 결과를 저장할 영역을 확보하려는 것

def search(pos) :
    if len(tree[pos]) == 2 :        # 자식 노드가 2개 있을 때
        search(tree[pos][0])
        print(pos, end = " ")       # 왼쪽 노드와 오른쪽 노드 사이에 출력
        search(tree[pos][1])
    elif len(tree[pos]) == 1 :      # 자식 노드가 1개 있을 때
        search(tree[pos][0])
        print(pos, end = " ")
    else :
        print(pos, end = " ")

search(0)

# result
# 7 3 8 1 9 4 10 0 11 5 12 2 13 6 14

• 경로가 복잡한 모드 노드 탐색할 경우
  • 너비 우선 탐색 : 탐색 중인 모든 노드를 저장해야 함
  • 깊이 우선 탐색 : 현재 경로상의 노드를 저장하는 것만으로도 탐색 진행 가능 (메모리 사용량 줄임)
• 최단으로 도달할 길을 하나만 탐색할 경우
  • 너비 우선 탐색 : 발견된 시점에 처리 종료함
  • 깊이 우선 탐색 : 모든 노드를 조사한 뒤 최단인지 여부 판정