분류 전체보기
-
[알고리즘] Greedy Algorithm : 최소 동전으로 거슬러 주기알고리즘 2023. 9. 29. 15:20
미래를 내다 보지 않고, 당장 눈앞에 보이는 최적의 선택을 하는 방식 장점 : 구현하기쉽고 빠르다. 단점 : 최적의 답이 보장되지 않는다. ** 그리디 알고리즘이 최적의 답을 보장해주는 문제도 있음(최적 부분 구조/탐욕적 선택 속성) 동전 거슬러주기 (최대한 적은 동전을 사용해서 돈 거슬러 주기) - 최적 부분 구조 존재 : 처음 100원 줄때/ 처음 50원 줄때... - 탐욕적 선택 속성 존재 : 매순간 마다 최대한 큰 동전을 거슬러 줄수 있음. 실습설명 최소 동전으로 돈을 거슬러 주는 함수를 Greedy Algorithm으로 구현해 보겠습니다. 우리가 작성할 함수 min_coin_count는 거슬러 줘야 하는 총액 value와 동전 리스트 coin_list를 파라미터로 받고, 거슬러 주기 위해 필요한..
-
[알고리즘] Dynamic Programming : 새꼼달꼼 장사(Tabulation)알고리즘 2023. 9. 29. 14:36
실습설명 솔희는 학원 쉬는 시간에 친구들을 상대로 새꼼달꼼 장사를 합니다. 그러다 문뜩, 갖고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익이 궁금해졌는데요. 가능한 최대 수익을 리턴시켜 주는 함수 max_profit를 작성해보세요. Tabulation방식으로 작성해보세요. max_profit는 파라미터 두개를 받습니다. - price_list: 개수별 가격이 정리되어 있는 리스트 - count : 판매할 새꼼달꼼 개수 예를 들어 price_list 가 [0, 100, 400, 800, 900, 1000]이라면, 1. 새꼼달꼼 0개에 0원 2. 새꼼달꼼 1개에 100원 3. 새꼼달꼼 2개에 400원 4. 새꼼달꼼 3개에 800원 5. 새꼼달꼼 4개에 900원 6. 새꼼달꼼 5개에 1000원 만약 솔희가 ..
-
[알고리즘] Dynamic Programming : 새꼼달꼼 장사분석(Memoization)알고리즘 2023. 9. 29. 14:25
실습설명 솔희는 학원 쉬는 시간에 친구들을 상대로 새꼼달꼼 장사를 합니다. 그러다 문뜩, 갖고 있는 새꼼달꼼으로 벌어들일 수 있는 최대 수익이 궁금해졌는데요. 가능한 최대 수익을 리턴시켜 주는 함수 max_profit_memo를 작성해보세요. Memoization방식으로 작성해보세요. max_profit_memo는 파라미터 세개를 받습니다. - price_list: 개수별 가격이 정리되어 있는 리스트 - count : 판매할 새꼼달꼼 개수 - cache : 개수별 최대 수익이 저장되어 있는 사전 예를 들어 price_list 가 [0, 100, 400, 800, 900, 1000]이라면, 1. 새꼼달꼼 0개에 0원 2. 새꼼달꼼 1개에 100원 3. 새꼼달꼼 2개에 400원 4. 새꼼달꼼 3개에 800원..
-
[알고리즘] Dynamic Programming 공간최적화 : 피보나치 수열알고리즘 2023. 9. 28. 23:29
Dynamic Programming을 할때, 모든 계산 값을 저장할 필요가 없다면 공간 사용을 최적화 한다. Tabulation은 모든 값을 리스트에 저장하고 있으므로 비효율적이다. r가장최근 값 current 직전 값 previous 을 활용한다.(사용하는 메모리는 늘어나지 않음) 실습설명 영상에서 보듯, 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_opt..
-
[알고리즘] Dynamic Programming : 피보나치 수열(Memoization vs Tabulation)알고리즘 2023. 9. 28. 22:50
다이나믹 프로그래밍 필요조건 1. 최적 부분구조 : 부분문제들의 최적의 답을 이용해서 기존문제의 최적의 답을 구할 수 있다는 것 -> 기존 문제를 부분 문제로 나눠서 풀수 있다. -> 중복되는 부분 문제들이 있을 수 있다. 2. 중복되는 부분 문제 다이나믹 프로그래밍 : 한 번 계산한 결과를 재활용 하는 방식 구현방법 1. Memoization : 중복되는 계산은 한 번만 계산 후 "메모" (Cache) / 재귀 실습설명 n번째 피보나치 수를 찾아주는 함수 fib_memo을 작성해 보세요. fib_memo는 꼭 memoization 방식으로 구현하여야 합니다. 힌트1 Memoization 방식으로 문제를 풀면 재귀 함수를 사용하는데, 제귀 함수를 작성할 때 가장 먼저 생각해야 하는 두가지가 무엇인지 기억..
-
[알고리즘] Divide and Conquer : 퀵 정렬 구현하기알고리즘 2023. 9. 28. 22:07
실습설명 Divide and Conquer 방식으로 quicksort 함수를 써보세요. quicksort 는 파라미터로 리스트 하나와 리스트 내에서 정렬시킬 범위를 나타내는 인덱스 start와 인덱스 end를 받습니다. merge_sort 함수와 달리 quicksort 함수는 정렬된 새로운 리스트를 리턴하는게 아니라, 파라미터로받는리스트 자체를 정렬시키는 것입니다. swap_elements와 partition 함수는 이전과제에서 작성한 그대로 사용하면 됩니다. 힌트1 Divide and Conquer로 문제를 풀기 위해서는 문제를 더 작은 부분 문제로 나누고, 재귀적으로 부분 문제들을 해결해야 하는데요. 재귀적으로 문제를 풀 때에는 늘 base case와 recursive case가 있어야 하죠? 그럼 ..
-
[알고리즘] 퀵정렬 : partition 함수 구현하기알고리즘 2023. 9. 28. 18:15
파티션 : 퀵정렬에서 리스트를 나누는 것 피벗 : 기준점 피벗을 기준으로 값을 새롭게 정렬한다. ex 피벗보다 작은값들을 왼쪽으로, 큰값을 오른쪽으로 1,Divede : 피벗을 설정한다. 2.Conquer : 피벗을 기준으로 정렬한다. 3.Combine : ..(할것 없음) 실습설명 partition함수 설명 영상을 토대로 partition 함수를 작성하세요. partition 함수는 리스트 my_list, 그리고 partition 할범위를 나타내는 인덱스 start 와 인덱스 end를파라미터로 받습니다. my_list의 값들을 pivot 기준으로 재배치한 후 , pivot의 최종 위치 인덱스를 리턴해야 합니다. 예시1 Pivot(기준점)은 마지막 인덱스에 있는 5. list1 = [4, 3, 6, 2,..
-
[알고리즘] Divide and Conquer 합병정렬 : merge 함수 작성알고리즘 2023. 9. 28. 17:36
실습 설명 Divide and Conquer 방식으로 merge_sort 함수를 써보세요. merge_sort는 파라미터로 리스트 하나를 받고, 정렬된 새로운 리스트를 리턴한다. merge함수는 이전과제에서 작성한 그대로 사용하면 된다. 답안 def merge(list1, list2): i = 0 j = 0 # 정렬된 항목들을 담을 리스트 merged_list = [] # list1과 list2를 돌면서 merged_list에 항목 정렬 while i list2[j]: merged_list.append(list2[j]) j += 1 else: merged_list.append(list1[i]) i += 1 # list2에..