[자료구조와 알고리즘] DataStrucure Intermediate

검색과 재귀 ( Searching and Recursion )

▶ 검색 ( Searching )

- 특정 노드를 추가하거나 삭제를 위해서는 검색이 우선되어야 함

- 다양한 알고리즘을 활용하는 경우, 최적 알고리즘 경로를 측정하는데 쓰임

- 검색하는 컬렉션이 무작위이고 정렬되지 않는 경우, 선형검색이 기본적인 검색방법

# 선형 검색 알고리즘

def linear_search(arr, target):
    for idx in range(len(arr)):
        if arr[idx] == target:
            return idx
            
    return -1

▶ 재귀 ( Recursion )

- 재귀 호출은 스택의 개념이 적용되며, 함수의 내부는 스택처럼 관리됨 ( LIFO, 후입선출 )

- 하위 문제를 쉽게 해결할 수 있을 때 까지 문제를 더 작은 하위 문제로 나누는 것을 의미

- 단점 : 재귀를 사용하면 함수를 반복적으로 호출되는 상황이 벌어지므로, 메모리를 더 많이 사용함

#  1 ~ num 까지 합

def oneto100(num):

    if num == 1:
        return 1
    else:
        return num + oneto100(num-1)

# 최대공약수

def factor(num1, num2):

    if num2 == 0:
        return num1

    num1, num2 = max(num1, num2), min(num1, num2)
    return factor(num2, num1 % num2)

■ 분할정복법

하나의 문제를 분할하면서 해결하고 해결 후 하나로 다시 합치는 방법

■ 재귀의 조건

1. Base Case ( 기본 케이스 또는 조건 )가 있어야 함
2. 추가 조건과 기본 케이스의 차이를 확인함
3. 반드시 자기 자신 ( 함수 )를 호출해야 함

■ 재귀 제한

• 파이썬에서는 재귀 깊이의 제한을 1000으로 기본 설정하고 있음
• 재귀 함수의 호출이 1000에 도달했을 때 RecursionError 발생

# 최대 재귀 깊이 늘이기

import sys
sys.setrecursionlimit(3500) # 재귀 깊이 3500으로 변경

트리 ( Tree ) 란?

▶ 용어 정리

• 루트 ( Root ) : 가장 위쪽에 있는 노드, 트리별 하나만 있음
  • 루트와 부모는 다름. 부모노드는 자식노드가 1개 이상 있는 경우에만 존재할 수 있음
• 서브트리 : 자식노드이면서 부모노드역할을 하는 노드가 있는 트리
• 차수 : 노드가 갖고 있는 최대 자식노드 수
• 리프 ( Leaf ) : 레벨별로 가장 마지막에 있는 노드, 단말노드 ( Terminal Node ), 외부노드 ( External Node )  라고도 함. 히프는 트리별로 여러 개가 있을 수 있음
• 레벨 : 루트노드에서 얼마나 멀리 떨어져 있는지를 각각 나타냄. 루트노드의 레벨은 0이며, 아래로 내려갈 때마다 1씩 증가함
• 높이 : 루트에서 가장 멀리 떨어진 리프노드까지의 거리이며, 리프 레벨의 최대값을 높이라고 함
• 형제 노드 : 부모가 같은 두 개의 노드

▶ 이진 트리

- 이진트리는 아래와 같이 각 노드별로, 최대 2개의 서브노드를 가질 수 있음

- 이진트리는 루트노드를 중식으로 두 개의 서브트리로 나눠짐

- 이진트리는 나눠진 두 서브트리도 모두 두 개의 서브트리를 가짐

■ 이진검색트리 ( Binary Search Trees, BST )

이진탐색트리는 노드를 정확하게 정렬해야하는 특정 유형의 이진 트리

class node:
    def __init__(self, value):

        self.left = None
        self.value = value
        self.right = None

class binary_search_tree:
    def __init__(self, head):
        self.head = head

    def insert_node(self, value):
        self.base_node = self.head
        
        while True:
            if value < self.base_node.value:
                if self.base_node.left != None:
                    self.base_node = self.base_node.left
                else:
                    self.base_node.left = node(value)
                    break
            else:
                if self.base_node.right != None:
                    self.base_node = self.base_node.right
                else:
                    self.base_node.right = node(value)
                    break
        

    def search_node(self, value):
        self.base_node = self.head
        
        while self.base_node:
            if self.base_node.value == value:
                return True
            elif value < self.base_node.value:
                self.base_node = self.base_node.left
            else:
                self.base_node = self.base_node.right
        return False

if __name__ == "__main__":

    head = node(16)  
    bt = binary_search_tree(head)

    bt.insert_node(12)
    bt.insert_node(19)
    bt.insert_node(11)
    bt.insert_node(13)
    bt.insert_node(18)
    bt.insert_node(20)
    bt.insert_node(9)
    bt.insert_node(8)
    bt.insert_node(10)

    print(bt.search_node(5))    #False
    print(bt.search_node(-2))   #False
    print(bt.search_node(18))   #True