TIL(2022-11-15) 알고리즘 (재귀 , 2주차 숙제)

/ 재귀함수

재귀 함수는 바로 자기 자신을 호출하는 함수
간결하고 효율성 있는 코드를 작성할 수 있기 때문에 사용

---

회문검사, 재귀함수 / 슬라이싱 이용

input = "소주만병만주소"


def is_palindrome(string): 
    # is_is_palindrome("소주만병만주소") -> 
    #is_is_palindrome("주만병만주") -> is_is_palindrome("만병만") -> is_is_palindrome("병")
    if len(string) <= 1: # 패스 .... is_is_palindrome("병") True 반환
        return True
    if string[0] != string[-1]: # 맨 앞 뒤 문자 같다, 패스 ....
        return False

    return is_palindrome(string[1:-1]) # 맨앞뒤 자르고 다시호출 is_is_palindrome("주만병만주") ....

print(is_palindrome(input))

---

문제2, 배달의 민족 배달 가능 여부

shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]


def is_available_to_order(menus, orders):
    menus.sort() # 정렬된 menus
    for order in orders: # orders 중 하나씩 반복
        if not is_existing_target_number_binary(order, menus): # 아래함수 충족못하면
            return False # False
    return True # 아니면 True

def is_existing_target_number_binary(target,array): # 하나의 타겟 , munus에 존재하는지 확인
    current_min = 0
    current_max = len(array) -1 # 최댓값 인덱스, menus 길이 -1
    current_guess = (current_min + current_max) // 2

    while current_min <= current_max:
        if array[current_guess] == target:
            return True
        elif array[current_guess] < target:
            current_min = current_guess + 1
        else:
            current_max = current_guess - 1
        current_guess = (current_min + current_max) //2

    return False


result = is_available_to_order(shop_menus, shop_orders)
print(result)

---

문제2, 집합자료형 이용한 두번째 방법
( 집합은 중복을 허용하지 않는 자료형입니다)

shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]


def is_available_to_order(menus, orders):
    menus_set = set(menus) # set() 집합자료형
    for order in orders:
        if order not in menus_set: # 집합에 포함되어있지 않다면?
            return False # False
    return True


result = is_available_to_order(shop_menus, shop_orders)
print(result)

---

문제3

numbers = [1, 1, 1, 1, 1]
target_number = 3
result_count = 0


def get_all_ways_to_by_doing_plus_or_minus(array, target, current_index, current_sum):
    # 구현해보세요!
    if current_index == len(array): # 재귀 함수 탈출조건, 현재인덱스위치인덱스 = 어레이의 길이 같다면
        if current_sum == target: # 그리고 current_sum = 타겟의 값과 같다면
            global result_count 
            # 파이썬의 Call by Object Reference라는 개념 때문에 
            #함수 외부의 변수 사용하려면 global변수 사용해야한다
            result_count += 1 # 만족하는 경우만큼 1더함
        return
    get_all_ways_to_by_doing_plus_or_minus( # 위의 if 경우 아니라면
    array,target, current_index + 1, current_sum + array[current_index] 
    ) # 1번 : 어레이 , 타겟, 현재위치 인덱스 + 1(어레이의 다음 수), 현재까지 합 + 어레이의 현재위치 인덱스값(+연산자 쓸경우)
    get_all_ways_to_by_doing_plus_or_minus(
    array,target, current_index + 1, current_sum - array[current_index] 
    ) # 2번 : 어레이 , 타겟, 현재위치 인덱스 + 1(어레이의 다음 수), 현재까지 합 - 어레이의 현재위치 인덱스값(-연산자 쓸경우)
    
# 1번의 1번2번 그 1번의 1번2번... 모든경우의수 계산한다

get_all_ways_to_by_doing_plus_or_minus(numbers,target_number, 0, 0)
# 위에 정의한 함수 실행, 변수를 다음과 같이 받음 numbers, taget_number, 0 , 0 
#											(초기 어레이 인덱스값, 현재까지 합은 0이다)
print(result_count)