73일차 TIL ( 면접 카타 6일 )

질문 : BigO에 대해 설명해주세요 

 

답 : Big-O 표기법은 알고리즘이 얼마나 빠르게 실행되는지 또는 얼마나 많은 메모리를 사용하는지를 나타냅니다.

 

주요 시간 복잡도(Big-O 종류)

• O(1) (상수 시간) → 입력 크기에 관계없이 실행 시간이 일정함 (예: 배열의 인덱스 접근)
• O(log N) (로그 시간) → 입력이 커질수록 실행 시간이 완만하게 증가 (예: 이진 탐색)
• O(N) (선형 시간) → 입력 크기만큼 실행 시간이 증가 (예: 단순 반복문)
• O(N²) (제곱 시간) → 중첩된 반복문이 있는 경우 (예: 버블 정렬)
• O(2^N) (지수 시간) → 재귀적 호출이 많아질 때 (예: 피보나치 재귀)

실무에서 Big-O가 중요한 이유

• 성능 최적화: 데이터가 많아질수록 효율적인 알고리즘 선택이 중요함.
• 시간 단축: 예를 들어, O(N²) 알고리즘을 O(N log N)으로 개선하면 속도가 크게 향상됨.
• 면접 대비: 알고리즘 문제를 풀 때 시간 복잡도를 고려하여 최적의 접근 방식을 선택해야 함.

 

추가 질문 대비

1. Big-O에서 O(1)과 O(log N)의 차이를 설명해보세요.
   → O(1)은 입력 크기와 관계없이 일정한 시간, O(log N)은 입력 크기가 커질수록 천천히 증가 (예: 이진 탐색).
2. O(N log N)이 나오는 대표적인 알고리즘은?
   → 퀵 정렬(Quick Sort)과 병합 정렬(Merge Sort).
3. 시간 복잡도 외에도 고려해야 할 요소는?
   → **공간 복잡도(Space Complexity)**도 고려해야 하며, 메모리 사용량이 중요한 경우 O(1)이나 O(log N)으로 최적화할 필요가 있음.

 

---

 

질문 :

1. 다음의 정렬을 설명하고 본인이 가장 편한 언어를 사용하여 로직을 구현해주세요
   • 선택 정렬(Selection Sort)
   • 버블 정렬(Bubble Sort)
   • 병합 정렬(Merge Sort)
   • 삽입 정렬(Insertion Sort)
   • 퀵 정렬(Quick Sort)
   • 힙 정렬(Heap Sort)

답: 

 

1. 선택 정렬 (Selection Sort)

개념:

• 배열에서 가장 작은(또는 큰) 요소를 찾아 정렬되지 않은 부분의 맨 앞 요소와 교환하는 방식.
• 단순하지만 비효율적이며, 작은 데이터에서만 유용함.

 시간 복잡도:

• O(N²) (모든 요소를 비교해야 함)
• O(1) (추가 메모리 거의 필요 없음)

function selectionSort(arr: number[]): number[] {
  const n = arr.length;
  for (let i = 0; i < n - 1; i++) {
    let minIdx = i;
    for (let j = i + 1; j < n; j++) {
      if (arr[j] < arr[minIdx]) {
        minIdx = j;
      }
    }
    [arr[i], arr[minIdx]] = [arr[minIdx], arr[i]]; // Swap
  }
  return arr;
}

 

 

---

2. 버블 정렬 (Bubble Sort)

 

개념:

• 인접한 두 요소를 비교하여 정렬되지 않은 요소를 점진적으로 정렬하는 방식.
• 데이터 크기가 커질수록 매우 비효율적.

시간 복잡도:

• 최악: O(N²)
• 최선 (이미 정렬된 경우): O(N) (개선된 버전에서 가능)

