CS 박사되깅 9주차 자료구조 & 알고리즘 필수

배열 vs 연결 리스트

배열(Array)

• 같은 종류의 데이터를 연속된 공간에 저장하는 자료구조.
• 크기를 미리 정해야 하고, 인덱스를 통해 빠르게 원하는 데이터에 접근할 수 있다(O(1)).
• 하지만 중간에 데이터 삽입, 삭제가 느려(O(n)), 크기를 변경할 수 없다는 단점이 있다.

연결 리스트(Linked List)

• 노드라는 단위에 데이터와 다음 노드의 주소(포인터)를 저장해 서로 이어주는 구조.
• 메모리 공간 어디에든 노드를 추가할 수 있고, 중간 삽입/삭제가 빨라(O(1), 포인터 변경만 하면 됨), 크기도 자유롭게 늘릴 수 있음.
• 대신, 원하는 위치 데이터에 접근할 때는 첫 노드부터 순차적으로 찾아가야 해서 느림(O(n)).

	배열	연결 리스트
구조	연속된 메모리	비연속, 포인터로 연결
크기	고정	동적(필요시 추가)
접근 속도	빠름(O(1))	느림(O(n))
삽입/삭제	느림	빠름(특정 위치 기준)

아래 이미지를 보면 쉽게 이해가 됩니당

출처: C언어로 쉽게 풀어쓴 자료구조

---

스택, 큐, 힙

스택(Stack)

• 후입선출(LIFO: Last In First Out) 구조로, 나중에 넣은 데이터가 먼저 나옴.
• 한쪽 끝(Top)에서만 데이터 추가(push)와 제거(pop)가 가능함.
• 예시: 웹 브라우저 뒤로 가기, 함수 호출 스택.

큐(Queue)

• 선입선출(FIFO: First In First Out) 구조로, 먼저 넣은 데이터가 먼저 나옴.
• 한쪽(Rear)에서 추가(Enqueue), 반대쪽(Front)에서 제거(Dequeue).
• 예시: 줄 서기, 프린터 대기열.

힙(Heap)

• 완전 이진트리 형태로, “최댓값”이나 “최솟값”을 빠르게 찾기 위한 자료구조.
• 보통 두 가지가 있음: 최대 힙(Max-Heap, 부모>자식), 최소 힙(Min-Heap, 부모<자식).
• 우선순위 큐 구현에 활용됨.

---

정렬 알고리즘 (퀵, 병합, 힙 정렬)

퀵 정렬(Quick Sort)

• 기준 값(pivot)을 하나 뽑고,

• 그보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 분류(‘분할’),

• 각 그룹을 다시 퀵 정렬로 정렬(‘정복’), 이 과정을 재귀적으로 반복해 정렬을 완성.

• 빠르고 효율적이지만, 운에 따라(나쁜 pivot 선택) 느려질 수 있음.

  평균 수행 시간복잡도는 O(nlogn)이고, 최악의 경우 O(N²)까지 걸릴 수 있습니다.

// 퀵 정렬 (Quick Sort)
public class QuickSort {
    public static void quickSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int pivot = arr[(left + right) / 2];
        int l = left;
        int r = right;
        while (l <= r) {
            while (arr[l] < pivot) l++;
            while (arr[r] > pivot) r--;
            if (l <= r) {
                int temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
                l++;
                r--;
            }
        }
        quickSort(arr, left, r);
        quickSort(arr, l, right);
    }
}

병합 정렬(Merge Sort)

• 배열을 반씩 계속 쪼개서(분할),

• 크기가 1이 될 때까지 나눈 뒤,

• 다시 병합(merge)할 때 각 그룹을 정렬하며 합침.

• 항상 시간 복잡도가 일정하며, 다만 추가 메모리가 필요함.

  평균과 최악 모두 O(nlogn)의 시간복잡도를 가집니다.

// 병합 정렬 (Merge Sort)
public class MergeSort {
    public static void mergeSort(int[] arr, int left, int right) {
        if (left >= right) return;
        int mid = (left + right) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
    public static void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) temp[k++] = arr[i++];
            else temp[k++] = arr[j++];
        }
        while (i <= mid) temp[k++] = arr[i++];
        while (j <= right) temp[k++] = arr[j++];
        for (int t = 0; t < temp.length; t++) {
            arr[left + t] = temp[t];
        }
    }
}

힙 정렬(Heap Sort)

• 주어진 배열을 힙 구조(보통 최대 힙)로 만든 다음,

• 루트(최댓값/최솟값)를 꺼내 배열 맨 끝으로 옮김,

• 힙 크기를 줄이고 이 과정을 반복해 정렬을 완성.

• 힙을 사용해 정렬하기 때문에 ‘힙 상태’(부모가 자식보다 큼/작음)를 유지해야 함.

  평균과 최악 모두 O(nlogn)의 시간복잡도를 가집니다.

// 힙 정렬 (Heap Sort)
public class HeapSort {
    public static void heapSort(int[] arr) {
        int n = arr.length;
        // build heap
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);
        // extract elements
        for (int i = n - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            heapify(arr, i, 0);
        }
    }
    public static void heapify(int[] arr, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && arr[left] > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
}