Yepchani's place

들어가며지난 시간에는 기본적인 정렬 알고리즘에 대해 알아봤는데요. 이번 시간에는 그보다 효율적인 정렬 알고리즘에 대해 알아보겠습니다. 병합 정렬(Merge sort)분할 정복 알고리즘의 대표적인 예로, 리스트를 반으로 나누어 정렬한 뒤 다시 병합하는 방식으로 동작합니다. 병합 정렬의 동작 과정은 다음과 같습니다.원소 개수가 1 또는 0이 될 때까지 리스트를 절반으로 나눕니다.각 부분 리스트를 정렬합니다.정렬된 두 부분 리스트를 병합합니다.      시간복잡도O(n log n) 공간복잡도O(n) 특징분할 정복 알고리즘안정 정렬추가적인 메모리 공간 필요병렬 처리에 적합대규모 데이터 처리에 효과적 힙 정렬(Heapsort)힙 자료구조를 활용하여 정렬을 수행하는 알고리즘입니다. 동작 과정은 다음과 같습니다.주어..

들어가며이번 시간에는 기본 정렬 알고리즘에는 어떤 것들이 있는지 알아보겠습니다.버블 정렬(Bubble sort)리스트의 첫 원소부터 시작해 인접한 두 원소를 비교하여 정렬하는 가장 단순한 알고리즘입니다.동작 과정은 다음과 같습니다.리스트의 첫 번째 원소부터 마지막 원소까지 인접한 두 원소를 비교합니다.앞의 원소가 뒤의 원소보다 크다면 두 원소의 위치를 서로 바꿉니다.이 과정을 리스트의 마지막 원소까지 반복합니다.이 과정을 리스트가 정렬될 때까지 반복합니다.  시간 복잡도O(n²)최선의 경우 O(n). 리스트가 이미 정렬되어 있는 경우 정렬을 한 번만 수행하면 됩니다. 공간 복잡도O(1) 특징안정 정렬제자리 정렬리스트가 이미 정렬되어 있는 경우 효율적거의 모든 상황에서 최악의 성능 정렬이 이루어지는 모습이..

들어가며 이번 시간에는 알고리즘 중 하나인 '그리디 알고리즘'에 대해 알아보려고 합니다. 소개 그리디(Greedy) 알고리즘, 또는 탐욕법 알고리즘은 매 순간에서 가장 최적의 선택을 통해 문제를 해결하는 방식입니다. 그리디라는 단어는 '탐욕적인'이라는 의미를 가지고 있죠. 이 알고리즘의 핵심은 각 단계에서 '현재 가장 좋은 선택'을 하는 것입니다. 주요 특징 그리디 알고리즘이 가지는 주요 특징은 다음과 같습니다. 탐욕적 선택 속성 알고리즘이 진행되는 동안, 각 단계에서 최적의 선택을 합니다. 이 선택은 이후의 선택 전략에 영향을 주지 않습니다. 최적 부분 구조 문제 전체에 대한 최적해(global optimum)가 부분 문제에 대해서도 최적해(local optimum)를 포함하고 있습니다. 접근 방법 그..