자료구조 정복하기 1

정지인·2025년 6월 19일

📚 스택 (Stack)

스택(Stack)은 데이터를 효율적으로 관리할 수 있도록 돕는 자료 구조. 데이터를 넣고 빼는 방식에 독특한 특징이 있다.

특징: FILO (First In Last Out) 또는 LIFO (Last In First Out)

스택은 가장 먼저 들어온 데이터가 가장 마지막에 나가고, 가장 마지막에 들어온 데이터가 가장 먼저 나가는 선형 구조. FILO와 LIFO는 스택의 동작 방식을 설명하는 같은 의미의 용어.

💡 예시

  • Ctrl + Z (되돌리기): 가장 최근에 작업한 내용부터 순서대로 취소.
  • 햄버거 쌓기

스택 구현 방법

스택은 주로 두 가지 방식으로 구현.

  1. 정적 1차원 배열 (Static Array)
    • 장점: 구현이 간단.
    • 단점: 스택의 최대 크기를 미리 정해야 한다.
  2. 동적 연결 리스트 (Dynamic Linked List)
    • 장점: 스택의 크기가 유동적으로 변할 수 있어 미리 크기를 알 필요가 없다.
    • 단점: 배열보다 구현이 복잡하고, 메모리 사용량이 상대적으로 많을 수 있다.

스택의 주요 연산

스택에서 데이터를 다루기 위한 핵심 연산들이 있다.

  1. PUSH: 스택에 새로운 데이터를 추가하는 연산. 데이터는 항상 스택의 가장 위에 쌓인다.
  2. POP: 스택의 가장 위에 있는 데이터를 제거하는 연산. 데이터를 꺼냄과 동시에 스택에서 사라진다.
  3. Top / Peek: 스택의 가장 위에 있는 데이터를 확인하는 연산. 데이터는 스택에 그대로 남아있다.

⚡ 퀵 정렬 (Quick Sort)

퀵 정렬(Quick Sort)은 분할 정복 알고리즘을 기반으로 하는 효율적인 정렬 알고리즘. 특정 기준 값인 '피벗(Pivot)'을 중심으로 배열을 나눈 후, 각 부분을 재귀적으로 정렬하는 방식으로 동작.

퀵 정렬의 핵심 원리

  • 피벗 기준 분할: 배열을 피벗을 기준으로 두 개의 하위 배열로 분할. 하나는 피벗보다 작은 값들, 다른 하나는 피벗보다 큰 값들로 이루어진다.
  • 피벗 위치 확정: 분할 과정에서 피벗은 최종 정렬된 위치를 찾아가게 된다.
  • 성능과 피벗: 피벗을 어떻게 선택하느냐에 따라 퀵 정렬의 성능이 크게 달라질 수 있다.

퀵 정렬 C 코드 예시

#include <stdio.h>

// 두 원소의 값을 교환하는 함수
void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 배열을 분할하고 피벗의 최종 위치를 반환하는 함수
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 배열의 마지막 원소를 피벗으로 선택
    int i = (low - 1); // 작은 원소들의 경계를 추적하는 인덱스

    // 배열을 순회하며 피벗보다 작거나 같은 원소들을 왼쪽으로 이동
    for (int j = low; j <= high - 1; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    // 피벗을 올바른 위치로 이동
    swap(&arr[i + 1], &arr[high]);
    return (i + 1); // 피벗의 최종 위치 반환
}

