WHAT WE TAGS DynamicProgramming LIST
최고 17kg의 무게를 저장할 수 있는 가방이 있다. 그리고 각각 3kg, 4kg, 7kg, 8kg, 9kg의 무게를 가진 5종류의 보석이 있다. 이 보석들의 가치는 각각 4, 5, 10, 11, 13이다. 이 보석을 가방에 담는데 17kg를 넘지 않으면서 최대의 가치가
실습과제 영훈이는 출근할 때 계단을 통해 사무실로 간다. 급할 때는 두 계단씩 올라가고 여유 있을 때는 한 계단씩 올라간다. 결국 계단을 오를 수 있는 모든 방법으로 계단을 올라갔다. 이제 다르게 계단을 올라갈 수는 없을까 고민하던 영훈이는 특이한 방법으로 계단을 오르려고 한다. 가령 계단을 한 번에 1, 2, 4
실습과제 영훈이는 출근할 때 계단을 통해 사무실로 간다. 급할 때는 두 계단씩 올라가고 여유 있을 때는 한 계단씩 올라 간다. 어느 날 문득, 호기심이 생겼다. 한 계단 또는 두 계단씩 올라가서 끝까지 올라가는 방법은 총 몇 가지가 있을까? 계단 4개를 올라간다고 가정하면, 이런 방법들이 있다. 1, 1, 1, 1
실습과제 태호는 주식 분석이 취미다. 요즘 제일 핫한 종목은 삼송전자인데, 삼송전자의 주식을 딱 한 번 사고 팔았다면 최대 얼마의 수익이 가능했을지 궁금하다. 그것을 계산해 주는 O(n) 함수 max_profit을 작성하라. max_profit은 파라미터로 일별 주식 가격이 들어 있는 리스트 stock_prices를 받고 최대 수익을 리턴한다. 주식은 딱 한 번만
실습과제 이미 sublist_max 함수를 각각 Brute Force과 Divide and Conquer 방식으로 작성했었다. Brute Force로 풀었을 때는 시간 복잡도가 O(n^2), Divide and Conquer 를 사용했을 때는 O(nlgn) 였다. 이번 과제에서는 시간 복잡도를 O(n) 로 한 번 더 단축하라! 나의 답 def sublist_max(profits): # 코드를 작성하세요. answer
실습과제 솔희는 학원 쉬는 시간에 친구들을 상대로 새꼼달꼼 장사를 한다. 그러다 문뜩, 갖고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익이 궁금해졌다... 가능한 최대 수익을 리턴시켜 주는 함수 max_profit_memo를 Tabulation 방식으로 작성해 보라. max_profit_memo는 파라미터 세 개를 받는다. price_list: 개수별 가격이 정리되어 있는 리스트 count: 판매할 새꼼달꼼 개수
실습과제 솔희는 학원 쉬는 시간에 친구들을 상대로 새꼼달꼼 장사를 한다. 그러다 문뜩, 갖고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익이 궁금해졌다... 가능한 최대 수익을 리턴시켜 주는 함수 max_profit_memo를 Memoization 방식으로 작성해 보라. max_profit_memo는 파라미터 세 개를 받는다. price_list: 개수별 가격이 정리되어 있는 리스트 count: 판매할 새꼼달꼼 개수
솔희는 학원 쉬는 시간에 친구들을 상대로 새꼼달꼼 장사를 한다. 그러다 문뜩, 갖고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익이 궁금해졌다... 가능한 최대 수익을 리턴시켜 주는 함수 max_profit을 작성해 보자. max_profit은 파라미터로 개수별 가격이 정리되어 있는 리스트 price_list와 판매할 새꼼달꼼 개수 count를 받는다. 예를 들어 price_list가 [100, 400, 800, 900,
실습과제 이전 장에서 본 것과 같이, n번째 피보나치 수를 계산하기 위해서는 가장 최근에 계산한 두 값만 알면 된다. 공간 복잡도 O(1)로 fib_optimized 함수를 작성하라. def fib_optimized(n): # 코드를 작성하세요. # 테스트 print(fib_optimized(16)) print(fib_optimized(53)) print(fib_optimized(213)) 987 53316291173 146178119651438213260386312206974243796773058 나의 답 def
피보나치 수열 문제를 Tabulation 방식으로 풀어 봤다. 이 방법을 사용하면 시간 복잡도가 O(n) 이고, 공간 복잡도도 O(n) 이다. Dynamic Programming 을 사용해서 훨씬 효율적인 코드가 되었다. 그런데 아직도 비효율이 좀 있다. fib(5) 를 계산하기 위해서는 fib(4) 와 fib(3) 만 알면 된다. 마찬가지로 fib(20) 을 계산하기 위해서는 fib(19)