[11.11] 내일배움캠프[Spring] TIL-10

[11.11] 내일배움캠프[Spring] TIL-10

1.파이썬 알고리즘

• 재귀함수 : 나를 계속해서 호출하는 함수
  👉 간결하고 효율적인 코드를 만들기 위해 사용!
  👉 함수안에서 함수를 호출하는 것... -> 근데 꼭!! 재귀함수를 쓸 때는 탈출 조건을 줘야함 꼭!!!

• 0~60까지 count 하는 재귀함수 예제

def count_down(number):

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


count_down(60)

• 팩토리얼 예제

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

    return n * factorial(n-1)


print(factorial(5))

• 회문 예제

input = "tomato"


def is_palindrome(string):

    if len(string) <= 1:
        True

    if string[0] != string[-1]:
        return False

    return is_palindrome(string[1:-1])

print(is_palindrome(input))

• 2주차 숙제 -1
  👉 링크드리스트 끝에서 K번째를 반환해라

• 내가 짠 코드( 튜터님 비슷 )

def get_kth_node_from_last(self, k):

        node = self.head
        tot_len = 0

        while node is not None:
            node = node.next
            tot_len+=1


        node = self.head
        for i in range(tot_len-k):
            node = node.next

        return node

• 2주차 숙제 -2
  👉 배달음식이 현재 주문가능한 상태인지 판별해라

shop_menus = ["만두", "떡볶이", "오뎅", "사이다", "콜라"]
shop_orders = ["오뎅", "콜라", "만두"]


def is_available_to_order(menus, orders):

    for order in orders:
        if order not in menus:
            return False

    return True



result = is_available_to_order(shop_menus, shop_orders)
print(result)

• 2주차 숙제 -3 ( 다시 볼 것!!! )
  👉 [2,3,1]로 타겟 숫자를 만들 수 있는 경우의 수를 구해라(재귀)

numbers = [2, 3, 1]
target_number = 0
result_count = 0  # target 을 달성할 수 있는 모든 방법의 수를 담기 위한 변수


def get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index, current_sum):
    if current_index == len(array):  # 탈출조건!
        if current_sum == target:
            global result_count
            result_count += 1  # 마지막 다다랐을 때 합계를 추가해주면 됩니다.
        return
    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1,
                                                       current_sum + array[current_index])
    get_count_of_ways_to_target_by_doing_plus_or_minus(array, target, current_index + 1,
                                                       current_sum - array[current_index])


get_count_of_ways_to_target_by_doing_plus_or_minus(numbers, target_number, 0, 0)
# current_index 와 current_sum 에 0, 0을 넣은 이유는 시작하는 총액이 0, 시작 인덱스도 0이니까 그렇습니다!
print(result_count)  # 2가 반환됩니다!

2. 자료구조

• Stack : First in Last out
• Queue : First in First out
• Hash : 블록체인 , Dict에 유용

• 버블정렬 : n , n+1 자료를 비교하면서 교환하면서 정렬하는 방식

• 버블정렬 예제

input = [4, 6, 2, 9, 1]


def bubble_sort(arrays):
    n = len(arrays)
    for i in range(n-1):
        for j in range(n-i-1):
            if arrays[j] > arrays[j+1]:
                arrays[j],arrays[j+1] = arrays[j+1],arrays[j]

    return arrays

result = bubble_sort(input)
print(result)  # [1, 2, 4, 6, 9] 가 되어야 합니다!