반응형
퀵정렬
-
알고리즘: 분할 정복(Divide And Conquer) 예제 공부하기! (합병 정렬, 퀵 정렬)알고리즘 2020. 7. 10. 17:39
분할 정복(Divide and conquer)이란? 어떤 문제를 해결하는 알고리즘에서 원래 문제를 성질이 똑같은 여러 개의 부분 문제로 나누어 해결하여 원래 문제의 해를 구하는 방식. 분할 정복은 다음과 같은 절차를 거친다. 1. Divide 2개 이상의 작은 문제들로 쪼갠다. 2. Conquer 나누어진 작은 문제들을 푼다. 3. Combine 나누어 해결한 문제들을 합친다. 1. 1부터 n까지의 합 (1 + 2 + 3 + ... + n) def consecutive_sum(start, end): if start == end: return start mid = (start + end) // 2 return consecutive_sum(start, mid) + consecutive_sum(mid + 1,..