5. [Algorithm 연습 Level 2] 출근하는 방법 II

실습과제 영훈이는 출근할 때 계단을 통해 사무실로 간다. 급할 때는 두 계단씩 올라가고 여유 있을 때는 한 계단씩 올라간다. 결국 계단을 오를 수 있는 모든 방법으로 계단을 올라갔다. 이제 다르게 계단을 올라갈 수는 없을까 고민하던 영훈이는 특이한 방법으로 계단을 오르려고 한다. 가령 계단을 한 번에 1, 2, 4

1. [Algorithm 연습 Level 2] 투자 귀재 규식이 II

실습과제 저번에 sublist_max 함수를 Brute Force 방식으로 작성했다. 이번에는 같은 문제를 Divide and Conquer 방식으로 풀어볼 것이다. 시간 복잡도는 O(n lg n) 이 되어야 한다. 이번 sublist_max 함수는 3개의 파라미터를 받는다. profits: 며칠 동안의 수익이 담겨 있는 리스트 start: 살펴볼 구간의 시작 인덱스 end: 살펴볼 구간의 끝

2. [Algorithm 연습 Level 1] 거듭 제곱 빠르게 계산하기

실습과제 거듭 제곱을 계산하는 함수 power를 작성하고 싶다. power는 파라미터로 자연수 x와 자연수 y를 받고, x^y를 리턴한다. 가장 쉽게 생각할 수 있는 방법은 반복문으로 단순하게 x를 y번 곱해 주는 방법이다. def power(x, y): total = 1 # x를 y번 곱해 준다 for i in range(y): total *=

14. [Divide and Conquer] 퀵 정렬 더 멋있게 구현하기

실습과제 이전 과제에서 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 파라미터를 넘겨줘야 한다는 게 조금 거슬린다. 테스트를

13. [Divide and Conquer] 퀵 정렬 구현하기

실습과제 Divide and Conquer 방식으로 quicksort 함수를 써 보라. quicksort는 파라미터로 리스트 하나와 리스트 내에서 정렬시킬 범위를 나타내는 인덱스 start와 인덱스 end를 받는다. merge_sort 함수와 달리 quicksort 함수는 정렬된 새로운 리스트를 리턴하는 게 아니라, 파라미터로 받는 리스트 자체를 정렬시키는 것이다. # 두 요소의 위치를 바꿔주는 helper function

12. [Divide and Conquer] partition 함수 구현하기

실습과제 partition 함수를 작성하시오. partition 함수는 리스트 my_list, 그리고 partition할 범위를 나타내는 인덱스 start와 인덱스 end를 파라미터로 받는다. my_list의 값들을 pivot 기준으로 재배치한 후, pivot의 최종 위치 인덱스를 리턴해야 한다. 예시 1 Pivot(기준점)은 마지막 인덱스에 있는 5. list1 = [4, 3, 6, 2, 7,

11. [Divide and Conquer] partition 함수 설명

퀵 정렬에서 가장 많은 노력이 들어가는 Divide 부분을 보겠다. 사실 Divide 부분이라고 하면 말했던 파티션 과정을 이야기하는 것이다. 위에 보이는 리스트를 파티션하려고 하면 마지막 부분을 피벗 즉, 기준점으로 잡고 이 기준점 보다 작은 값들은 모두 왼쪽에

10. [Divide and Conquer] 퀵 정렬 진행 과정

여덟 개 짜리 리스트가 있다. 퀵 정렬을 하려고 한다. 우선 Divide 단계에서 파티션을 해야 한다. 편하게 마지막에 있는 7 을 피벗으로 삼을 것이다. 그러면 7 보다 작은 값들은 다 왼쪽으로 오고, 7 보다 큰 값들은 다 오른쪽으로 오게끔

9. [Divide and Conquer] 퀵 정렬

Divide and Conquer 를 사용하는 또 다른 정렬 알고리즘이 있다. 바로 "퀵 정렬" 영어로는 "Quicksort" 이다. 퀵 정렬은 Divide 부분에서 대부분 일을 하고, Combine 부분은 하는 일이 없다. Divide 단계 퀵 정렬에서 리스트를 나누는 작업을 "파티션(Partition)" 이라고 부른다. 파티션에는 두 단계가 있다. 첫 번째 단계는 리스트에서 피벗(Pivot)

8. [Divide and Conquer] 합병 정렬 구현하기

실습과제 Divide and Conquer 방식으로 merge_sort 함수를 써 보자. merge_sort는 파라미터로 리스트 하나를 받고, 정렬된 새로운 리스트를 리턴한다. def merge(list1, list2): # 이전 과제에서 작성한 코드를 붙여 넣으세요! merged_list = [] P1 = 0 P2 = 0 while P1 < len(list1) and P2 < len(list2): if list1[P1] <