실습 설명 Divide and Conquer 방식으로 quicksort 함수를 써 보세요. quicksort는 파라미터로 리스트 하나와 리스트 내에서 정렬시킬 범위를 나타내는 인덱스 start와 인덱스 end를 받습니다. merge_sort 함수와 달리 quicksort 함수는 정렬된 새로운 리스트를 리턴하는 게 아니라, 파라미터로 받는 리스트 자체를 정렬시키는 것입니다. swap_elements와 partition 함수는 이전과제에서 작성한 그대로 사용하면 됩니다! quick_sort.py # 두 요소의 위치를 바꿔주는 helper function def swap_elements(my_list, index1, index2): # 지난 실습의 코드를 여기에 붙여 넣으세요 my_list[index1], m..
실습 설명 Divide and Conquer 방식으로 merge_sort 함수를 써 보세요. merge_sort는 파라미터로 리스트 하나를 받고, 정렬된 새로운 리스트를 리턴합니다. merge 함수는 이전에서 작성한 그대로 사용하면 됩니다! merge_sort.py def merge(list1, list2): # 지난 실습의 코드를 여기에 붙여 넣으세요 merge_list = [] i = 0 j = 0 # list1과 list2를 돌면서 merge_list에 추가 while i list2[j]: merge_list.append(list2[j]) j += 1 else: merge_list.append(list1[i]) i ..
실습 설명 합병 정렬 알고리즘 중 사용되는 merge 함수를 작성해 보세요. merge 함수는 정렬된 두 리스트 list1과 list2를 받아서, 하나의 정렬된 리스트를 리턴합니다. merge.py def merge(list1, list2): # 여기에 코드를 작성하세요 merge_list = [] i = 0 j = 0 # list1과 list2를 돌면서 merge_list에 추가 while i list2[j]: merge_list.append(list2[j]) j += 1 else: merge_list.append(list1[i]) i += 1 if i == len(list1): merge_list += list2[j:..
Divide and Conquer를 이용해서 1부터 n까지 더하는 예시를 보았는데요. 코드로 한 번 구현해 봅시다. 우리가 작성할 함수 consecutive_sum은 두 개의 정수 인풋 start와 end를 받고, start부터 end까지의 합을 리턴합니다. end는 start보다 크다고 가정합니다. consecurive_sum.py def consecutive_sum(start, end): # 여기에 코드를 작성하세요 # base case if start == end: return start # 부분 문제를 반으로 나눠주기 위해서 문제의 정중앙을 정의한다.(Divide) mid = (start + end) // 2 # 각 부분을 재귀적으로 풀고(conquer), 부분문제의 답을 서로 더한다. retur..
실습 설명 런던에 엄청난 폭우가 쏟아진다고 가정합시다. 정말 재난 영화에서나 나올 법한 양의 비가 내려서, 고층 건물이 비에 잠길 정도입니다. 그렇게 되었을 때, 건물과 건물 사이에 얼마큼의 빗물이 담길 수 있는지 알고 싶은데요. 그것을 계산해 주는 함수 trapping_rain을 작성해 보려고 합니다. 함수 trapping_rain은 건물 높이 정보를 보관하는 리스트 buildings를 파라미터로 받고, 담기는 빗물의 총량을 리턴해 줍니다. 예를 들어서 파라미터 buildings로 [3, 0, 0, 2, 0, 4]가 들어왔다고 합시다. 그러면 0번 인덱스에 높이 33의 건물이, 3번 인덱스에 높이 22의 건물이, 5번 인덱스에 높이 44의 건물이 있다는 뜻입니다. 1번, 2번, 4번 인덱스에는 건물이 ..
실습 설명 스다벅스는 줄어든 매출 때문에 지점 하나를 닫아야 하는 위기에 처해 있습니다. 어떤 지점을 닫는 게 회사에 타격이 적을지 고민이 되는데요. 서로 가까이 붙어 있는 매장이 있으면, 그 중 하나는 없어져도 괜찮지 않을까 싶습니다. 사장님은 비서 태호에게, 직선 거리가 가장 가까운 두 매장을 찾아서 보고하라는 임무를 주셨습니다. 태호는 영업팀에서 매장들 좌표 위치를 튜플 리스트로 받아 왔습니다. # 예시 tuple 리스트 test_coordinates = [(2, 3), (12, 30), (40, 50), (5, 1), (12, 10), (3, 4)] 튜플은 각 매장의 위치를 x, y 좌표로 나타낸 것입니다. 0번 매장은 (2, 3)에, 그리고 1번 매장은 (12, 30) 위치에 있는 거죠. 태호가..
실습 설명 영상에서 보았던 문제를 코드로 풀어봅시다! 카드 두 뭉치가 있습니다. 왼쪽 뭉치에서 카드를 하나 뽑고 오른쪽 뭉치에서 카드를 하나 뽑아서, 두 수의 곱이 가장 크게 만들고 싶은데요. 어떻게 하면 가장 큰 곱을 구할 수 있을까요? 함수 max_product는 리스트 left_cards와 리스트 right_cards를 파라미터로 받습니다. left_cards는 왼쪽 카드 뭉치의 숫자들, right_cards는 오른쪽 카드 뭉치 숫자들이 담겨 있고, max_product는 left_cards에서 카드 하나와 right_cards에서 카드 하나를 뽑아서 곱했을 때 그 값이 최대가 되는 값을 리턴합니다. 내가쓴답.py def max_product(left_cards, right_cards): # 여기에..
type print(type([7, 5, 2, 3, 6])) # => print(type(5)) # => print(type(3.14)) # => print(type(True)) # => print(type("True")) # => type 함수를 사용하면 파라미터의 데이터 타입이 리턴됩니다. 시간 복잡도는 O(1)입니다. max, min print(max(2, 5)) # => 5 print(max(2, 7, 5)) # => 7 print(min(2, 5)) # => 2 print(min(2, 7, 5, 11, 6)) # => 2 max 함수를 사용하면 파라미터 중 가장 큰 값이 리턴되고, min 함수를 사용하면 파라미터 중 가장 작은 값이 리턴됩니다. 두 함수 모두 파라미터 개수가 유동적이기 때문에 원..
