Jun's note

1. 퀵정렬 정의 임의로 pivot 잡은 후 pivot보다 작은 그룹을 왼쪽. 큰 그룹을 오른쪽으로 분할하여 해결한다. (분할 정복 방법) 분할 정복 방법 (divide-and-conquer) 큰 문제를 작은 문제 단위로 쪼개면서 해결한다. 문제를 2개의 문제로 분리하는데, 원소개수가 1개가 될 때까지 분리한다. 그 다음 작은 문제에서부터 결과를 모아 원래 문제를 해결한다. 멀리 있는 값들끼리 교환이 일어나므로 불안정한 정렬이다. 퀵정렬은 분할, 정복, 결합 단계로 이뤄진다. 분할(Divide): 피벗을 중심으로 피벗보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 분할한다. 정복(Conquer): 부분 배열을 정렬한다. 결합(Combine): 정렬된 부분 배열들을 하나의 배열로 합친다. 2. 퀵정렬 특징 ..

1. 삽입정렬 정의 자신보다 앞의 원소가 큰지 작은지 비교하여 자신의 위치를 찾아서 삽입하는 정렬 알고리즘이다. 왼쪽에는 이미 정렬된 부분, 오른쪽에는 정렬해야하는 부분으로 나눈 후 정렬한다. 두 번째 원소부터 시작하여 왼쪽에 있는 이미 정렬된 부분이랑 비교하여 삽입할 위치를 지정한 후, 삽입할 위치 뒤에 있는 원소들을 뒤로 옮겨 해당 위치에 원소를 삽입하는 알고리즘이다. (사진 출처: https://rninche01.tistory.com/entry/%EC%A0%95%EB%A0%AC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-01-%EC%82%BD%EC%9E%85-%EC%A0%95%EB%A0%AC) 2. 삽입정렬 특징 정렬하고자 하는 개수 크기가 작을수록 좋은 알고리즘 이미 정렬되..

이 분석은 “최악”의 경우에 대한 것이다. Amortized Analysis 정의 “최악의 경우에 대해 최악의 경우가 발생하도록 연속된 연산을 수행하고, 그때 한 번의 연산에 대한 평균수행시간을 분석하는 것” 이것이 왜 필요한가? 예를 들어, 비용을 1만큼 쓰는 연산이 있는데 이 연산은 가끔 n번 발생한다고 하면, Asymptotic analysis(점근적 분석)을 사용하면 이 연산은 O(n)이 된다. 하지만 가끔 일어나는 경우 때문에 O(n)이라고 하기에는 아깝다. 이를 보완하기 위해 나온 분석이 “Amortized Analysis”이다 다시 말하면 Amortized Analysis는 최악의 경우에 연속으로 발생하는 연산의 “평균비용”을 의미한다. (Array Doubling) n크기의 배열이 꽉 차 ..