일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- 코어뱅킹
- 개인프로필스튜디오창업
- 맥북셋팅
- 학점은행제
- 코딩테스트
- fastapi
- 은행IT
- SQL
- union
- MSA
- 맥북
- it자격증
- oracleapex
- 인강빨리듣기
- 컴퓨터공학학사취득
- 디렉토리계층구조
- 맥북환경설정
- python
- jdk
- 모놀리식
- 계정계
- jdk17
- 오라클
- 학점은행제무료강의
- 프로그래머스
- 렌탈스튜디오창업
- Pass By Value
- Homebrew
- DB
- 채널계
- Today
- Total
목록알고리즘 (43)
개발머해니
실습 설명 최소 동전으로 돈을 거슬러 주는 함수를 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..
실습 설명 솔희는 학원 쉬는 시간에 친구들을 상대로 새꼼달꼼 장사를 합니다. 그러다 문뜩, 갖고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익이 궁금해졌는데요... 가능한 최대 수익을 리턴시켜 주는 함수 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..
실습 설명 n번째 피보나치 수를 찾아주는 함수 fib_tab을 작성해 보세요. fib_tab는 꼭 tabulation 방식으로 구현하셔야 합니다! 실습 결과 def fib_tab(n): # 이미 계산된 fib 값들을 담는 리스트 fib_table = [0, 1, 1] # n번째 피보나치 수까지 리스트를 하나씩 채워 나간다 for i in range(3, n+1): #print("[%d] fib_table : %s" %(i,fib_table)) fib_table.append(fib_table[i-1]+fib_table[i-2]) return fib_table[n] # 테스트 코드 print(fib_tab(10)) print(fib_tab(56)) print(fib_tab(132)) #[3] fib_tabl..
실습 설명 n번째 피보나치 수를 찾아주는 함수 fib_memo을 작성해 보세요. fib_memo는 꼭 memoization 방식으로 구현하셔야 합니다! 실습 결과 # 캐시에 담긴 n번째 피보나치 수를 반환 def fib_memo(n, cache): #base case if n
실습 설명 이전 과제에서 quicksort 함수를 작성했습니다. # 테스트 코드 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) 그런데 quicksort 함수에 필수로 start와 end 파라미터를 넘겨줘야 한다는 게 조금 거슬리네요. 테스트를 할 때 만큼은 아래처럼 깔끔하게 작성하고 싶은데요. # 테스트 코드 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(..
실습 설명 Divide and Conquer 방식으로 quicksort 함수를 써 보세요. quicksort는 파라미터로 리스트 하나와 리스트 내에서 정렬시킬 범위를 나타내는 인덱스 start와 인덱스 end를 받습니다. merge_sort 함수와 달리 quicksort 함수는 정렬된 새로운 리스트를 리턴하는 게 아니라, 파라미터로 받는 리스트 자체를 정렬시키는 것입니다. 실습 결과 # 두 요소의 위치를 바꿔주는 helper function def swap_elements(my_list, index1, index2): temp = my_list[index1] my_list[index1] = my_list[index2] my_list[index2] = temp # 퀵 정렬에서 사용되는 partition 함..
실습 설명 partition 함수를 작성하세요. partition 함수는 리스트 my_list, 그리고 partition할 범위를 나타내는 인덱스 start와 인덱스 end를 파라미터로 받습니다. my_list의 값들을 pivot 기준으로 재배치한 후, pivot의 최종 위치 인덱스를 리턴해야 합니다. 예시 1 Pivot(기준점)은 마지막 인덱스에 있는 5. list1 = [4, 3, 6, 2, 7, 1, 5] pivot_index1 = partition(list1, 0, len(list1) - 1) print(list1) print(pivot_index1) [4, 3, 2, 1, 5, 6, 7] 4 5보다 작은 값들은 왼쪽에, 5보다 큰 값들은 오른쪽에 배치됩니다. 예시 2 Pivot(기준점)은 마지막..
실습 설명 Divide and Conquer 방식으로 merge_sort 함수를 써 보세요. merge_sort는 파라미터로 리스트 하나를 받고, 정렬된 새로운 리스트를 리턴합니다. 실습 결과 def merge_sort(my_list): # base case if len(my_list) < 2: return my_list # my_list를 반씩 나눈다(divide) left_half = my_list[:len(my_list)//2] # 왼쪽 반 right_half = my_list[len(my_list)//2:] # 오른쪽 반 # merge_sort 함수를 재귀적으로 호출하여 부분 문제 해결(conquer)하고, # merge 함수로 정렬된 두 리스트를 합쳐(combine)준다 return merge(..