Algorithm 실기 기출 유형

🎯 유형 1: 코드 결과 예측

버블 정렬 문제

int main() {
    int arr[] = {5, 2, 8, 1, 9};
    int n = 5;
    
    for (int i = 0; i < 2; i++) {  // 2회전만
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
    
    // 배열 출력
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

풀이:

초기: [5, 2, 8, 1, 9]

1회전:
[2, 5, 8, 1, 9]
[2, 5, 1, 8, 9]
[2, 5, 1, 8, 9]
[2, 5, 1, 8, 9]
결과: [2, 5, 1, 8, 9] (9가 맨 뒤로)

2회전:
[2, 5, 1, 8, 9]
[2, 1, 5, 8, 9]
[2, 1, 5, 8, 9]
결과: [2, 1, 5, 8, 9] (8이 뒤에서 2번째로)

출력: 2 1 5 8 9

선택 정렬 문제

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = 5;
    
    for (int i = 0; i < 2; i++) {  // 2회전만
        int minIndex = i;
        
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
        
        printf("%d ", arr[i]);
    }
    
    return 0;
}

풀이:

초기: [64, 25, 12, 22, 11]

1회전:
최솟값 찾기: 11 (인덱스 4)
교환: [11, 25, 12, 22, 64]
출력: 11

2회전:
나머지 [25, 12, 22, 64]에서 최솟값 찾기: 12 (인덱스 2)
교환: [11, 12, 25, 22, 64]
출력: 12

출력: 11 12

삽입 정렬 문제

int main() {
    int arr[] = {5, 2, 4, 6, 1, 3};
    int n = 6;
    
    for (int i = 1; i <= 3; i++) {  // 3회전만
        int key = arr[i];
        int j = i - 1;
        
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        
        arr[j + 1] = key;
    }
    
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    
    return 0;
}

풀이:

초기: [5, 2, 4, 6, 1, 3]

i=1, key=2:
[2, 5, 4, 6, 1, 3]

i=2, key=4:
[2, 4, 5, 6, 1, 3]

i=3, key=6:
[2, 4, 5, 6, 1, 3] (변화 없음)

출력: 2 4 5 6 1 3

이진 탐색 문제

int binarySearch(int arr[], int n, int key) {
    int left = 0, right = n - 1;
    int count = 0;  // 비교 횟수
    
    while (left <= right) {
        int mid = (left + right) / 2;
        count++;
        
        if (arr[mid] == key) {
            return count;
        }
        
        if (arr[mid] < key) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return count;
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15};
    int result = binarySearch(arr, 8, 13);
    printf("%d", result);
    
    return 0;
}

풀이:

arr[] = {1, 3, 5, 7, 9, 11, 13, 15}
key = 13

1회: mid=3, arr[3]=7, 13>7 → left=4
2회: mid=6, arr[6]=13 → 찾음!

출력: 2

🎯 유형 2: 빈칸 채우기

버블 정렬

void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < ______; j++) {  // 빈칸 1
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = ______;              // 빈칸 2
                arr[j + 1] = temp;
            }
        }
    }
}

정답:

빈칸 1: n - 1 - i
빈칸 2: arr[j + 1]

선택 정렬

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIndex = ______;  // 빈칸 1
        
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = ______;  // 빈칸 2
            }
        }
        
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

정답:

빈칸 1: i
빈칸 2: j

삽입 정렬

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        
        while (j >= 0 && arr[j] ______ key) {  // 빈칸 1
            arr[j + 1] = arr[j];
            j______;  // 빈칸 2
        }
        
        arr[j + 1] = key;
    }
}

정답:

빈칸 1: >
빈칸 2: --

이진 탐색

int binarySearch(int arr[], int n, int key) {
    int left = 0;
    int right = ______;  // 빈칸 1
    
    while (left <= right) {
        int mid = (left + right) / 2;
        
        if (arr[mid] == key) {
            return mid;
        }
        
        if (arr[mid] < key) {
            left = ______;  // 빈칸 2
        } else {
            right = mid - 1;
        }
    }
    
    return -1;
}

정답:

빈칸 1: n - 1
빈칸 2: mid + 1

🎯 유형 3: 개념 서술

Q1: 버블 정렬의 동작 원리를 설명하시오.

답:

버블 정렬은 인접한 두 원소를 비교하여 
큰 값을 뒤로 보내는 정렬 알고리즘입니다.

동작:
1. 첫 번째부터 끝까지 인접 원소 비교
2. 큰 값을 뒤로 교환
3. 가장 큰 값이 맨 뒤로 이동
4. 이를 n-1회 반복

시간복잡도: O(N²)
장점: 구현이 간단, 안정 정렬
단점: 느린 속도

