Devlog

앞에서 n^2 과 nlgn의 수행시간을 갖는 최대 부분합 탐색 알고리즘을 구현해 봤는데 이번에는 n 시간인 알고리즘을 구현해봤다. 이번에는 재귀로 분할을 하는 것도 아니고 모든 분할합들을 비교하지도 않는다. 작은 문제에서 시작해서 문제를 확장시켜 나간다. 책에 나온 힌트를 토대로 내가 구현해 본 코드는 아래와 같다.def maximum_sub(a): for i,value in enumerate(a): if(i==0): left_idx = 0 right_idx = 0 maximum_sum = value tail_maximum_sum = value tail_left_idx = 0 else: if tail_maximum_sum>0: tail_maximum_sum += value else: tail_maximu..

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 이..