내일배움캠프 4기 React 9일차 (이진탐색, 재귀함수, 집합이용)

1. 이진탐색

• 업&다운 숫자 찾기 개념에서 list 를 정렬하여 중간 값을 기준으로 목표 값을 찾는 것
  - 반복문을 쓰지 않을 수 있어 시간복잡도에 유리할 수 있다.
  -
  라고 한다.

2. 재귀함수

• 어떤 것을 정의할 때 자신을 참조하는 함수
  - ex)

• while 문 처럼 무한반복에 빠지지 않게 빠져나가는 코드 필수!

• ex) 회문검사

input = "abcbcba"


def is_palindrome(string):
    x = len(string)
    for n in range(x):
        if string[n] != string[x - n -1]:
            return False
    return True


print(is_palindrome(input))

• 난 string 을 받아 문자열의 길이를 받고 for문을 돌려
  첫값과 끝값 그 다음값과 끝다음값을 비교하여 같지 않으면 false를 출력했다.
• ex) 재귀함수를 이용한 회문검사

input = "수박이박수"


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


print(is_palindrome(input))

• 재귀함수를 이용할때 list[:]를 이용하여 첫값 끝값을 비교한후 삭제 그 다음 값을 비교한 후 삭제 하는 식으로 list의 길이를 줄여 문자열의 길이가 1 이하 일때 True를 반환한다.
  어떻게 이렇게 생각할 수 있는지 신기하다.

• ex) list 의 숫자를 더하고 빼서 타겟팅 숫자와 같은 수 세기

  numbers = [2, 3, 1]
  target_number = 0
  result_count = 0
  def get_all_ways_to_by_doing_plus_or_minus(array, current_index, current_sum, all_ways):
     if current_index == len(array):
         if current_sum == target_number:
             global result_count
             result_count += 1
         return
     get_all_ways_to_by_doing_plus_or_minus(array, current_index + 1, current_sum + array[current_index], all_ways)
     get_all_ways_to_by_doing_plus_or_minus(array, current_index + 1, current_sum - array[current_index], all_ways)
  get_all_ways_to_by_doing_plus_or_minus(numbers, 0, 0, result_count)
  print(result_count)
  

• 이해하기 조차 어려웠지만 원래 어려운 문제였다.
  첫 재귀 되었을땐 + 로 조건 만족 후 -값으로 변경되어 똑같은 바퀴를 도는 것이다.
  이 문제는 처음 딱 보자마자 어떻게 하면 되겠다! 라고 알고리즘 적으로 이해는 했지만 어떤식으로 풀어내야 할지 이해하지 못했다.