Devlog

4.1 단원은 주어진 리스트에서 합을 최대로 갖는 부분 합을 찾는 방법에 대해 공부했다. 앞에서 했던 merge sort와 비슷하게 리스트를 반으로 나누어서 최대 값을 찾아주면 된다. 그러나 한가지 경우가 더 있는데, 리스트를 나누어준 중간 값을 지나는 부분 합이다. find_maximum_cross 라는 함수를 추가로 정의해서 그 합을 왼쪽 리스트의 부분합, 오른쪽 리스트의 부분합 이렇게 세 개의 합과 비교해서 가장 큰 부분합의 시작인덱스와 끝 인덱스를 반환한다. python으로 작성을 해보았는데 쓸데없이 길어보이는 부분이 있지만 너무 귀찮아서 책에 있는 수도코드를 참고했다.def find_maximum_sub(a, low_index, high_index): if low_index == high_ind..

1. merge sort 직접 구현하기def merge_sort(alist): div = int(len(alist)/2) if div > 0 : return merge(merge_sort(alist[:div]), merge_sort(alist[div:])) else : return alist def merge(alist,blist): merged_list = [] i=0 j=0 while(i list[div]: return binary_search(value,list[div:]) else: return binary_search(value,list[:div]) else: if value == list[0]: print("yes") else: print("no")파이썬으로 구현한 binary_search 이..

2.2-2 selection sort를 python으로 구현한 코드import random def selection_sort(A): for i in range(0,len(A)-1): min = A[i] min_index = i for j in range(i, len(A)): if A[j]