개발머해니

실습 설명 거듭 제곱을 계산하는 함수 power()를 작성하고 싶습니다. power()는 파라미터로 자연수 x와 자연수 y를 받고, x 의 y승을 리턴합니다. 가장 쉽게 생각할 수 있는 방법은 반복문으로 단순하게 x를 y번 곱해 주는 방법입니다. def power(x, y): total = 1 # x를 y번 곱해 준다 for i in range(y): total *= x return total 이 알고리즘의 시간 복잡도는 O(y)인데요. O(lgy)로 더 빠르게 할 수는 없을까요? 실습 결과 def power(x, y): if y == 0: return 1 # 계산을 한 번만 하기 위해서 변수에 저장 subresult = power(x, y // 2) # 문제를 최대한 똑같은 크기의 문제 두 개로 나눠준..

실습 설명 규식이는 친구들 사이에서 투자의 귀재로 알려져 있습니다. 페이수북과 인수타그램에 자신의 성과를 과시하기 때문인데요. 사실 규식이가 그 정도의 실력자는 아닙니다. 성과가 좋을 때에만 SNS에 공유해서 그렇게 비춰질 뿐이죠. 계속해서 멋진 모습을 보여주기 위해, 특정 기간 중 수익이 가장 큰 구간을 찾아내는 함수 sublist_max()를 작성해 보려고 합니다. Brute Force 방법을 이용해서 이 문제를 한번 풀어 봅시다! 함수 설명 우선 함수 sublist_max()는 파라미터로 리스트 profits를 받는데요. profits에는 며칠 동안의 수익이 담겨 있습니다. 예를 들어서 profits가 [7, -3, 4, -8]이라면 첫 날에는 7달러를 벌었고, 둘째 날에는 3달러를 잃었고, 셋째 ..

실습 설명 이번 학기 코드잇 대학교의 수업 리스트가 나왔습니다. [(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분이 걸립니다. 현재 순서대로 출력한다면, 첫 번째 사람: 3분 지각 두 번째 사람: 3+1분 지각 세 번째 사람: 3+1+4분 지각 네 번째 사람: 3+1+4+3분 지각 다섯 ..

실습 설명 def max_product(card_lists): # 여기에 코드를 작성하세요 # 테스트 코드 test_cards = [[1, 2, 3], [4, 6, 1], [8, 2, 4], [3, 2, 5], [5, 2, 3], [3, 2, 1]] print(max_product(test_cards)) 여럿이서 카드 게임을 하고 있는데, 각 플레이어는 3장의 카드를 들고 있습니다. 위의 경우 첫 번째 플레이어는 1, 2, 3을 들고 있고, 두 번째 플레이어는 4, 6, 1을 들고 있고, 세 번째 플레이어는 8, 2, 4를 들고 있는 거죠. 함수 max_product는 한 사람당 카드를 하나씩 뽑아서 모두 곱했을 때 가능한 최대 곱을 리턴합니다. max_product를 Greedy Algorithm 방식..

실습 설명 최소 동전으로 돈을 거슬러 주는 함수를 Greedy Algorithm으로 구현해 보겠습니다. 우리가 작성할 함수 min_coin_count는 거슬러 줘야 하는 총액 value와 동전 리스트 coin_list를 파라미터로 받고, 거슬러 주기 위해 필요한 최소 동전 개수를 리턴합니다. 예를 들어 1170원을 거슬러 주기 위해서는 500원 2개, 100원 1개, 50원 1개, 10원 2개를 줄 수 있기 때문에 6을 리턴하면 되겠죠? 동전의 조합은 항상 500원, 100원, 50원, 10원이라고 가정합시다. 실습 결과 def min_coin_count(value, coin_list): # 누적 동전 개수 count = 0 # coin_list의 값들을 큰 순서대로 본다 for coin in sorte..

1. 수신(예금)이 없는 비은행 금융사들은 막대한 자금을 어디서 구할까? 2. 흔히 말하는 여전사(여신전문 금융회사)는 돈을 빌려주고 이자를 받는 회사라고만 알고 있었음 3. 근데 이때 사람들에게 빌려주는 돈을 어디서 구해오는가? 4. 이건 고민해본적이 없던 사실임 5. 알고보니 회사채나 기업어음으로 대출을 받아서 자금을 조달하는 것이라고 함 6. [여전사의 사업구조] 도매 : 회사 신용을 보증서로 은행에서 돈을 꿔옴(회사채) 소매 : 일반 고객들에게 돈을 빌려주고 이자를 받음(캐피탈,카드론,자동차할부) 7. 수익이 나려면 (소매로 얻는 이자) > (회사채로 내는 이자) 여야 함 8. 인터넷 쇼핑몰을 생각해보면, (동대문에서 옷을 사오는 가격) < (일반 소비자에게 판매하는 비용)보다 싸야하는 것처럼 당..

실습 설명 솔희는 학원 쉬는 시간에 친구들을 상대로 새꼼달꼼 장사를 합니다. 그러다 문뜩, 갖고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익이 궁금해졌는데요... 가능한 최대 수익을 리턴시켜 주는 함수 max_profit_memo를 Tabulation 방식으로 작성해 보세요. max_profit은 파라미터 두 개를 받습니다. price_list: 개수별 가격이 정리되어 있는 리스트 count: 판매할 새꼼달꼼 개수 예를 들어 price_list가 [100, 400, 800, 900, 1000]이라면, 새꼼달꼼 1개에 100원 새꼼달꼼 2개에 400원 새꼼달꼼 3개에 800원 새꼼달꼼 4개에 900원 새꼼달꼼 5개에 1000원 이렇게 가격이 책정된 건데요. 만약 오늘 솔희가 새꼼달꼼 5개를 판매한다면 최..

실습 설명 솔희는 학원 쉬는 시간에 친구들을 상대로 새꼼달꼼 장사를 합니다. 그러다 문뜩, 갖고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익이 궁금해졌는데요... 가능한 최대 수익을 리턴시켜 주는 함수 max_profit_memo를 Memoization 방식으로 작성해 보세요. max_profit_memo는 파라미터 세 개를 받습니다. price_list: 개수별 가격이 정리되어 있는 리스트 count: 판매할 새꼼달꼼 개수 cache: 개수별 최대 수익이 저장되어 있는 사전 예를 들어 price_list가 [100, 400, 800, 900, 1000]이라면, 새꼼달꼼 1개에 100원 새꼼달꼼 2개에 400원 새꼼달꼼 3개에 800원 새꼼달꼼 4개에 900원 새꼼달꼼 5개에 1000원 이렇게 가격이 ..

실습 설명 n번째 피보나치 수를 계산하기 위해서는 가장 최근에 계산한 두 값만 알면 됩니다. 공간 복잡도 O(1)로 fib_optimized 함수를 작성하세요. 실습 결과 def fib_optimized(n): current = 1 previous = 0 # 반복적으로 위 변수들을 업데이트한다. for i in range(1, n): print("%i : cur[%d], pre[%d]" %(i,current, previous)) current, previous = current + previous, current # n번재 피보나치 수를 리턴한다. return current # 테스트 코드 print(fib_optimized(16)) print(fib_optimized(53)) print(fib_opti..