// 퀵 정렬을 수행하는 재귀 함수
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // 배열을 피벗을 기준으로 분할하고 피벗의 위치를 얻음
        int pi = partition(arr, low, high);

        // 피벗을 기준으로 좌측과 우측 하위 배열을 재귀적으로 정렬
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 메인 함수
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("정렬 전 배열: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    quickSort(arr, 0, n - 1); // 퀵 정렬 수행

    printf("정렬 후 배열: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

퀵 정렬 요약

  1. 분할 정복: 퀵 정렬은 배열을 분할하고 각 부분을 정복(정렬)하는 방식으로 동작.
  2. 피벗 기준 재귀: 피벗을 정한 뒤, 피벗보다 작은 원소들은 왼쪽, 큰 원소들은 오른쪽으로 배치하고, 이 과정을 각 하위 배열에 대해 재귀적으로 반복.
  3. 다양한 피벗 선정: 피벗을 선택하는 방식(예: 첫 번째 원소, 중간 원소, 무작위 원소)에 따라 퀵 정렬의 성능에 영향을 미친다.
  4. 시간 복잡도:
  • 최악의 경우 (Worst Case): O(N2)O(N^2) (배열이 이미 정렬되어 있거나 역순으로 정렬되어 있고, 피벗 선택이 항상 가장 작거나 큰 원소가 될 때)
  • 평균의 경우 (Average Case): O(Nlog⁡N)O(N \log N)
  • 최선의 경우 (Best Case): O(Nlog⁡N)O(N \log N)

병합 정렬(Merge Sort)

  • 단순하지 않는 정렬 시리즈 중 제일 단순한 정렬
  • 분할 정복 알고리즘
  • 모든 숫자를 다 나눈 다음에 병합하는 방식으로 정렬을 진행

알고리즘 설명

1. 배열을 분할

배열을 중간 지점에서 두 개로 나눕니다.

2. 재귀적으로 정렬

각각의 하위 배열에 대해 병합 정렬을 재귀적으로 적용합니다.

3. 병합

두 정렬된 배열을 병합하여 하나의 정렬된 배열을 만듭니다.

코드 예시

#include <stdio.h>

// 병합 함수
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;  // 왼쪽 배열의 크기
    int n2 = r - m;      // 오른쪽 배열의 크기

    int L[n1], R[n2];

    // 왼쪽 배열과 오른쪽 배열에 데이터 복사
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // 두 배열을 병합하여 arr[l..r]에 저장
    int i = 0, j = 0, k = l;
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // L[] 배열에 남은 요소 복사
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // R[] 배열에 남은 요소 복사
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// 병합 정렬 함수
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // 중간 인덱스를 계산
        int m = l + (r - l) / 2;

        // 왼쪽과 오른쪽 배열을 재귀적으로 정렬
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        // 두 배열을 병합
        merge(arr, l, m, r);
    }
}

int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);

    // 주어진 배열 출력
    printf("주어진 배열: ");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");

    // 병합 정렬 함수 호출
    mergeSort(arr, 0, arr_size - 1);

    // 정렬된 배열 출력
    printf("정렬된 배열: ");
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    printf("\n");

    return 0;
}

코드 설명

mergeSort 함수

  • 배열을 재귀적으로 두 개로 나누고, 각 부분을 정렬한 후 merge 함수로 병합합니다.
  • l과 r은 배열의 시작과 끝 인덱스를 나타냅니다.

merge 함수

  • 두 개의 정렬된 배열을 하나의 배열로 병합하는 함수입니다.
  • L 배열은 왼쪽 부분 배열, R 배열은 오른쪽 부분 배열입니다.
  • 두 배열을 하나씩 비교하며 더 작은 값을 결과 배열에 삽입합니다.

시간 복잡도

  • 시간 복잡도: O(n log n)
  • 배열을 계속 나누기 때문에 log n 단계가 필요하고, 각 단계에서 배열의 모든 요소를 비교하므로 O(n)이 걸립니다.
  • 병합 정렬의 특징
    안정적인 정렬: 값이 같은 요소들의 순서를 변경하지 않습니다.
  • 분할 정복 알고리즘: 배열을 반복적으로 절반씩 나누어 정렬하고 병합합니다.
  • 최악의 경우에도 O(n log n): 최악의 경우에도 O(n log n) 시간 복잡도를 보장합니다.'

정리

이 알고리즘은 특히 큰 데이터 집합을 정렬할 때 유용하며, O(n log n)의 시간 복잡도를 가지므로 효율적입니다.

profile
정지인
멋쟁이사자 13기 백엔드
이전 포스트

8강

다음 포스트

자료구조 정복하기 2

0개의 댓글