4주차 질문 목록

[blcklamb]

• 일시: 2월 8일 (목) 22시
• 범위:
• 각자 질문한 것을 comment로 달아주세요.

[blcklamb]

Heap sort 의 TC SC

[blcklamb]

LCA Union find

[freemjstudio]

Q. 버블 정렬과 선택 정렬의 차이점 ?

버블 정렬은 서로 인접한 두 원소를 비교하여 정렬하는 알고리즘이다. 0번 인덱스부터 n-1번 인덱스까지 모든 인덱스를 비교하며 정렬한다. 선택 정렬은 배열 전체를 검사하여 최솟값(혹은 최댓값)을 찾아서 그 요소를 현재 위치에 배치한다. 정렬된 부분을 제외한 나머지에 대해 같은 과정을 반복한다. 일반적으로 선택 정렬이 버블 정렬보다 더 적은 교환 횟수를 가지게 된다. 또한 버블 정렬은 안정 정렬, 선택 정렬은 불안정 정렬에 해당한다.

• 안정 정렬 : 중복된 값이 입력 순서와 동일하게 정렬되는 경우
• 불안정 정렬 : 중복된 값이 입력 순서와 동일하게 정렬되지 않는 경우

Q. 병합 정렬(Merge Sort)에 대해 설명해주세요

데이터를 크기가 1이 될때까지 절반으로 나누는 작업을 하고, 데이터 크기가 1인 배열이 된다면 그 이후로 부터 합병을 진행하는 알고리즘입니다. 합병 작업에서 값을 비교해서 정렬이 일어납니다. 값 비교에는 N 만큼이 소요되고 이 비교 과정이 logN 만큼 반복됩니다.

• 시간 복잡도 O(NlogN)
• 공간 복잡도 O(2N)

Q .BFS가 DFS에 비해서 최단경로를 찾는데 유리한 이유

DFS의 경우, 루트 노드에서 시작하여 다음 분기로 넘어가기 전 해당 분기를 모두 탐색하는 방식이므로 처음으로 발견되는 경로가 최단거리가 아닐 수 있다. 하지만 BFS의 경우 현재 노드에서 가까운 노드부터 탐색하기 때문에 먼저 찾아지는 경로가 최단거리가 된다.

[maintain0404]

1. 삽입 정렬과 선택 정렬의 차이점을 설명해주세요.
2. 최소 공통 조상(LCA)을 찾는 알고리즘에 대해 설명해주세요.
3. 이분 탐색이 무엇인지 설명하고, 사용할 수 있는 조건을 설명해주세요.

[blcklamb]

Q. Quick Sort에 대해서 아는대로 설명해 주세요.

Quick sort는 분할 정복 알고리즘 중 하나입니다. 리스트 가운데서 하나의 원소를 고르고, 해당 원소를 피벗으로 설정합니다. 피벗 앞에는 피벗보다 작은 모든 원소들이, 뒤에는 피벗보다 큰 모든 원소들이 오도록 리스트를 둘로 나눕니다. 이러한 분할 작업 이후에는 피벗을 고정시켜 놓고, 두 분할된 리스트에 대해 재귀적으로 이 과정을 반복합니다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복합니다.

function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return quickSort(left).concat(pivot, quickSort(right));
}

def quickSort(arr):
  if len(arr) <= 1:
    return arr

  pivot = arr[0]
  left = [x for x in arr[1:] if x < pivot]
  right = [x for x in arr[1:] if x >= pivot]

  return quickSort(left) + [pivot] + quickSort(right)

Quick sort의 시간복잡도는 최선과 평균의 경우 O(N*logN)이며, 최악의 경우 O(N^2)가 될 수 있습니다. 공간복잡도는 최선과 평균의 경우 O(logN)이며, 최악의 경우 O(N)가 될 수 있습니다.

Quick sort는 평균적으로 매우 빠르며 제자리 정렬이라는 특징을 가지고 있습니다. 하지만 불안정 정렬이라는 단점을 가지고 있습니다.

Algorithms — Quick Sort - Medium

Quick sort가 최악의 시간 복잡도를 가지는 경우 해결방안은 무엇인가요?

Quick sort는 피벗 선택이 최악의 경우, 리스트가 이미 정렬되어 있거나 피벗이 항상 최대 또는 최소값을 선택하는 경우 최악의 시간 복잡도를 가질 수 있습니다. 이런 경우 피벗을 무작위로 선택하거나 리스트 내의 중간값을 선택하는 방법을 통해 최악의 경우를 피할 수 있습니다.

Q. Heap Sort에 대해서 아는대로 설명해 주세요.

