알고리즘 - 2주차 이진탐색 / 재귀함수(팩토리얼, 회문검사)

 

이진 탐색

정렬되어 있는 배열의 중간값을 찾아 답을 찾아나가는 방식

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):
    current_min = 0
    current_max = len(array) - 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_existing_target_number_binary(finding_target, finding_numbers)
print(result)

• max_num = len(array) - 1 는 맨 마지막 인덱스 번호를 넣기 위함.
• (current_min + current_max) // 2 로 중간값인덱스를 구하는데 // 를 사용해서 소숫점 이하는 내림.
• 목표값이 중간값과 최대값 사이에 있다면 중간값의 다음번 인덱스가 최솟값 인덱스가 됨.

 

시간복잡도 : O(logN)

 

---

 

재귀 함수

재귀 : 어떠한 것을 정의할 때 자기 자신을 참조하는 것을 뜻한다.

def count_down(number):
    if number < 0:         # 탈출 조건
        return
    print(number)          # number를 출력하고
    count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 자신을 호출한다!

count_down(60)

• 항상 탈출 조건이 필요하다. 그렇지 않으면 무한 루프에 빠져서 RecursionError가 발생한다.
• 자기자신을 호출함으로써 코드를 간결하고 명확하게 만들 수 있다.

 

 

팩토리얼

# Factorial(N) = N * Factorial(N - 1)
# ...
# Factorial(1) = 1

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


print(factorial(5))

 

 

회문 검사

거꾸로 읽어도 똑같은 단어나 문장

문자열 슬라이스 [ : ]

input = "여보안경안보여"


# 반복문 사용
# def is_palindrome(string):
#     n = len(string)
#     for i in range(n):
#         if string[i] != string[n - 1 - i]:
#             return False
#     return True


# 재귀 함수 활용 : 문제가 축소되는 특징이 보이거나, 특정 구조가 반복되는 것 같은 양상이 보이면
def is_palindrome(string):
    if len(string) <= 1:    # 한글자 남았을때 조건. 탈출 조건 보다 아래에 위치하면 에러발생
        return True

    if string[0] != string[-1]:     # 탈출 조건  # 다르면 바로 False 반환
        return False

    return is_palindrome(string[1:-1])  # 처음과 끝 같다면 자르고 다시 함수 실행


print(is_palindrome(input))

 

 

---

숙제 1. 

Q. 링크드 리스트의 끝에서 K번째 값을 반환하시오.

 

숙제 2.

Q. 배달의 민족 서버 개발자로 입사했다. 상점에서 현재 가능한 메뉴가 ["떡볶이", "만두", "오뎅", "사이다", "콜라"] 일 때, 유저가 ["오뎅", "콜라", "만두"] 를 주문했다. 그렇다면, 현재 주문 가능한 상태인지 여부를 반환하시오.

 

숙제 3.

Q. 음이 아닌 정수들로 이루어진 배열이 있다. 이 수를 적절히 더하거나 빼서 특정한 숫자를 만들려고 한다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들기 위해서는 다음 다섯 방법을 쓸 수 있다.

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target_number이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 반환하시오.