Q2: 선택 정렬과 버블 정렬의 차이점을 설명하시오.

답:

선택 정렬:
- 전체에서 최솟값을 찾아 맨 앞과 교환
- 교환 횟수: 최대 n-1번
- 불안정 정렬
- 이미 정렬되어도 모든 비교 수행

버블 정렬:
- 인접 원소를 비교하여 교환
- 교환 횟수: 최대 n(n-1)/2번
- 안정 정렬
- 최적화 시 이미 정렬된 경우 빠름

공통점:
- 둘 다 O(N²) 시간복잡도
- 추가 메모리 O(1)

Q3: 삽입 정렬이 효율적인 경우를 설명하시오.

답:

삽입 정렬이 효율적인 경우:

1. 이미 정렬된 배열:
   - 시간복잡도: O(N)
   - 각 원소마다 1번만 비교

2. 거의 정렬된 배열:
   - 이동 횟수가 적음
   - 다른 O(N²) 알고리즘보다 빠름

3. 작은 데이터셋 (n < 50):
   - 오버헤드가 적음
   - 구현이 간단

4. 온라인 알고리즘:
   - 데이터가 실시간으로 들어올 때
   - 즉시 정렬 가능

실무 활용:
- TimSort (Python, Java) 등의 
  하이브리드 정렬 알고리즘에서
  작은 부분 배열 정렬에 사용

Q4: 퀵 정렬의 최악의 경우와 해결 방법을 설명하시오.

답:

최악의 경우:

발생 상황:
- 이미 정렬된 배열
- 피벗이 항상 최솟값 또는 최댓값
- 한쪽으로만 분할

시간복잡도: O(N²)

해결 방법:

1. Median-of-Three:
   - 첫, 중간, 끝 원소 중 중앙값을 피벗으로
   - 최악 확률 감소

2. 무작위 피벗:
   - 피벗을 무작위로 선택
   - 평균 O(N log N) 보장

3. 3-Way 파티션:
   - 피벗과 같은 값들을 중간에 모음
   - 중복 값이 많을 때 효과적

4. Introsort:
   - 깊이가 깊어지면 힙 정렬로 전환
   - C++ STL sort()가 사용

Q5: 이진 탐색의 전제 조건과 시간복잡도를 설명하시오.

답:

전제 조건:
- 반드시 정렬된 배열
- 랜덤 액세스 가능 (배열)

동작 원리:
- 중간값과 비교
- 절반씩 범위를 줄임
- log₂N번 만에 탐색

시간복잡도: O(log N)

예시:
- 1,000,000개: 최대 20번 비교
- 선형 탐색: 최대 1,000,000번

장점:
- 매우 빠른 탐색
- 큰 데이터에 효율적

단점:
- 정렬 필요 (O(N log N))
- 삽입/삭제 시 정렬 유지 어려움

📝 핵심 암기 사항

정렬 알고리즘 요약

버블 정렬:
✔ 인접 원소 비교 교환
✔ O(N²), 안정 정렬
✔ 구현 간단, 실무 X

선택 정렬:
✔ 최솟값 선택 교환
✔ O(N²), 불안정 정렬
✔ 교환 횟수 적음

삽입 정렬:
✔ 정렬된 부분에 삽입
✔ O(N²), 최선 O(N)
✔ 거의 정렬된 경우 빠름

퀵 정렬:
✔ 피벗 기준 분할
✔ 평균 O(N log N)
✔ 실무에서 가장 많이 사용

시간복잡도 비교

정렬	최선	평균	최악
버블	O(N)	O(N²)	O(N²)
선택	O(N²)	O(N²)	O(N²)
삽입	O(N)	O(N²)	O(N²)
퀵	O(N log N)	O(N log N)	O(N²)

탐색 알고리즘

선형 탐색:
- 시간: O(N)
- 정렬 불필요
- 작은 데이터

이진 탐색:
- 시간: O(log N)
- 정렬 필수
- 큰 데이터 ✔

🎓 실기 시험 팁

1. 정렬 알고리즘 선택

문제에서 요구하는 것:
- "간단한 정렬" → 버블/선택
- "효율적인 정렬" → 퀵 정렬
- "안정 정렬" → 버블/삽입

2. 코드 추적

손으로 배열 상태를 그리면서 추적!

[5, 2, 8, 1]
↓ 1회전
[2, 5, 1, 8]
↓ 2회전
[2, 1, 5, 8]
...

3. 시간복잡도 계산

이중 for문 → O(N²)
while 절반씩 → O(log N)
재귀 분할 → O(log N)

4. 경계 조건

- 빈 배열: n = 0
- 단일 원소: n = 1
- 중복 값
- 이미 정렬됨