(3주차) 발자국 자료구조 알고리즘

삽입 정렬 (Insertion Sort)

개념
삽입 정렬은 리스트를 앞에서부터 차례로 정렬된 부분과 비교해서 적절한 위치에 삽입하는 방식의 정렬 알고리즘
손으로 카드를 정렬하는 방법과 비슷하다
이미 정렬된 부분은 항상 유지되고, 새로운 값을 적절한 자리에 넣는 방식
동작 방식
1. 두 번째 요소부터 시작해서 이전 요소들과 비교
2. 크기를 비교해서 알맞은 위치에 삽입
3. 끝까지 반복
시간 복잡도
- 평균/최악: O(n²)
- 최선(이미 정렬된 경우): O(n)
장점
- 구현이 간단함
- 거의 정렬된 데이터에서는 빠름
- 추가 메모리 필요 없음 (제자리 정렬, In-place)
단점
- 데이터가 많으면 비효율적 (시간 복잡도 때문에)

const Insertion = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    let insertingData = arr[i];
    let j;

    for (j = i - 1; j >= 0; j--) {
      if (arr[j] > insertingData) {
        arr[j + 1] = arr[j];
      } else {
        break;
      }

      arr[j + 1] = insertingData;
    }
  }
};

병합 정렬 (Merge Sort)

개념
병합 정렬은 분할 정복(Divide and Conquer) 방법을 사용하는 정렬 알고리즘
데이터를 반으로 나누고, 각각을 정렬한 후, 다시 병합하면서 정렬하는 방식
동작 방식
1. 리스트를 반으로 쪼갬
2. 각각 재귀적으로 병합 정렬 수행
3. 정렬된 두 리스트를 병합
시간 복잡도
- 최선/평균/최악: O(n log n)
장점
- 시간 복잡도가 안정적 (데이터 상태에 관계없이 O(n log n))
- 안정 정렬(같은 값의 순서 유지)
단점
- 추가 메모리 공간 필요 (배열을 나누고 병합하는 과정에서)
```
const Merge = (arr, leftIndex, midIndex, rightIndex) => {
  let leftAreaIndex = leftIndex;
  let rightAreaIndex = midIndex + 1;

  let tempArr = [];
  tempArr.length = rightIndex + 1;
  tempArr.fill(0, 0, rightIndex + 1);

  let tempArrIndex = leftIndex;

  while (leftAreaIndex <= midIndex && rightAreaIndex <= rightIndex) {
    if (arr[leftAreaIndex] <= arr[rightAreaIndex]) {
      tempArr[tempArrIndex] = arr[leftAreaIndex++];
    } else {
      tempArr[tempArrIndex] = arr[rightAreaIndex++];
    }
    tempArrIndex++;
  }

  if (leftAreaIndex > midIndex) {
    for (let i = rightAreaIndex; i <= rightIndex; i++) {
      tempArr[tempArrIndex++] = arr[i];
    }
  } else {
    for (let i = leftAreaIndex; i <= midIndex; i++) {
      tempArr[tempArrIndex++] = arr[i];
    }
  }

  for (let i = leftIndex; i <= rightIndex; i++) {
    arr[i] = tempArr[i];
  }
};

// leftIndex: 배열의 시작인덱스, rightIndex: 배열의 마지막 인덱스
const MergeSort = (arr, leftIndex, rightIndex) => {
  if (leftIndex < rightIndex) {
    let midIndex = parseInt(leftIndex + rightIndex) / 2;
    MergeSort(arr, leftIndex, midIndex);
    MergeSort(arr, midIndex + 1, rightIndex);
    Merge(arr, leftIndex, midIndex, rightIndex);
  }
};
```
  퀵 정렬 (Quick Sort)
  - 개념
    퀵 정렬도 분할 정복(Divide and Conquer) 방식의 정렬
    기준(pivot)을 하나 정해서, 그보다 작은 값과 큰 값으로 나누고, 각각 정렬한 후 합치는 방식
  - 동작 방식
    1. 피벗 선택
    2. 피벗을 기준으로 작은 값/큰 값으로 나누기
    3. 각 부분 배열에 대해 퀵 정렬 재귀 호출
  - 시간 복잡도
    - 평균: O(n log n)
    - 최악(피벗을 잘못 잡았을 때): O(n²)
  - 장점
    - 평균적으로 매우 빠름
    - 추가 메모리 거의 필요 없음 (제자리 정렬)
  - 단점
    - 최악의 경우 성능 저하 가능
    - 불안정 정렬(같은 값의 순서 보장 안 됨)
