-

이전 포스팅한 연결 리스트의 확장 버전으로 https://devsalix.tistory.com/233 [기초] C++ Linked List (연결 리스트)연결 리스트(linked list)는 데이터 요소의 집합을 순차적으로 저장하는 선형 자료구조입니다.배열과 달리, 연결 리스트에서는 데이터 요소들이 메모리의 연속적인 위치에 저장되지 않고각 요소가devsalix.tistory.com 양방향 연결 리스트의 예제를 보여 드리겠습니다  #include // 노드 정의struct Node { int data; Node* prev; Node* next;};// 연결 리스트 클래스 정의class DoublyLinkedList {private: Node* head;public: DoublyL..

연결 리스트(linked list)는 데이터 요소의 집합을 순차적으로 저장하는 선형 자료구조입니다.배열과 달리, 연결 리스트에서는 데이터 요소들이 메모리의 연속적인 위치에 저장되지 않고각 요소가 포인터를 통해 다음 요소와 연결됩니다.이런 특성 때문에 연결 리스트는 동적인 메모리 관리에 적합하며,삽입과 삭제 연산을 배열에 비해 효율적으로 수행할 수 있습니다.  전체 코드#include // 연결 리스트의 노드를 정의합니다.struct Node { int data; Node* next; // 생성자를 사용하여 노드를 초기화합니다. Node(int val) : data(val), next(nullptr) {}};// 연결 리스트 클래스를 정의합니다.class LinkedList {..

계수정렬은 정수나 특정 범위의 정수를 정렬할 때 사용할 수 있는 매우 빠른 알고리즘입니다.이 방법은 비교를 하지 않고 정렬을 수행합니다.대신, 각 숫자가 몇 번 등장하는지 세어서 배열을 정렬합니다.그렇기 때문에, 계수정렬의 시간복잡도는 O(n + k)로 매우 효율적입니다.여기서 n은 리스트의 길이이고, k는 입력 값의 범위입니다.  #include void countingSort(int arr[], int n) { // 배열에서 최대값 찾기 int max_val = arr[0]; for (int i = 1; i max_val) { max_val = arr[i]; } } // 카운트 배열 초기화 int* count = new int[max_..

기수 정렬은 데이터를 개별적인 "자릿수"를 기준으로 여러 차례에 걸쳐 정렬하는 비교가 아닌 정렬 방식입니다.이 알고리즘은 숫자의 가장 낮은 자리수부터 시작하여 가장 높은 자릿수까지각 자릿수에 따라 순차적으로 정렬을 수행합니다.이 과정은 주로 카운팅 정렬을 이용하여 각 단계에서 진행됩니다. #include // 배열에서의 최대값을 찾는 함수int getMax(int arr[], int n) { int max = arr[0]; for (int i = 1; i max) max = arr[i]; return max;}// 기수 정렬을 위한 카운트 정렬 함수void countSort(int arr[], int n, int exp) { int output[n]; // 결과..

힙 정렬(Heap Sort)은 힙(heap) 자료구조를 기반으로 한 정렬 알고리즘입니다.이 알고리즘은 평균 및 최악의 경우에 모두 O(n log n)의 시간 복잡도를 가지며,제자리 정렬(in-place sorting) 알고리즘 중 하나입니다.힙 정렬은 주로 배열을 기반으로 작동하며, 추가적인 메모리 공간을 필요로 하지 않습니다.  일반적으로 다음과 같은 단계로 진행됩니다 주어진 배열을 최대 힙(Max Heap) 또는 최소 힙(Min Heap)으로 구성합니다.최대 힙(또는 최소 힙)에서 가장 큰(또는 가장 작은) 요소를 추출하여 배열의 가장 뒤에 배치합니다.배열에서 추출한 요소를 제외하고 다시 최대 힙(또는 최소 힙)을 유지합니다.모든 요소가 정렬될 때까지 위 과정을 반복합니다.#include // 힙 정..

퀵 정렬(Quick Sort)은 가장 널리 사용되는 정렬 알고리즘 중 하나입니다.이 알고리즘은 분할 정복(Divide and Conquer) 방법을 기반으로 합니다.기본 아이디어는 피벗(pivot) 요소를 선택하고 이를 기준으로 배열을 분할하고 정렬하는 것입니다.평균적으로 O(n log n)의 시간 복잡도를 가지며, 최악의 경우 O(n^2)입니다.일반적으로 다음과 같은 단계로 진행됩니다: 피벗 선택배열에서 피벗(pivot) 요소를 선택합니다. 일반적으로는 첫 번째 요소, 마지막 요소, 중간 요소 등이 선택됩니다.분할피벗을 기준으로 배열을 분할합니다.피벗보다 작은 요소는 피벗의 왼쪽에, 큰 요소는 오른쪽에 위치하도록 재배치합니다. 재귀적으로 정렬 분할된 두 하위 배열에 대해 재귀적으로 퀵 정렬을 수행합니다..

병합 정렬(Merge Sort)은 효율적인 정렬 알고리즘 중 하나로,분할 정복(divide and conquer) 방식을 이용합니다.이 알고리즘의 기본 원리는 큰 문제를 작은 문제로 나누어 해결한 후,그 해결된 결과들을 합쳐 전체 문제의 해답을 얻는 것입니다.  #include using namespace std;// 병합 함수void merge(int arr[], int const left, int const mid, int const right) { auto const subArrayOne = mid - left + 1; auto const subArrayTwo = right - mid; // 임시 배열 생성 int *leftArray = new int[subArrayOne], ..

삽입 정렬은 매우 직관적이고 구현이 간단한 정렬 알고리즘입니다.기본 원리는 이미 정렬된 배열의 부분에 새로운 원소를 그에 맞는 위치에 삽입하는 방식으로 진행됩니다.이 때문에 삽입 정렬은 거의 정렬된 데이터에 대해 매우 효율적입니다.최선의 경우 O(n)의 시간 복잡도를 보이며, 평균과 최악의 경우 O(n^2)입니다.  #include using namespace std;// 배열을 출력하는 함수void printArray(int arr[], int n) { for (int i = 0; i = 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; // key를 올바른 위치..

가장 작은 (혹은 가장 큰) 원소를 선택해 앞으로 옮기는 방식입니다.시간 복잡도는 O(n^2)으로 비효율적입니다.  #include // 배열을 출력하는 함수void printArray(int arr[], int size) { for (int i = 0; i  이 코드는 선택 정렬 알고리즘을 구현하고, 주어진 배열을 정렬한 뒤 결과를 출력합니다.코드를 실행하면 정렬되지 않은 배열이 정렬된 상태로 출력됩니다. 정렬 전 배열: 64 25 12 22 11 정렬 후 배열: 11 12 22 25 64 이 출력은 배열이 선택 정렬을 통해 어떻게 오름차순으로 정렬되는지 보여줍니다.코드의 'selectionSort' 함수에서 배열의 각 위치를 순회하면서 그 위치 이후의 최솟값을 찾고,그 최솟값을 현재 위치로 이동..

인접한 두 원소를 비교하며 정렬해 나가는 방식입니다.간단하나 비효율적인 경우가 많습니다.시간 복잡도는 O(n^2)입니다.   아래 코드는 버블 정렬을 사용하여 정수 배열을 정렬합니다.먼저 정렬 전과 후의 배열을 출력하고, 'bubbleSort' 함수를 사용하여 배열을 정렬합니다.결과적으로 정렬된 배열을 출력합니다. #include void printArray(int arr[], int size) { for (int i = 0; i arr[j+1]) { // 두 원소의 위치를 바꿈 int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; ..