[공부] 내일배움캠프 알고리즘 2주차 이진탐색, 재귀

내일배움캠프 알고리즘 2주차

이진탐색

• UP, DOWN 게임과 유사하다!

• 반씩 후보를 줄이면서 탐색

• 전제조건 : 일정한 규칙으로 정렬되어있는 데이터

• 숫자를 내림하는 방법
  // 연산자를 이용하면 소수점 이하의 수를 모두 버리고 몫만 나타낼 수 있다

• 총 숫자가 1 ~ N 까지라고 한다면,
  탐색을하면서 범위가 반으로 계속 줄어드므로,
  k번 탐색하면 N / 2^k 개가 남는다.
  이걸 수식으로 표현하면, N / 2^k = 1
  즉, k = log2 _N 횟수를 시도하면 정답을 찾을 수 있다!

• 결론적으로 시간복잡도가 O(log N)

def is_existing_target_number_binary(target, array):
    current_min = 0
    current_max = len(array-1)

    # 중간 index
    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     # 최대값을 시도값 앞의 값으로

        # 중간 index 재설정
        current_guess = (current_min + current_max) // 2

    return False

---

재귀

• 어떤 것을 정의할 때 자기자신을 참조하는 것
• 자기 자신을 계속 호출하는 함수
• 항상 탈출 조건을 고민해야 한다

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


count_down(60)

회문

• 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장을 의미
• ex) 토마토, 오디오, 아시아, 일요일 ...

input = "abcba"


def is_palindrome(string):

    n = len(string)	# 문자열의 길이
    # 0 ~ n-1
    for idx in range(n) :
        if string[idx] != string[n-1 -idx] :
            return False

    return True

print(is_palindrome(input))

• 재귀를 이용한 회문
• 한 글자만 있어도 회문

input = "abcba"

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))