(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);