자료구조 2주차_이진탐색과 재귀함수

자료구조 2주차_이진탐색과 재귀함수

 

---

이진탐색

 

📌 숫자 내림

>>> print((4 + 5) / 2)
4.5
>>> print((4 + 5) // 2)
4

소수점 이하의 수는 모두 버리고 몫만 나타낼 수 있음!

 

📄나의 코드

finding_target = 5
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 = array[0]
    end = array[len(array)-1]

    while start <= end:
        mid = (start + end) // 2
        if target is array[mid]:
            return True
        elif target < array[mid]:
            end = mid - 1
        elif target > array[mid]:
            start = mid + 1
            
    return False


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

그런데, finding_target에 16를 초과하는 수를 넣으면 배열 index초과 오류가 발생한다.

 

📄 나의 코드 수정

finding_target = 5
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 = 0
    end = len(array)-1

    while start <= end:
        mid = (start + end) // 2
        if target is array[mid]:
            return True
        elif target < array[mid]:
            end = mid - 1
        elif target > array[mid]:
            start = mid + 1
            
    return False


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

강의와 강의 노트를 참고해 start와 end를 배열의 인덱스값으로 해주니 배열 index초과 없이 잘 나온다!!

배열 안에서 범위를 조정해야 하니 start와 end는 배열 index범위 내로 해줘야 한다!

 

---

무작위 수 찾기

 

📄 나의 코드

finding_target = 2
finding_numbers = [0, 3, 5, 6, 1, 2, 4]

def is_exist_target_number_binary(target, numbers):
    start = 0
    end = len(numbers) - 1

    numbers.sort()

    while start <= end:
        mid = (start + end) // 2
        if target == numbers[mid]:
            return True
        elif target < numbers[mid]:
            end = mid -1
        elif target > numbers[mid]:
            start = mid + 1

    return False


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

정렬시키고 하라는 줄 알고 내장함수 sort() 활용해서 이진탐색 해봤다.

그런데 낚시 문제였다고 한다...

하하하핳 이진탐색은 정렬된 배열에서만 적용 가능한 알고리즘이다!

---

재귀함수

 

📌 재귀란?

Recurison

어떠한 것을 정의 할 때 자기 자신을 참조하는 것

자기 자신을 호출하는 함수!

 

📌 보신각 카운트 다운

60에서 0까지 숫자를 출력하시오.

def count_down(number):
    print(number) # number를 출력하고

    # 탈출조건
    if number > 0 :
        count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!


count_down(60)

재귀함수를 하기 위해서는 반드시 탈출조건이 있어야 함!!!

---

팩토리얼

n! = n × (n-1) × (n-2) × ... × 1

 

📄 코드

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

    return n * factorial(n-1)

f(n)=f(n) × f(n-1) × f(n-2) × ... × f(1)

탈출조건은 f(1) = 1 !!!

---

회문(palindrome)검사

똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장을 단어나 문장을 의미합니다.

 

📄 나의 코드

input = "abcba"


def is_palindrome(string):
    #반복문 이용.
    n = len(string) // 2

    for i in range(n):
        # print(string[i])
        # print(string[len(string) - 1 -i])
        if string[i] != string[len(string)-1-i]:
            return False
    return True


print(is_palindrome(input))

 

📄 재귀함수 활용

input = "소주만병만주소"
# print(input[1:-1])

# 소주만병만주소
# 주만병만주
# 만병만
# 병

# 맨앞뒤 검사를 했다면 is_palindrome(string[1:-1])
def is_palindrome(string):
    if len(string) <= 1:
        return True
    if string[0] != string[-1]:
        return False
    return is_palindrome(string[1:-1])


print(is_palindrome(input))

0번 인덱스부터 문자열 끝나기 전까지 출력하는 str[1:-1] 이용해서 문자열 다듬기!!