[algorithms] ch2. Divide-and-Conquer algorithms (multiplication, binary search, master theorem, merge sort)

(23.03.07)

algorithms  S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani (2008) 책 읽고 정리하기

http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf

 

정리한 내용

2.1 multiplication

2.2 recurrence relations

2.3 merge sort

---

 

Divide-and-Conquer algorithms

divide: 문제를 sub-problem 으로 쪼갠다.

conquer: cub-problem을 recuresively 하게 해결한다. 

combine: sub-problems의 solutions를 combine 한다. 

 

(+ 예전에 수업들으면서 정리했던 내용들:

https://hey-stranger.tistory.com/130

https://hey-stranger.tistory.com/131)

 

 

 

 

 

merge sort

 

 

merge sort pyhton code

def merge_sort(l):
  if len(l)<2:
    return l
  mid = len(l)//2
  left = merge_sort(l[:mid])
  right = merge_sort(l[mid:])
  return merge(left, right)


def merge(l, r):
  i, j = 0
  result = []
    
  while (i<len(l) & (j<len(r))):
    if l[i] < r[j]:
      result.append(l[i])
      i+=1
    else:
      result.append(r[i])
      j+=1
    
  while (i<len(l)):
    result.apped(l[i])
    i+=1
  
  while (j<len(r)):
    result.append(r[i])
    j+=1
  
  return result



# merge sort 실행
unsorted_list = [int(x) for x in input(x).spilt()]
sorted_list = merge_sort(unsorted_list)
print('unsorted_list: ' unsorted_list)
print('sorted_list: ' sorted_list)