자료구조 예상문제 3 - 시간복잡도

1. 선택 정렬 (Selection Sort)

선택 정렬은 리스트에서 최솟값을 찾아 첫 번째 위치와 교환하는 방식으로 정렬하는 알고리즘입니다. 이 과정을 배열의 크기만큼 반복합니다.

#include <iostream>
using namespace std;

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        swap(arr[i], arr[minIdx]);
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    selectionSort(arr, n);
    
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

시간 복잡도:

• 최선, 평균, 최악: O(n²)
• 공간 복잡도: O(1) (추가 공간이 필요 없음

 

2. 버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 원소를 비교하여 자리를 바꾸는 방식으로 정렬을 진행합니다. 이 과정은 배열이 정렬될 때까지 반복됩니다.

#include <iostream>
using namespace std;

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
            }
        }
    }
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    bubbleSort(arr, n);
    
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

시간 복잡도:

• 최선: O(n) (배열이 이미 정렬되어 있을 때)
• 평균, 최악: O(n²)
• 공간 복잡도: O(1)

 

3. 퀵 정렬 (Quick Sort)

퀵 정렬은 분할 정복 방식을 사용하여 배열을 정렬합니다. 피벗을 선택하고 배열을 피벗을 기준으로 두 부분으로 나누어 각각 정렬하는 방식입니다.

#include <iostream>
using namespace std;

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; 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[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    quickSort(arr, 0, n - 1);
    
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

시간 복잡도:

• 최선, 평균: O(n log n)
• 최악: O(n²) (피벗을 최댓값이나 최솟값으로 선택했을 때)
• 공간 복잡도: O(log n) (재귀 호출에 의한 스택 공간)

4. 스택 (Stack) 기본 구현

스택은 후입선출(LIFO) 구조로, 가장 마지막에 들어온 요소가 가장 먼저 나옵니다. 스택은 배열이나 연결 리스트로 구현할 수 있습니다

#include <iostream>
using namespace std;

class Stack {
private:
    int* arr;
    int top;
    int capacity;

public:
    Stack(int size) {
        capacity = size;
        arr = new int[capacity];
        top = -1;
    }

    ~Stack() {
        delete[] arr;
    }

    bool isFull() {
        return top == capacity - 1;
    }

    bool isEmpty() {
        return top == -1;
    }

    void push(int value) {
        if (isFull()) {
            cout << "Stack Overflow!" << endl;
            return;
        }
        arr[++top] = value;
    }

    int pop() {
        if (isEmpty()) {
            cout << "Stack Underflow!" << endl;
            return -1;
        }
        return arr[top--];
    }

    int peek() {
        if (isEmpty()) {
            cout << "Stack is empty!" << endl;
            return -1;
        }
        return arr[top];
    }
};

int main() {
    Stack stack(5);
    stack.push(10);
    stack.push(20);
    stack.push(30);
    cout << "Top element: " << stack.peek() << endl;
    stack.pop();
    cout << "Top element after pop: " << stack.peek() << endl;

    return 0;
}

시간 복잡도:

• push: O(1)
• pop: O(1)
• peek: O(1)

 

 

5. 큐 (Queue) 기본 구현

큐는 선입선출(FIFO) 구조로, 먼저 들어온 요소가 먼저 나옵니다.

코드 (배열로 구현한 큐)

#include <iostream>
using namespace std;

class Queue {
private:
    int* arr;
    int front, rear;
    int capacity;

public:
    Queue(int size) {
        capacity = size;
        arr = new int[capacity];
        front = -1;
        rear = -1;
    }

    ~Queue() {
        delete[] arr;
    }

    bool isFull() {
        return (rear == capacity - 1);
    }

    bool isEmpty() {
        return (front == -1 || front > rear);
    }

    void enqueue(int value) {
        if (isFull()) {
            cout << "Queue Overflow!" << endl;
            return;
        }
        if (front == -1) {
            front = 0;
        }
        arr[++rear] = value;
    }

    int dequeue() {
        if (isEmpty()) {
            cout << "Queue Underflow!" << endl;
            return -1;
        }
        return arr[front++];
    }

    int peek() {
        if (isEmpty()) {
            cout << "Queue is empty!" << endl;
            return -1;
        }
        return arr[front];
    }
};

int main() {
    Queue q(5);
    q.enqueue(10);
    q.enqueue(20);
    q.enqueue(30);
    cout << "Front element: " << q.peek() << endl;
    q.dequeue();
    cout << "Front element after dequeue: " << q.peek() << endl;

    return 0;
}

시간 복잡도:

• enqueue: O(1)
• dequeue: O(1)
• peek: O(1)

 

6. 순환 함수 (Recursion) 시간 복잡도

순환 함수의 시간 복잡도는 주로 함수 호출이 얼마나 중첩되는지, 그리고 각 호출에서 하는 일에 따라 달라집니다.

#include <iostream>
using namespace std;

int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

int main() {
    cout << "Factorial of 5: " << factorial(5) << endl;
    return 0;
}

 

시간 복잡도:

• 팩토리얼 함수: O(n) (n번의 함수 호출)

 

 

 

7. 피보나치 수 (Fibonacci Sequence)

피보나치 수는 재귀적 방식으로 계산될 때 시간이 지수적으로 증가합니다

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) return n;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    cout << "Fibonacci of 10: " << fibonacci(10) << endl;
    return 0;
}

시간 복잡도:

• 피보나치 수 계산: O(2^n) (중복 계산이 많이 발생함)