수강 신청 분석 이번 학기 ♣♧대학교의 수업 리스트가 나왔습니다. [(4, 7), (2, 5), (1, 3), (8, 10), (5, 9), (2, 6), (13, 16), (9, 11), (1, 8)] 리스트에 담겨있는 튜플들은 각각 하나의 수업을 나타냅니다. 각 튜플의 0번째 항목은 해당 수업의 시작 교시, 그리고 1 번 항목은 해당 수업이 끝나는 교시입니다. 예를 들어서 0번 인덱스에 있는 튜플값은 (4, 7)이니까, 해당 수업은 4교시에 시작해서 7교시에 끝납니다. (2, 5)를 듣는다고 가정합니다. (4, 7) 수업은 (2, 5)가 끝나기 전에 시작하기 때문에, 두 수업은 같이 들을 수 없습니다. 반면, 수업 (1, 3)과 (4, 7)은 시간이 겹치지 않기 때문에 동시에 들을 수 있습니다. (단..

지각 벌금 적게 내기 익중이네 밴드부는 매주 수요일 오후 6시에 합주를 하는데요. 멤버들이 너무 상습적으로 늦어서, 1분에 1달러씩 내야 하는 벌금 제도를 도입했습니다. 그런데 마침 익중이와 친구 넷이 놀다가 또 지각할 위기입니다. 아직 악보도 출력해 놓지 않은 상황입니다. 어차피 같이 놀다 늦은 것이니 벌금을 다섯 명이서 똑같이 나눠 내기로 하고, 벌금을 가능한 적게 내는 방법을 고민해 보기로 합니다. 다섯 사람이 각각 출력해야 하는 페이지 수는 3장, 1장, 4장, 3장, 2장입니다. 프린터는 한 대밖에 없고, 1장을 출력하기 위해서는 1분이 걸립니다. 현재 순서대로 출력한다면, 첫 번째 사람: 33분 지각 두 번째 사람: 3 + 13+1분 지각 세 번째 사람: 3 + 1 + 43+1+4분 지각 네 ..

최대 곱 구하기 여럿이서 카드 게임을 하고 있는데, 각 플레이어는 3장의 카드를 들고 있습니다. 위의 경우 첫 번째 플레이어는 1, 2, 3을 들고 있고, 두 번째 플레이어는 4, 6, 1을 들고 있고, 세 번째 플레이어는 8, 2, 4를 들고 있습니다. 주의사항 * 함수 max_product는 한 사람당 카드를 하나씩 뽑아서 모두 곱했을 때 가능한 최대 곱을 리턴합니다. ❧ 테스트 셋 def max_product(card_lists): #Code #Test test_cards1 = [[1, 6, 5], [4, 2, 3]] print(max_product(test_cards1)) test_cards2 = [[9, 7, 8], [9, 2, 3], [9, 8, 1], [2, 8, 3], [1, 3, 6], ..

최소 동전으로 거슬러 주기 최소 동전으로 돈을 거슬러 주는 함수를 Greedy Algorithm으로 구현하시오. 주의사항 * 함수 min_coin_count는 거슬러 줘야 하는 총액 value와 동전 리스트 coin_list를 파라미터로 받고, 거슬러 주기 위해 필요한 최소 동전 개수를 리턴합니다. * 동전의 조합은 항상 500원, 100원, 50원, 10원이라고 가정합니다. ❧ 테스트 셋 def min_coin_count(value, coin_list): #Code #Test default_coin_list = [100, 500, 10, 50] print(min_coin_count(1440, default_coin_list)) print(min_coin_count(1700, default_coin_li..

합병 정렬 구현하기 솔희는 학원 쉬는 시간에 친구들을 상대로 새꼼달꼼 장사를 합니다. 그러다 문득, 갖고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익이 궁금해졌습니다. 가능한 최대 수익을 리턴시켜 주는 함수 max_profit을 Tabulation 방식으로 작성해 보세요. max_profit은 파라미터 두 개를 받습니다. - price_list: 개수별 가격이 정리되어 있는 리스트 - count: 판매할 새꼼달꼼 개수 ❧ 테스트 셋 def max_profit(price_list, count): # Code # Test print(max_profit([0, 200, 600, 900, 1200, 2000], 5)) print(max_profit([0, 300, 600, 700, 1100, 1400], 8)..

최대 수익(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..