최대 수익(Memoization) 솔희는 학원 쉬는 시간에 친구들을 상대로 새꼼달꼼 장사를 합니다. 그러다 문득, 갖고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익이 궁금해졌습니다. 가능한 최대 수익을 리턴시켜 주는 함수 max_profit_memo를 Memoization 방식으로 작성해 보세요. max_profit_memo는 파라미터 세 개를 받습니다. - price_list: 개수별 가격이 정리되어 있는 리스트 - count: 판매할 새꼼달꼼 개수 - cache: 개수별 최대 수익이 저장되어 있는 사전 ❧ 테스트 셋 def max_profit_memo(price_list, count, cache): # Code def max_profit(price_list, count): max_profit_cac..

피보나치 수열(최적화) 공간 복잡도 O(1)로 fib_optimized 함수를 작성하세요. ❧ 테스트 셋 def fib_optimized(n): # Code # Test print(fib_optimized(16)) print(fib_optimized(53)) print(fib_optimized(213)) ❧ 출력 예시 987 53316291173 146178119651438213260386312206974243796773058 ❧ 정답 def fib_optimized(n): current = 1 previous = 0 # update for i in range(1, n): current, previous = current + previous, current return current # Test prin..

합병 정렬 구현하기 n번째 피보나치 수를 찾아주는 함수 fib_tab을 tabulation 방식으로 구현해 보세요. ❧ 테스트 셋 def fib_tab(n): # Code # Test print(fib_tab(10)) print(fib_tab(56)) print(fib_tab(132)) ❧ 출력 예시 55 225851433717 1725375039079340637797070384 ❧ 정답 def fib_tab(n): fib_table = [0, 1, 1] for i in range(3, n + 1): fib_table.append(fib_table[i - 1] + fib_table[i - 2]) return fib_table[n] print(fib_tab(10)) print(fib_tab(56)) pri..

피보나치 수열(Memoization) n번째 피보나치 수를 찾아주는 함수 fib_memo를 memoization 방식으로 구현해 보세요. ❧ 테스트 셋 def fib_memo(n, cache): # Code def fib(n): # n번째 피보나치 수를 담는 사전 fib_cache = {} return fib_memo(n, fib_cache) # Test print(fib(10)) print(fib(50)) print(fib(100)) ❧ 출력 예시 55 12586269025 354224848179261915075 ❧ 정답 def fib_memo(n, cache): if n < 3: return 1 if n in cache: return cache[n] cache[n] = fib_memo(n - 1,ca..

퀵 정렬(3) 이전에 작성한 quicksort 함수를 파라미터 하나만을 이용해서 작성하시오. ❧ Before # Test test_list = [9, 5, 1, 5, 2, 8, 2, 7, 1, 3, 6, 2, 4, 7, 10, 11, 4, 6] quicksort(test_list, 0, len(test_list) - 1) print(test_list) ❧ After # Test test_list = [9, 5, 1, 5, 2, 8, 2, 7, 1, 3, 6, 2, 4, 7, 10, 11, 4, 6] quicksort(test_list) # start, end 파라미터 없이 호출 print(test_list) ❧ 정답 def swap_elements(my_list, index1, index2): tmp =..

퀵 정렬(2) Divide and Conquer 방식으로 quicksort 함수를 써 보세요. quicksort는 파라미터로 리스트 하나와 리스트 내에서 정렬시킬 범위를 나타내는 인덱스 start와 인덱스 end를 받습니다. merge_sort 함수와 달리 quicksort 함수는 정렬된 새로운 리스트를 리턴하는 게 아니라, 파라미터로 받는 리스트 자체를 정렬시키는 것입니다. ❧ 테스트 셋 def swap_elements(my_list, index1, index2): tmp = my_list[index1] my_list[index1] = my_list[index2] my_list[index2] = tmp return my_list # partition fuction def partition(my_list..

퀵 정렬(1) 퀵 정렬의 partition 함수를 작성하세요. partition 함수는 리스트 my_list, 그리고 partition할 범위를 나타내는 인덱스 start와 인덱스 end를 파라미터로 받습니다. my_list의 값들을 pivot 기준으로 재배치한 후, pivot의 최종 위치 인덱스를 리턴해야 합니다. ❧ 테스트 셋 # helper function def swap_elements(my_list, index1, index2): tmp = my_list[index1] my_list[index1] = my_list[index2] my_list[index2] = tmp return my_list # partition function def partition(my_list, start, end): ..

합병 정렬 구현하기 Divide and Conquer 방식으로 merge_sort 함수를 써 보세요. merge_sort는 파라미터로 리스트 하나를 받고, 정렬된 새로운 리스트를 리턴합니다. ❧ 테스트 셋 def merge(list1, list2): merge_list = [] i = 0 j = 0 while i < len(list1) and j < len(list2): if(list1[i] < list2[j]): merge_list.append(list1[i]) i+=1 else: merge_list.append(list2[j]) j+=1 if (i == len(list1)): return merge_list + list2[j:] else: return merge_list + list1[i:] retu..

합병 정렬 합병 정렬 알고리즘 중 사용되는 merge 함수를 작성하시오. 주의사항 * merge 함수는 정렬된 두 리스트 list1과 list2를 받아서, 하나의 정렬된 리스트를 리턴합니다. ❧ 테스트 셋 def merge(list1, list2): # Code # Test print(merge([1],[])) print(merge([],[1])) print(merge([2],[1])) print(merge([1, 2, 3, 4],[5, 6, 7, 8])) print(merge([5, 6, 7, 8],[1, 2, 3, 4])) print(merge([4, 7, 8, 9],[1, 3, 6, 10])) ❧ 출력 예시 [1] [1] [1, 2] [1, 2, 3, 4, 5, 6, 7, 8] [1, 2, 3, 4..