```
const swap = (arr, index1, index2) => {
  let temp = arr[index1];
  arr[index1] = arr[index2];
  arr[index2] = temp;
};

const divide = (arr, left, right) => {
  let pivot = arr[left];
  let leftStartIndex = left + 1;
  let rightStartIndex = right;

  while (leftStartIndex <= rightStartIndex) {
    while (leftStartIndex <= right && pivot >= arr[leftStartIndex]) {
      leftStartIndex++;
    }
    while (rightStartIndex >= left + 1 && pivot <= arr[rightStartIndex]) {
      rightStartIndex--;
    }

    if (leftStartIndex <= rightStartIndex) {
      swap(arr, leftStartIndex, rightStartIndex);
    }
  }

  swap(arr, left, rightStartIndex);
  return rightStartIndex;
};

const quickSort = (arr, left, right) => {
  if (left <= right) {
    let pivot = divide(arr, left, right);
    quickSort(arr, left, pivot - 1);
    quickSort(arr, pivot + 1, right);
  }
};
```
  메모이제이션 (Memoization)
  - 개념
    메모이제이션은 이미 계산한 값을 저장해서 재사용하는 최적화 기법
    주로 재귀함수와 함께 사용된다
    중복 계산을 피해서 성능을 높여준다
  - 왜 필요할까?
    - 재귀함수는 같은 값을 계속 계산하는 경우가 많아.
    - 예를 들어 피보나치 수열을 재귀로 구현하면, 같은 계산을 수없이 반복하게 돼서 비효율적이다
  - 어떻게 동작할까?
    1. 계산하려는 값이 이미 계산된 값인지 검사(검색)
    2. 있다면 저장된 값을 바로 반환
    3. 없다면 계산하고 결과를 저장
  - 보통 어디에 저장?
    - 보통 해시테이블(객체, Map 등)에 저장
    - 키: 계산하려는 값
    - 값: 계산 결과
  - 장점
    - 중복 계산 제거 → 성능 향상
  - 단점
    - 메모리 사용량 증가 (저장 공간 필요)
  타뷸레이션 (Tabulation)
  - 개념
    타뷸레이션은 상향식(bottom-up) 방식의 동적 프로그래밍
    작은 문제부터 차근차근 해결해서 테이블에 값을 저장하고, 그 값을 이용해서 큰 문제를 푸는 방식
  - 차이점 vs 메모이제이션
    - 메모이제이션: 탑다운(top-down) → 재귀함수 + 캐싱
    - 타뷸레이션: 바텀업(bottom-up) → 반복문 사용해서 테이블 채우기
  - 피보나치 예시
    1. fib[0], fib[1]을 먼저 저장
    2. fib[2]부터 fib[n]까지 차례로 계산
  - 장점
    - 재귀 호출 스택을 사용하지 않아서 스택 오버플로우 방지
    - 보통 메모이제이션보다 메모리를 적게 사용
  - 단점
    - 모든 값을 전부 다 계산해야 해서 필요 없는 값까지 구할 수도 있음

동적 프로그래밍에서 어떤 방식 더 좋을까

메모이제이션
- 간단하게 재귀함수 수정만으로 구현 가능
- 부분 문제 중 일부만 필요한 경우 적합
타뷸레이션
- 반복문으로 구현해서 스택 문제 없음
- 대부분의 경우 메모리 효율이 좋고 속도도 빠름

const fibonacci1 = (n) => {
  if (n === 0 || n === 1) return n;
  return fibonacci1(n - 2) + fibonacci1(n - 1);
};

const fibonacci2 = (n, memo) => {
  if (n === 0 || n === 1) return n;

  // 검색
  if (memo[n] === null) {
    memo[n] = fibonacci2(n - 2, memo) + fibonacci2(n - 1, memo);
  }

  return memo[n];
};

const fibonacci3 = (n) => {
  if (n <= 0) return n;

  let table = [0, 1];

  for (let i = 2; i <= n; i++) {
    table[i] = table[i - 2] + table[i - 1];
  }

  return table[n];
};

let start = new Date();

console.log(fibonacci1(40));
let end = new Date();
console.log("피보나치 1 실행 시간 : ", end - start);

start = new Date();
console.log(fibonacci2(40, {}));
end = new Date();
console.log("피보나치 2 실행 시간 : ", end - start);

start = new Date();
console.log(fibonacci3(40, {}));
end = new Date();
console.log("피보나치 3 실행 시간 : ", end - start);

삽입 정렬 (Insertion Sort)

병합 정렬 (Merge Sort)

퀵 정렬 (Quick Sort)

메모이제이션 (Memoization)

타뷸레이션 (Tabulation)