알고리즘 2주차 - 이진탐색, 재귀

이진탐색과 재귀함수

• 이진탐색은 반을 쪼개고 탐색하는 방식

• 순차탐색은 하나하나 탐색하는 방식

이진탐색을 항상 사용할 수 있는 것은 아니므로 어떨 때 사용 가능한지 배워야함

이진탐색 vs 순차탐색

이진탐색: 1~100 숫자 맞추기 놀이를 한다고 했을 때 "범위의 절반인 50"을 시도하는 방식.

• 50을 말한다.

• 대답이 up이라면 1~49는 후보에서 없어진다.

• 대답이 down이라면 51~100은 후보에서 없어진다.

• ............

# 예제 코드. 14를 찾는 코드
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)

순차탐색: 위 게임과 동일할 시 1~100을 순차적으로 시도하는 방식

• 1을 말한다

• 2를 말한다.

• .............

# 예제 코드. 14를 찾는 코드
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_sequential(target, array):
    for number in array:
        if target == number:
            return True

    return False


result = is_existing_target_number_sequential(finding_target, finding_numbers)
print(result)  # True

비교

이진탐색: 3번 째에 찾음 → O(log n)

순차탐색: 14번 째에 찾음 → O(N)

이진탐색:

총 숫자가 1~N 까지라고 한다면, 1번 탐색하면 반절이 줄어드니 N/2 개가 남습니다. 2번 탐색하면 반절이 줄어드니 N/4 = N/2^2 개가 남습니다. 3번 탐색하면 반절이 줄어드니 N/8 = N/2^3 개가 남습니다. .... k번 탐색하면 반절이 줄어드니 N/2^k 개가 남습니다. 이 때, 이분탐색을 열심히 시도해서 딱 1개만 남았다고 가정을 해보겠습니다. 이걸 수식으로 표현하면, N/2^k = 1 입니다. 즉, k = \log_2{N} 횟수를 시도하면 정답을 찾을 수 있습니다!

무작위 수 찾기

❓

Q. 다음과 같이 숫자로 이루어진 배열이 있을 때, 2이 존재한다면 True 존재하지 않는다면 False 를 반환하시오.

[0, 3, 5, 6, 1, 2, 4]

# 코드 스니펫
finding_target = 2
finding_numbers = [0, 3, 5, 6, 1, 2, 4]

def is_exist_target_number_binary(target, numbers):
    # 이 부분을 채워보세요!
    return 1

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

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

def is_exist_target_number_binary(target, numbers):
    numbers.sort() # [0, 1, 2, 3, 4, 5, 6]
    current_min = 0
    current_max = len(numbers) - 1
    current_guess = (current_min + current_max) // 2

    while current_min <= current_max:
        if numbers[current_guess] == target:
            return True
        elif numbers[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_exist_target_number_binary(finding_target, finding_numbers)
print(result)

• 이진탐색을 하려면 순차적으로 오름차순으로 정렬되어 있어야 함

재귀 함수

• 재귀란? 어떠한 것을 정의할 때 자기 자신을 참조하는 것

• 재귀 함수란 바로 자기 자신을 호출하는 함수

👨‍🏫

어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다. "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어. 마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지. 그의 답은 대부분 옳았다고 하네. 그런데 어느날, 그 선인에게 한 선비가 찾아와서 물었어. "재귀함수가 뭔가요?" "잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을...

• 그렇다면 재귀 함수를 왜 사용할까?
  • 간결하고 효율성 있는 코드를 자기 반복을 함으로써 작성 가능
  • 예) 카운트 다운 - 60부터 0까지 사람들이 숫자를 외친다면 어떻게 재귀를 이용할까?

  def count_down(number):
      print(number)          # number를 출력하고
      if number == 0: # number가 0일 때는 스톱, 이것이 없으면 RecursionError 남(무한루프)
          return
      else:
          count_down(number - 1) # count_down 함수를 number - 1 인자를 주고 다시 호출한다!
  
  
  count_down(60)

  • 재귀 함수를 쓰기 전에는 탈출 조건 을 미리 생각하자!
  • 재귀 함수는 자기 자신을 호출함으로써 코드를 간결하고 명확하게 할 수 있음

  재귀 - 팩토리얼

  • 팩토리얼: 팩토리얼은 1부터 어떤 양의 정수 n까지의 정수를 모두 곱한 것을 의미
    • 3! = 3*2*1 = 6
    • Factorial(n) = n * Factorial(n-1)

  # 코드
  def factorial(n):
      # 이 부분을 채워보세요!
      if n == 1:
          return 1
      return n * factorial(n-1)
  
  
  print(factorial(5))

  • 회문 문제: 회문은 똑바로 읽으나 거꾸로 읽으나 똑같은 단어나 문장을 의미
    • 토마토, 아시아, 오디오 등
    • is_palindrome("토마토") = True

    소주만병만주소가 회문인지 알기 위해서는, 아래와 같은 검사들이 필요합니다. ↓ ↓ 소주만병만주소 첫 번째 글자와 맨 뒤에서 첫번째 글자가 같아야 합니다. ↓ ↓ 소주만병만주소 두 번째 글자와 맨 뒤에서 두번째 글자가 같아야 합니다. ↓ ↓ 소주만병만주소 세 번째 글자와 맨 뒤에서 세번째 글자가 같아야 합니다. ↓ 소주만병만주소 마지막 남은 가운데 글자는 뭐가 오든 상관 없습니다!

  # 일반적인 방법
  input = "abcba"
  
  
  def is_palindrome(string):
      n = len(string)
      for i in range(n):
          if string[i] != string[n-1-i]: #인덱스기 때문에 -1 해주는 것
              return False
      return True
  
  
  print(is_palindrome(input))

  # 재귀를 이용한 방법
  input = "소주만병만주소"
  
  # is_palindrom(string) -> 조건에 맞다면 -> is_palindrom(string[1:-1]
  def is_palindrome(string):
      if string[0] != string[-1]:
          return False
      if len(string) <= 1:
          return True
      return is_palindrome(string[1:-1])
  
  
  print(is_palindrome(input))

  • 글자가 1개만 남는다면 회문이라고 치는 것임!