function bubbleSort(arr: number[]): number[] {
  const n = arr.length;
  let swapped: boolean;
  do {
    swapped = false;
    for (let i = 0; i < n - 1; i++) {
      if (arr[i] > arr[i + 1]) {
        [arr[i], arr[i + 1]] = [arr[i + 1], arr[i]]; // Swap
        swapped = true;
      }
    }
  } while (swapped);
  return arr;
}

 

---

3. 병합 정렬 (Merge Sort)

개념:

• 배열을 반으로 나눈 후, 각각을 정렬하고 합치는 방식(분할 정복).
• 안정적인 정렬이며, 큰 데이터에서도 효율적.

시간 복잡도:

• O(N log N) (모든 경우에서 일정)
• O(N) (추가적인 배열 공간 필요)

function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left: number[], right: number[]): number[] {
  let sortedArr: number[] = [];
  while (left.length && right.length) {
    sortedArr.push(left[0] < right[0] ? left.shift()! : right.shift()!);
  }
  return [...sortedArr, ...left, ...right];
}

---

4. 삽입 정렬 (Insertion Sort)

개념:

• 각 요소를 올바른 위치에 삽입하면서 정렬하는 방식.
• 거의 정렬된 데이터에서 매우 효율적.

시간 복잡도:

• 최악: O(N²)
• 최선 (거의 정렬된 경우): O(N)

function insertionSort(arr: number[]): number[] {
  for (let i = 1; i < arr.length; i++) {
    let key = arr[i];
    let j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j--;
    }
    arr[j + 1] = key;
  }
  return arr;
}

 

---

 

5. 퀵 정렬 (Quick Sort)

개념:

• 피벗(Pivot)을 선택해 작은 값은 왼쪽, 큰 값은 오른쪽으로 분할하는 방식(분할 정복).
• 일반적으로 가장 빠른 정렬 중 하나.

시간 복잡도:

• 평균: O(N log N)
• 최악 (이미 정렬된 경우): O(N²)

function quickSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;

  const pivot = arr[arr.length - 1];
  const left = arr.filter((el) => el < pivot);
  const right = arr.filter((el) => el > pivot);
  const middle = arr.filter((el) => el === pivot);

  return [...quickSort(left), ...middle, ...quickSort(right)];
}

 

---

 

6. 힙 정렬 (Heap Sort)

개념:

• 힙(Heap) 자료구조를 사용하여 정렬하는 방식.
• 우선순위 큐처럼 최대/최소 값을 빠르게 정렬하는 데 유용함.

시간 복잡도:

• O(N log N)
• 추가 메모리 사용이 적고, 안정적인 정렬이 아님.

function heapSort(arr: number[]): number[] {
  const heapify = (arr: number[], length: number, i: number) => {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;

    if (left < length && arr[left] > arr[largest]) largest = left;
    if (right < length && arr[right] > arr[largest]) largest = right;

    if (largest !== i) {
      [arr[i], arr[largest]] = [arr[largest], arr[i]];
      heapify(arr, length, largest);
    }
  };

  for (let i = Math.floor(arr.length / 2) - 1; i >= 0; i--) {
    heapify(arr, arr.length, i);
  }

  for (let i = arr.length - 1; i > 0; i--) {
    [arr[0], arr[i]] = [arr[i], arr[0]];
    heapify(arr, i, 0);
  }

  return arr;
}

 

---

면접에서 강조할 포인트

1. 정렬 알고리즘의 차이점
   • O(N²) → 선택/버블/삽입
   • O(N log N) → 병합/퀵/힙
   • 퀵 정렬은 보통 가장 빠르지만 최악의 경우 O(N²), 병합 정렬은 안정적이지만 O(N) 공간 필요.
2. 정렬 알고리즘 선택 기준
   • 데이터가 거의 정렬됨 → 삽입 정렬
   • 큰 데이터에서 빠른 정렬 → 퀵 정렬 / 병합 정렬
   • 안정적인 정렬이 필요 → 병합 정렬
   • 추가 메모리 사용이 적어야 함 → 힙 정렬