(TIL) 20210608

📕Facts(한 것) 알고리즘 복습 운동하기 프로그래머스 문제 풀기 수업듣기 📕Findings(배운 것) 오늘은 퀵정렬과 다이나믹 프로그래밍에 대해서 복습했다. 퀵정렬의 partition과 sort 두 부분으로 나뉜다. (사실상 partition이 전부다) partition은 퀵정렬의 정수인데, 왼쪽에는 pivot보다 작은값을, 오른쪽에는 pivot보다 큰 값을 정렬해준다 그리고 pivot을 작은값과 큰 값 사이에 넣으면 완성이다. 이 partition 알고리즘을 재귀적으로 호출하면 결국 퀵정렬이 된다. 퀵정렬은 평균적으로 O(nlogn)의 시간복잡도를 보장하지만, 최악의 경우에는 O(N^2)의 시간복잡도를 가진다. 최악의 경우는 배열이 모두 같은 수로 이루어진 경우인데, 이를 보완하기 위해서 3-way..

2021.06.08