💛 검색(searching)

• 특정 노드를 추가하거나 삭제를 위해서는 검색이 우선되어야 한다.
• 다양한 알고리즘을 활용하는 경우, 최적 알고리즘 경로를 측정하는데 쓰인다.
• 검색하는 컬렉션이 무작위이고 정렬되지 않은 경우, 선형검색이 기본적인 검색방법이다.

# 선형 검색 알고리즘
# 하나의 반복문과 리스트의 인덱스, 조건문을 활용하여 특정값을 검색할 때까지 반복한다.

def linear_search(arr, target):
    #입력배열의 각 항목을 반복
    for index in range(len(arr)):
        #현재 인덱스의 항목이 비교대상과 같은지 확인
        if arr[index] == target:
            return index
    #전체 배열을 반복할 수 있다면, 비교 대상은 존재하지 않는다.
    #찾는 대상이 없다면 의미없는 숫자인 -1을 반환한다.
    return -1

💛 재귀(recursion)

• 알고리즘과 방법론에서 자주 언급되고 중요한 개념이기 때문에 반복하며 익숙해져야한다.
• 재귀의 개념은 수학적 사고에 기반하고, 코드를 작성하기 전에 문제를 해결하는 재호출 로직을 발견해야 한다.
• 재귀 호출은 스택의 개념이 적용되며, 함수의 내부는 스택처럼 후입선출(LIFO)로 관리된다.
  • 단점: 재귀를 사용하면 함수를 반복적으로 호출하는 상황이 벌어져 메모리를 더 많이 사용하게 된다.
  • 수학적으로 개념이 복잡한 경우에는 시간과 공간(메모리)복잡도 측면에서 효율이 좋지 않더라도 재귀를 사용하여 문제를 해결하는 것이 좋다.
• 재귀에서 중점적으로 생각해야하는 부분은 조건에 따른 반복 계산이다.
• 재귀적으로 문제를 해결하는 방법 중 하나는 분할 정복이 있다.

  분할 정복법
  하나의 문제를 분할하고 해결하는 구체적인 방법론으로 하위 문제를 쉽게 해결할 수 있을 때까지 문제를 더 작은 단위로 나누는 것을 의미한다.

  • 재귀는 해결을 위한 특정 기능을 재호출한다는 측면에서 사용되며, 분할정복은 문제를 분할하고 해결하는 구체적인 방법론이다.
  • 분할정복법을 활용하기 위해서는 재귀개념(기능재호출)이 필요하다.

my_list = [1,2,3,4,5]
def sum_list(items):
    sum = 0
    for i in items:
        sum = sum + i
    return sum

sum_list(my_list)

#아래의 코드처럼 문제를 두 개의 하위 문제로 나눌 수 없을 때까지 분할할 수 있다.
1 + 2 + 3 + 4 + 5
(1 + (2 + 3 + 4 + 5))
(1 + (2 + (3 + 4 + 5)))
(1 + (2 + (3 + (4 + 5))))
(1 + (2 + (3 + (4 + (5)))))

#분리된 내용을 의사코드를 활용해서 먼저 로직을 해석해볼 수 있다.
sum_list(items)
    if the length of item is 1:
        return the 1 item in the list
    else:
        return the first items from the list + sum_list(the rest of the items)
        
#의사코드를 구현되는 코드로 만들어주기
def sum_list(items):
    if len(items) == 1:
        return items[0]
    else:
        return items[0] +sum_list(items[1:])

재귀 조건 1: base case가 존재한다.

1) base case(기본 케이스 또는 조건)가 있어야 한다.

• 알고리즘은 특성상 반복을 중지할 수 있다.
• 아래의 sum_list 함수에서도 알고리즘이 반복을 중지하도록 하는 조건이 내부에 있다.

def sum_list(items):
    if len(items) == 1: #base case
        return items[0]
    else:
        return items[0]+sum_list(items[1:])

재귀 조건 2: 추가 조건과 기본 케이스의 차이

2) 기본 케이스와 추가 조건이 차이가 있어야 한다.

def sum_list(items):
    if len(items) == 1: # Base Case(항목이 1개인 경우가 기본 케이스)
        return items[0]
    elif len(items)>1:
        print("items:",items[0:])
        return items[0] + sum_list(items[1:]) # items[:]는 한 항목씩 감소한다.
        
print("sum_list:",sum_list([2,3,4,5]))

위의 재귀에서는 sum_list에 전달된 Items는 한 항목씩 감소한다.

재귀 조건 3: 반드시 자기 자신(함수)를 호출해야 한다.

3) 재귀조건을 만족하기 위해서는 자기 자신을 호출히야 한다.
(함수의 마지막 죽에서 재귀 작업을 수행하는 경우가 많은 것 같다.)

def sum_list(items):
    if len(items) == 1: # Base Case
        return items[0]
    else:
        return items[0] + sum_list(items[1:]) # 반복적으로 자기자신을 호출한다.