algorithm16 합병 정렬 알고리즘(Merge Sort) ✔ 합병 정렬(Merge Sort) 합병 정렬은 퀵 정렬과 마찬가지로 분할 정복(divide and conquer) 방법을 통해 정렬하는 알고리즘이다. 정렬되지 않은 리스트를 각각 하나의 원소만 포함하는 n개의 부분리스트로 분할한다. (한 원소만 든 리스트는 정렬된 것) 분할한 부분리스트를 반복해서 비교하며 병합하여 정렬된 리스트로 만든다. 합병 정렬은 분할, 정복, 결합, 복사의 순으로 이루어진다. 분할(divide) : 정렬되지 않은 리스트를 절반으로 잘라 비슷한 크기의 두 부분 리스트로 나눈다. 리스트의 길이가 1 이하일 때까지 반복한다. 정복(conquer) : 각 부분 리스트를 재귀적으로 합병 정렬을 이용해 정렬한다. 결합(combine) : 두 부분 리스트를 다시 하나의 정렬된 리스트로 합병한.. 2023. 1. 10. 퀵 정렬 알고리즘(Quick Sort) ✔ 퀵 정렬(Quick Sort) 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 정렬하는 알고리즘이다. 간단히 얘기하면, 하나의 원소를 기준으로 기준 앞은 작은 모든 원소들이 오고, 뒤에는 큰 모든 원소들이 오도록 리스트를 둘로 분할하여 정렬하는 방법이다. 정렬하려는 리스트 가운데서 하나의 원소를 고른다. 고른 원소를 Pivot(피벗)이라 부른다. 피벗 기준 앞에서 큰 값을 찾고, 기준 뒤에는 작은 값을 찾아 교환하면서 피벗 앞에는 작은 원소들이 오게 하고 뒤에는 큰 원소들이 오도록 정렬을 진행한다. 분할 정복(divide and conquer) 그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 방법 ✔ 퀵 정렬 동작 과정 왼쪽 → 오른쪽 순으로 봐주시기 바랍니다.. 2022. 12. 14. 삽입 정렬 알고리즘(Insertion Sort) ✔ 삽입 정렬(Insertion Sort) 삽입 정렬은 적절한 위치에 삽입하여 정렬하는 알고리즘입니다. 삽입 정렬은 리스트의 두 번째 인덱스부터 시작해서 자기 기준의 왼쪽으로 비교하면서 정렬합니다. 또한, 자기 기준 왼쪽 부분은 정렬된 상태라 가정이 되기 때문에 적절한 위치를 파악할 수 있습니다. 예를 들면 [1, 2, 5, 4]인 리스트가 있을 때 현재 세 번째까지 정렬이 완료된 상태고 오름차순이라 가정하겠습니다. 네 번째와 자기 기준 왼쪽 값을 비교해서 자리를 변경하고, 다시 두 번째와 비교를 하지만 두 번째가 더 작기 때문에 변경이 발생하지 않습니다. 그리고 첫 번째는 이미 정렬된 상태여서 더 작은 값이기 때문에 아무 일도 일어나지 않습니다. 그래서 선택, 버블, 삽입 정렬 중에는 가장 적은 연산 .. 2022. 11. 30. 버블 정렬 알고리즘(Bubble Sort) ✔ 버블 정렬(Bubble Sort) 버블 정렬은 구현이 간단하지만 가장 비효율적인 알고리즘입니다. 버블 정렬은 바로 옆에 있는 두 원소를 비교하면서 정렬하는 알고리즘입니다. 오름차순일 경우, 두 원소를 비교해서 작은 값을 앞으로 보내고 큰 값을 뒤로 보내 가장 큰 값이 맨 뒤로 가면서 뒤에서부터 정렬이 완료되는 방법입니다. 내림차순일 경우, 두 원소를 비교해서 큰 값을 앞으로 보내고 작은 값을 뒤로 보내 정렬이 됩니다. ✔ 버블 정렬 동작 과정 왼쪽 → 오른쪽 순으로 봐주시기 바랍니다. 리스트의 첫 번째 인덱스를 교환(Swap) 대상으로 선정하고, 가장 가까운 두 번째 인덱스를 비교해서 교환 대상의 값이 더 크면 위치를 교환하고, 더 크지 않으면 넘어갑니다 리스트의 두 번째 인덱스를 교환(Swap) 대.. 2022. 11. 21. 선택 정렬 알고리즘(Selection Sort) ✔ 선택 정렬(Selection Sort) 선택 정렬은 가장 원시적이고 기초적인 방법 중 하나입니다. 선택 정렬은 이름 그대로 선택한 값을 제일 앞으로 보내서 정렬하는 알고리즘이다. 선택한 값이란 오름 차순일 경우 최솟값을 얘기하고, 내림 차순일 경우 최댓값을 얘기한다. ✔ 선택 정렬 동작 과정 리스트의 첫 번째 인덱스를 교환(Swap) 대상으로 선정하고, 교환 대상과 교환 대상 이후의 리스트를 전체 비교하면서 최솟값을 찾은 후 교환 대상과 최솟값의 위치를 교환(Swap) 첫 번째 인덱스는 정렬된 상태이기 때문에 고정. 두 번째 인덱스를 교환(Swap) 대상으로 선정하고, 첫 번째 인덱스를 제외한 전체 리스트를 비교하면서 최솟값을 찾은 후 교환 대상과 최솟값의 위치를 교환(Swap) 정렬이 완료될 때까지.. 2022. 11. 9. [Algorithm] 소수 구하기 ✔ 에라토스테네스의 체 수학에서 에라토스테네스의 체는 소수를 찾는 방법이다. 고대 그리스 수학자 에라토스테네스가 발견하였다. ✔ 알고리즘 에라토스테네스의 체 방식은 위와 같이 2부터 시작해 해당 배수의 값을 지워 나가면 된다. 에라토스테네스의 시간 복잡도는 O(nloglogn) 이다. 사실 O(nloglogn)이 어느 정도인지 모르겠다... 다만, O(n)인 선형 알고리즘보다 빠르다고 생각하고 있다. 배수의 값을 미리 지우기 때문이라고 생각한다.(DP 느낌? 👀) #include #include using namespace std; int main() { int n=120, cnt=0; vector v(n+1, 1); for(int i=2; i*i 2022. 4. 5. 이전 1 2 3 다음