def course_selection(course_list): # 여기에 코드를 작성하세요 # 최종으로 수업을 담을 수 있는 리스트 생성 early_time = [] # 수업을 끝나는 순서대로 정렬 sorted_list = sorted(course_list, key=lambda x: x[1]) # lambda x: 뒤에 인덱스 0, 1 조정 # 가장 먼저 끝나는 수업은 무조건 듣는다 early_time.append(sorted_list[0]) # 이미 선택한 수업과 선택을 안한 수업 중 가장 빨리 끝나는 수업을 고른다. for i in sorted_list: # 마지막 수업이 끝나기 전에 새 수업이 시작하면 겹친다. if i[0] > early_time[-1][1]: early_time.append(i)..
def min_fee(pages_to_print): # 여기에 코드를 작성하세요 fee = 0 min_list = [] for i in sorted(pages_to_print): fee += i min_list.append(fee) min_sum = 0 for j in min_list: min_sum += j return min_sum #########모범 답안######### def min_fee(pages_to_print): # 인풋으로 받은 리스트를 정렬시켜 준다 sorted_list = sorted(pages_to_print) # 총 벌금을 담을 변수 total_fee = 0 # 정렬된 리스트에서 총 벌금 계산 for i in range(len(sorted_list)): total_fee += s..
def max_product(card_lists): # 여기에 코드를 작성하세요 max_card = [] for i in card_lists: max_card.append(max(i)) max_num = max_card[0] for j in range(1, len(max_card)): max_num *= max_card[j] return max_num #########모범 답안######### def max_product(card_lists): # 누적된 곱을 저장하는 변수 product = 1 # 반복문을 돌면서 카드 뭉치를 하나씩 본다 for card_list in card_lists: # product에 각 뭉치의 최댓값을 곱해 준다 product *= max(card_list) return pro..
def min_coin_count(value, coin_list): # 누적 동전 개수 count = 0 # coin_list의 값들을 큰 순서대로 본다 for coin in sorted(coin_list, reverse=True): # 현재 동전으로 몇 개 거슬러 줄 수 있는지 확인한다 count += (value // coin) # 잔액을 계산한다 value %= coin return count # 테스트 코드 default_coin_list = [100, 500, 10, 50] print(min_coin_count(1440, default_coin_list)) print(min_coin_count(1700, default_coin_list)) print(min_coin_count(23520, def..
1. 최적 부분 구조, 중복되는 부분 문제, 탐욕적 선택 속성 없어도 Greedy Algorithm을 사용할 수 있다. 2. Greedy Algorithm을 사용해서 최적의 솔루션을 구하기 위한 필수조건 - 최적 부분 구조 / 탐욕적 선택 속성
실습 설명솔희는 학원 쉬는 시간에 친구들을 상대로 새꼼달꼼 장사를 합니다. 그러다 문뜩, 갖고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익이 궁금해졌는데요... 가능한 최대 수익을 리턴시켜 주는 함수 max_profit을 Tabulation 방식으로 작성해 보세요. max_profit은 파라미터 두 개를 받습니다.price_list: 개수별 가격이 정리되어 있는 리스트count: 판매할 새꼼달꼼 개수예를 들어 price_list가 [0, 100, 400, 800, 900, 1000]이라면,새꼼달꼼 0개에 0원새꼼달꼼 1개에 100원새꼼달꼼 2개에 400원새꼼달꼼 3개에 800원새꼼달꼼 4개에 900원새꼼달꼼 5개에 1000원이렇게 가격이 책정된 건데요. 만약 솔희가 새꼼달꼼 5개를 판매한다면 최대로 얼..
실습 설명솔희는 학원 쉬는 시간에 친구들을 상대로 새꼼달꼼 장사를 합니다. 그러다 문뜩, 갖고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익이 궁금해졌습니다. 가능한 최대 수익을 리턴시켜 주는 함수 max_profit_memo를 Memoization 방식으로 작성해 보세요. max_profit_memo는 파라미터 세 개를 받습니다.price_list: 개수별 가격이 정리되어 있는 리스트count: 판매할 새꼼달꼼 개수cache: 개수별 최대 수익이 저장되어 있는 사전예를 들어 price_list가 [0, 100, 400, 800, 900, 1000]이라면, 아래처럼 가격이 책정된 거예요.새꼼달꼼 0개에 0원새꼼달꼼 1개에 100원새꼼달꼼 2개에 400원새꼼달꼼 3개에 800원새꼼달꼼 4개에 900원새꼼달..
실습 설명공간최적화 관점으로 본다면, n번째 피보나치 수를 계산하기 위해서는 가장 최근에 계산한 두 값만 알면 됩니다. 공간 복잡도 O(1)로 fib_optimized 함수를 작성하세요.print(fib_optimized(1)) # 1을 출력 print(fib_optimized(2)) # 1을 출력 print(fib_optimized(3)) # 2을 출력 print(fib_optimized(4)) # 3을 출력 print(fib_optimized(5)) # 5을 출력 def fib_optimized(n): # 여기에 코드를 작성하세요 curent = 1 previous = 0 if n > 1: for i in range(1, n): temp = curent curent = curent + previous..
실습 설명n번째 피보나치 수를 찾아주는 함수 fib_tab을 작성해 보세요. fib_tab는 꼭 tabulation 방식으로 구현하셔야 합니다! - Tabulation(Table 방식으로 정리, 상향식 접근) def fib_tab(n): # 여기에 코드를 작성하세요 # tabulation fib_table = [0, 1, 1] if n > 2: for i in range(3, n+1): fib_sum = fib_table[i-1] + fib_table[i-2] fib_table.append(fib_sum) return fib_table[n] return fib_table[n] # 테스트 코드 print(fib_tab(10)) print(fib_tab(56)) print(fib_tab(132))해결과정 M..
실습 설명n번째 피보나치 수를 찾아주는 함수 fib_memo을 작성해 보세요. fib_memo는 꼭 memoization 방식으로 구현하셔야 합니다! - memoization(중복되는 계산은 한번만 계산 후 메모(재귀 함수 사용), 중복되는 부분 문제에 대한 비효율성 해결) def fib_memo(n, cache): # 여기에 코드를 작성하세요 # base case if n < 3: # 피보나치 수열의 첫 번째 수와 두번째 수는 1로 정해져있다. return 1 # recursive case if n in cache: # 이미 n번째 피보나치를 계산했으면 return cache[n] # 저장된 값 바로 리턴 # 아직 n번째 피보나치 수를 계산하지 않았다면 # 계산한 후 cache에 저장 cache[n] ..
