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

최영진·2022년 11월 10일
0

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

profile
안녕하시오.

1개의 댓글

comment-user-thumbnail
2022년 11월 11일

우와 ㅎㅎ벌써 재귀까지...!

답글 달기