본문 바로가기

알고리즘6

정렬 - 합병정렬(Merge Sort) 합병정렬(Merge Sort)오늘은 마지막으로 알아볼 정렬인 합병정렬입니다. 합병정렬 또한 이전에 살펴 본 퀵정렬과 같은 분할 정복 방식을 채택한 알고리즘으로 결과적으로는 퀵정렬과 동일한 O(nlogn)의 시간복잡도를 가집니다. 하지만 여러 상황에 따라 퀵정렬과는 차이점이 존재하니 자세히 살펴봐야 합니다.#include using namespace std;// 두 개의 정렬된 부분 배열을 병합하는 함수void merge(int arr[], int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; int* leftArr = new int[n1]; int* rightArr = new int[n2].. 2025. 4. 4.
정렬 - 퀵정렬(Quick Sort) 퀵정렬(Quick Sort) 오늘은 퀵정렬에 대해 알아보겠습니다. 퀵정렬은 "대표적인 분할정복 알고리즘으로 평균속도가 O(nlogn)" 입니다.#include #include using namespace std;// 배열을 분할하는 함수int partition(vector& arr, int low, int high) { int pivot = arr[high]; // 피벗을 마지막 요소로 설정 int i = low - 1; // 작은 요소들의 인덱스 for (int j = low; j & arr, int low, int high) { if (low arr = {10, 3, 8, 9, 1, 5}; int n = arr.size(); cout  퀵정렬은 평균적으로 수행시간이 .. 2025. 3. 26.
정렬 - 삽입정렬(Insertion Sort) 삽입정렬(Insertion Sort) 오늘은 삽입정렬에 대해 알아보겠습니다. 삽입정렬은 "각 숫자를 적절한 위치에 삽입하는 방식하는 정렬 방법" 입니다. #include #include using namespace std;// 삽입 정렬 함수void insertionSort(vector& arr) { int n = arr.size(); for (int i = 1; i = 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; // key 삽입 }}// 배열 출력 함수void printArray(const vector& arr) { for (int num :.. 2025. 2. 24.
정렬 - 버블정렬(Bubble Sort) 버블정렬(Bubble Sort) 이전에 알아본 선택정렬 다음은 버블정렬입니다. 버블 정렬을 간단하게 요약하면 "옆에 있는 값과 비교하여 더 작은 값을 반복적으로 앞으로 보내는 정렬 방법" 입니다. #include using namespace std;void bubbleSort(int arr[], int n) { for (int i = 0; i arr[j + 1]) { swap(arr[j], arr[j + 1]); } } }}void printArray(int arr[], int n) { for (int i = 0; i  위 소스코드는 C++로 짜여진 1~10까지의 숫자를 오름차순으로 정렬시키는 버블정렬입니다. 위 소스코드에서 p.. 2025. 2. 7.
정렬 - 선택정렬(Selection Sort) 선택정렬(Selection Sort) 지금부터는 다양한 종류의 알고리즘에 대해서 알아보도록 할 것입니다. 알고리즘의 종류는 매우 다양하지만 그 중에서 가장 많이 알려져있는 정렬에 대해서 차근차근 알아보겠습니다. 정렬에는 종류가 다양한데 그 중 가장 기본적인 것은 선택정렬입니다. 1~10까지의 숫자가 무작위로 있을 때 오름차순으로 정렬하는 것을 예시로 많이 사용하여 각 알고리즘의 동작과정을 살펴보는 것이 보편적입니다. 선택정렬은 "가장 작은 것을 선택하여 앞으로 보내는 방법" 입니다. #include using namespace std;int main() { int arr[10] = {1, 10, 5, 8, 7, 6, 4, 3, 2, 9}; int n = 10, minIndex, temp; .. 2025. 1. 31.
알고리즘 - 알고리즘의 정의 알고리즘의 정의안녕하십니까. 알고리즘 카테고리를 만들어놓고 언젠가 정리해야지 하다가 이제야 건들게 되었습니다. 기초부터 차근차근 알고리즘에 대해서 정리할 예정입니다. 그럼 바로 시작하겠습니다. 컴퓨터 구조의 기초알고리즘을 이야기 하기 전에 컴퓨터 구조에 대한 기초적인 내용부터 정리하고 가도록 하겠습니다. 결국 우리가 알고리즘을 짜고 사용하는 이유는 컴퓨터와 밀접한 연관이 있기 때문입니다. 컴퓨터의 정의는 전자회로를 이용한 고속 자동 계산기로 3가지 주요한 구성요소 하드웨어, 소프트웨어, 데이터로 구성되어 있습니다. 컴퓨터에는 다양한 부품이 있지만, 그 중 우리에게 중요한 것은 저장소입니다. 옜날에는 하드디스크를 사용했지만, 요즘은 SSD를 많이 사용합니다. 그런데 하드디스크는 우리가 알고있는 포인터와 비.. 2025. 1. 25.

티스토리툴바