목록Merge sort (2)

수학과의 좌충우돌 프로그래밍

[python] 파이썬의 정렬, Tim Sort

Tim Sort python에서의 정렬 함수 sorted()와 list.sort()에 사용된 정렬 알고리즘은 Timsort, 팀정렬입니다. 팀정렬은 파이썬 핵심 개발자인 팀 피터스에 의해서 Cpython에서 처음으로 구현되었으며 2009년 이후 표준 자바 및 안드로이드, swift 등 여러 언어에서 사용되고 있습니다. 이는 데이터의 정렬된 정도에 따라 삽입정렬과 병합정렬 사이를 전환하는 적응형 알고리즘입니다. 두 정렬방법을 결합했기에 안정적이며, 추가 메모리는 사용하지만 기존의 병합정렬에 비해 적은 추가메모리를 사용하여 다른 O(nlogn) 정렬 알고리즘의 단점을 최대한 극복한 알고리즘입니다. 알고리즘의 원리 위에서 언급했듯이 팀정렬은 삽입정렬과 병합정렬을 함께 사용하고 있습니다. 병합정렬은 추가적인 메..
프로그래밍 언어/Python 2020. 6. 3. 03:20
[Algorithm] Divide and Conquer, 분할 정복

Divide and Conquer Divide and Conquer 는 분할정복 알고리즘이라고도 하며, 문제를 2개 또는 그 이상의 작은 부분 문제로 나눠서 문제를 해결하는 알고리즘을 말합니다. 경우에 따라서는 푼 다음에 다시 부분 문제들을 합쳐서 정답을 구할 때도 있으며 퀵 정렬, 병합정렬, 큰수곱셈, FFT 등 여러 분야에서 분할정복 알고리즘을 이용하여 문제를 해결하고 있습니다. Divide and Conquer VS danamic programming 분할정복 알고리즘과 다이나믹 프로그래밍은 문제를 해결하는 핵심적인 전략이 동일합니다. 바로 문제를 작은 부분 문제로 나눠서 해결한다는 점입니다. 하지만 둘은 결정적인 차이가 존재하는데 바로 memorization 입니다. 다이나믹 프로그래밍은 작은 부..
알고리즘/이론 2019. 9. 20. 20:33
Prev 1 Next

티스토리툴바