탐색(Search)와 재귀 알고리즘(Reculsive algorithms)

탐색 (Search)

다수의 원소로 이루어진 데이터에서 특정 원소를 찾아내는 작업

---

1.  선형 탐색 (linear search) or 순차 탐색 (sequential search)
    - 순차적으로 모든 요소를 탐색
    - 배열의 길이에 비례하여 시간이 소모 (Ex_ 1,000,000,000개의 원소 존재 시 최악의 경우 모든 원소를 탐색...)
    - 성능 = O(n)
2. 이진 탐색 (binary search) (= 이분탐색)
    - 배열이 정렬되어 있는 경우에만 사용 가능
    - 찾고자 하는 원소를 배열의 가운데 원소와 비교하여 값이 크다면 오른쪽, 작다면 왼쪽
    - 위의 과정을 반복하여 원하는 값을 추출
    - 예제 코드

def binary_search(a, x):

    lower = 0
    upper = len(a) - 1
    
    while lower <= upper:
        mid = (lower + upper) // 2
        
        if a[mid] == x:
            return ...
        elif a[mid] < x:
            lower = mid + 1
        else:
            upper = mid - 1

---

재귀 알고리즘 (reculsive algorithems)

 - 호출된 함수가 자기 자신을 재호출하여 작업 수행

 - 재귀함수 사용 시 반드시 탈출 조건이 있어야 stack overflow를 방지 가능

 - 메모리 성능에서 보면 재귀함수의 효율은 떨어질 수 있지만, 간결한 코드를 제공하여 DFS/BFS 알고리즘 구현에 있어 꼭 알아야하는 개념

 - 주로 사용되는 경우

• 조합의 수 (n개의 서로 다른 원소에서 m개를 택하는 경우의 수) 구하기
• 하노이의 탑 (크기 순서대로 쌓여 있는 원반을 한 막대에서 다른 막대로 옮기기)
• 피보나치 수열

---

def function(n):
    if n == 0:
        return -1
    else:
        function(n-1)
        print(n)

function(3)

#====================

1
2
3

• function(3)을 호출
  • function(2)를 호출하고 메모리 영역이 구분되고, 변수 생성
  • function(1)을 호출하고 메모리 영역이 구분되고, 변수 생성
  • function(0)이 되면 리턴과 메모리 영역이 구분되고, 변수 생성
  • function(1)로 돌아가 없어짐
  • function(2)로 돌아가 없어짐