Jun's note

1. 기수정렬 개념

1. 합병정렬 정의 분할 정복 알고리즘의 하나로, 더 이상 쪼개지지 않을때까지 작은 크기로 분할하여, 작은 배열끼리 비교하는 과정을 수행해 하나의 배열로 합치는 정렬이다. 과정 1. 원래 배열을 두 개의 작은 배열로 분할하여 더 이상 쪼개지지 않을 때까지 재귀적으로 수행한다. 2. 가장 작은 크기의 배열부터 시작하여, 두 개의 배열을 서로 비교하면서 오름차순(또는 내림차순)으로 정렬해 합친다. 합병정렬 예제 2. 합병정렬 특징 - 장점 안정적인 정렬 방법 (입력한 값이 무엇이든 간에 정렬되는 시간은 O(nlog2n)으로 동일하다) - 단점 배열 크기가 큰 경우에는 이동횟수가 많아 시간적 측면에서 크게 낭비된다. 3. 시간 복잡도 - Best Case O(nlog2n) - Worst Case O(nlog2..

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크기의 배열이 꽉 차 ..