Heap sort는 Heap 자료구조를 기반으로 하는 정렬 알고리즘입니다. Heap은 완전 이진 트리로 구성되며 최대 힙 또는 최소 힙의 성질을 가집니다. 최대 힙을 사용하는 경우를 기준으로 힙 정렬 알고리즘에 대해 설명하겠습니다. 최대 힙을 생성한 후 루트 노드와 배열의 마지막 노드를 교환합니다. 힙의 크기를 1 감소시킨 다음 루트 노드에 대해 heapify를 재귀 호출하여 전체 트리를 최대 힙으로 만듭니다. 이 과정을 힙의 크기가 1이 될 때까지 반복합니다. 이 과정을 반복하면 정렬된 배열을 만들 수 있습니다.

function heapify(arr, n, i) {
  let largest = i;

  const left = 2 * i + 1;
  const right = 2 * i + 2;

  if (left < n && arr[largest] < arr[left]) {
    largest = left;
  }
  if (right < n && arr[largest] < arr[right]) {
    largest = right;
  }

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

function heapSort(arr) {
  const n = arr.length;

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

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

  return arr;
}

def heapify(arr, n, i):
  largest = i

  left = 2 * i + 1
  right = 2 * i + 2

  if left < n and arr[largest] < arr[left]:
    largest = left
  if right < n and arr[largest] < arr[right]:
    largest = right

  if i != largest:
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, n, largest)

  return arr

def heapSort(arr):
  n = len(arr)

  for i in range(n // 2 - 1, -1, -1):
    heapify(arr, n, i)

  for i in range(n - 1, 0, -1):
    arr[0], arr[i] = arr[i], arr[0]
    heapify(arr, i, 0)

  return arr

Heap sort는 항상 O(N*logN)의 시간 복잡도를 가집니다. 힙 생성 단계에서 O(N), 각 heapify 단계에서 O(logN)의 시간이 소요되기 때문입니다. 힙 정렬은 추가적인 메모리 공간이 필요하지 않고 주어진 배열 자체에서 정렬을 수행하므로 공간 복잡도는 O(1)입니다. (이 부분은 조금 더 보충해서 올리겠습니다!)

Heap sort는 배열 자체에서 정렬을 수행하는 제자리 정렬이고 추가적인 메모리를 사용하지 않기 때문에 공간 복잡도가 낮은 특성을 가집니다. 다만 숫자가 같은 경우에도 교환 및 heapify가 수행될 수 있기 때문에 Quick sort와 함께 불안정 정렬에 해당됩니다.

자료구조 개념 이해하기 '힙과 힙 정렬 알고리즘' - 요즘 IT [곰씨네 IT 블로그]

Q. Radix Sort에 대해서 아는대로 설명해 주세요.

비교 정렬은 수학적인 한계로 최선의 시간복잡도가 O(N*logN)보다 개선될 수 없습니다. 그래서 비교하지 않고 수의 특성을 이용해 sort를 하는 것으로 시간복잡도를 개선시킬 수 있습니다.

Radix sort는 일의 자리부터 시작해 각 자릿수 별로 정렬한 결과를 0-9까지의 버킷에 담는 그룹화를 진행합니다. 목록으로 다시 구성할 때에는 버킷에 이미 있는 순서대로 두는 것을 최대 수의 자릿 수만큼까지 반복합니다. 자릿수를 선택하는 기준은 가장 큰 자릿수부터 그룹화하는 Most Significant Digit과 가장 작은 자릿수부터 그룹화하는 Least Significant Digit이 있습니다.

Radix sort는 k가 수의 자릿수일 때항상 O(N*k)의 시간복잡도를 가집니다. 공간복잡도는 O(N+k)만큼을 가집니다. (여기서 모든 수가 고유하고 무작위로 분산된 데이터를 다룰 경우에는 k는 logN과 동일하게 작동됩니다.) Radix Sort는 정수에 대해서 주로 사용되며, 음수 또는 부동 소수점 수와 같은 다른 형태의 숫자에는 적합하지 않을 수 있습니다. 또한, 알고리즘이 각 자릿수에 따라 정렬하기 때문에 정수의 자릿수가 크면 성능이 떨어질 수 있습니다.

Radix Sort의 장점은 안정성과 시간 복잡도의 선형성입니다. 그러나 데이터가 정수이어야 하며, 다른 정렬 알고리즘에 비해 상대적으로 느린 성능을 보일 수 있습니다. 이를 통해 Radix Sort의 특징과 한계를 잘 이해하면서 적절한 상황에서 사용할 수 있습니다.

[Kim-Ju-won]

1. 시간 복잡도의 표기 방법 3가지를 설명해주시고, 그 중에 자주 사용하는 방법 한가지를 왜 사용하는지 설명해주세요.
2. BFS, DFS의 차이점과 장단점을 설명해주세요!
3. 최단 거리 알고리즘의 세가지를 간단하게 설명해주시고, 시간복잡도에 대해서 설명해주세요