알고리즘 22/11/16 (회문, 이진탐색, 재귀함수)

1. 이진 탐색

finding_target = 14
finding_numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16]


def is_existing_target_number_binary(target, array):
    start_num = 0
    end_num = len(array) - 1
    half_num = (array[start_num] + array[end_num]) // 2

    while start_num <= end_num:
        if half_num == target:
            return True
        elif half_num < target:
            start_num = half_num
            half_num = (array[start_num] + array[end_num]) // 2
        else:
            end_num = half_num
            half_num = (array[start_num] + array[end_num]) // 2
    return False


result = is_existing_target_number_binary(finding_target, finding_numbers)
print(result)

start_num 은 시작 num, end_num 은 행의 마지막 num
행의 시작부터 끝까지 while문을 돌려 타겟이 맞으면 True
없을 시 num 과 타겟의 크기를 비교하여 이진탐색을 해나감

2. 팩토리얼(재귀함수)

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n-1)


print(factorial(5))

재귀함수를 이용하여 팩토리얼을 구했다.
재귀함수는 범위를 줄여나가면서 답을 구하는게 목적이므로
n에 n-1 을 재귀함수로 구해 가면서 마지막 1일 때 리턴되게 함

3. 회문(재귀함수)

input = "가련하시다사장집아들딸들아집장사다시하련가"


def is_palindrome(string):
    if len(string) <= 1:
        return True
    if string[0] != string[-1]:
        return False
    print(string)
    return is_palindrome(string[1:-1])


print(is_palindrome(input))

회문이란 똑바로 읽어도 거꾸로 읽어도 같은 문단이다.
재귀함수로 범위를 줄이기 위해 처음과 끝이 같으면 삭제하여 string의 길이를 줄여나가다 string이 하나만 남으면 True 반환한다.