Devlog

문제 링크https://www.codewars.com/kata/pete-the-baker/train/python 내 답안def cakes(recipe, available): return min([available[x] // recipe[x] if x in available else 0 for x in recipe]) available에 key값이 없는 경우를 생각 안 해줘서 처음에 오류가 났었다. 그래서 if를 이용해서 키값이 있는지 찾고 없으면 0을 반환하도록 했는데 def cakes(recipe, available): return min(available.get(k, 0)//recipe[k] for k in recipe)위에 답처럼 딕셔너리의 get 함수를 써서 키값이 없으면 디폴트로 0을 반환하도록..

앞에서 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..

문제 링크https://www.codewars.com/kata/578aa45ee9fd15ff4600090d/train/python def sort_array(source_array): odd_num_idx = [] odd_num = [] for i,value in enumerate(source_array): if value%2==1 : odd_num_idx.append(i) odd_num.append(value) list.sort(odd_num) for i,value in enumerate(odd_num_idx): source_array[value] = odd_num[i] return source_array def sort_array2(arr): odds = sorted((x for x in arr if..

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