21-03-11 자바스크립트로 하는 자료구조와 알고리즘(5)

9장 집합

집합이란 유한하고 구분되는 객체들의 그룹
자바스크립트에서는 Set이 기본으로 지원된다
let exampleSet = new Set();
Set의 주요 특징은 유일함을 확인 한다는 것이다(중복되는 항목은 허용되지 않음)
Set.delete는 boolean값을 리턴하며 항목을 삭제할 수 있게 하는 메서드이다
Set.has는 집합 내에 존재하는지 확인하며 .delete / .has는 모두 O(1)의 시간 복잡도를 갖는다

Set을 사용하여 교집합 구하기

const intersectSets = (setA, setB) => {
  let intersection = new Set();
  for (let element of setB) {
    if (setA.has(element)) {
      intersection.add(element)
    }
    return intersection
  }
} // O(n)

어떤 집합이 다른 집합의 모든 항목을 포함하는 경우에는 상위 집합이 된다

const isSuperSet = (setA, subSet) => {
  for (let element of subSet) {
    if(!setA.has(element))
      return false;
  }
  return true;
}

Set을 사용한다면 합집합도 쉽게 구현할 수 있다

const unionSet = (setA, setB) => {
  let union = new Set(setA);
  for (let element of setB) {
    union.add(element);
  }
  return union
}

Spread Operator를 사용한 방법

1
2
3

const unionSetWithSpreadOperator = (setA, setB) => {
  return new Set([...setA,...setB]);
}

차집합은 .delete로 구현할 수 있다

const differenceSet = (setA, setB) => {
  let differ = new Set(setA);
  for (let element of setB) {
    differ.delete(element);
  }
  return differ;
}

집합을 사용해 배열의 중복 항목을 확인하기

const checkDupl = arr => {
  let mySet = newSet(arr);
  return mySet.size < arr.length;
}

개별적인 배열들에서 유일한 값만을 반환하기

const uniqueList = (arr1, arr2) => {
  // arr1 뒤에 arr2 배열을 붙이고 Set을 사용해 유니크한 값만 남기기
  let mySet = new Set(arr1.concat(arr2));
  return Array.from(mySet);
}

10장 검색과 정렬

검색은 자료 구조의 항목들을 반복적으로 접근하는 것 , 정렬은 자료구조의 항목들을 순서대로 위치시키는 것

한 인덱스씩 순차적으로 접근하는 선형 검색

const linearSearch = (arr, n) => {
  for (let i = 0, len = arr.length; i < len; i++) {
    if (arr[i] === n) return true;
  }
  return false;
}

정렬된 자료라면 이진검색을 사용할 수 있다

const binarySearch = (arr, n) => {
  let lowIndex = 0, highIndex = arr.length;
  while (lowIndex <= highIndex) {
    let midIndex = Math.floor((lowIndex + highIndex)/2);
    if (arr[midIndex] === n) return midIndex;
    else if (n > arr[midIndex]) lowIndex = midIndex+1;
    else highIndex = midIndex-1;
    return -1;
  }
}

이진검색을 사용하려면 자료를 정렬해야함

버블 정렬은 전체 배열을 순회하며 두 항목을 비교하고 교체하는 작업을 반복한다

const swap = (arr, idx1, idx2) => {
  let temp = arr[idx1];
  arr[idx1] = arr[idx2];
  arr[idx2] = temp;
}

const bubbleSort = arr => {
  for (let i = 0, len = arr.length; i < len; i++) {
    for (let j = 0; j <= i; j++){
      if (arr[j] > arr[j+1]) {
        swap(arr, i, j)
      } 
    }
  }
  return arr;
} // for문을 두 번 사용하므로 O(n의 제곱)값이 된다

선택 정렬은 가장 작은 항목을 찾고 해당 항목의 배열의 현 위치에 삽입하는 식으로 동작한다

const selectionSort = items => {
  let len = items.length, min;
  for (let i = 0; i < len; i++) {
    min = i;
    for (j = i+1; j < len; j++){
      if(items[j] < items[min]) min = j;
      if (i != min) swap(items, i, min);
    }
  }
  return items;
}

삽입 정렬을 배열을 순차적으로 검색하면서 정렬되지 않은 항목들을 왼쪽으로 이동시킨다

const insertionSort = items => {
  let len = items.length, 
      value, // 지금 비교중인 값
      i, // 정렬 안된 부분
      j; // 정렬 된 부분
  for (let i = 0; i < len; i++){
    // 
    value = items[i];
    for (j = i-1; j > -1 && items[j] > value; j--) {
      items[j+1] = items[j]
    }
    items[j+1] = value;
  }
  return items
}

퀵 정렬은 기준점을 기준으로 배열을 나눠 모든 항목이 정렬될 때까지 과정을 반복하는 정렬법이다

이 방법은 분할 정복을 이용한 재귀법으로 처리되어 평균 O(nlog2(n))으로 처리되지만 최악의 경우(이미 정렬된 배열을 받을 경우) O(n의 제곱)값을 갖는다

const quickSort = arr => {
  return quickSortHelper(arr, 0, arr.length-1);
}

const quickSortHelper = (arr, left, right) => {
  let idx;
  if (arr.length > 1) {
    idx = partition(arr, left, right);
    if (left < idx - 1) quickSortHelper(arr, left, idx -1);
    if (idx < right) quickSortHelper(arr, idx, right)
  }
  return arr;
}

const partition = (arr, left, right) => {
  let pivot = arr[Math.floor((left+right)/2)] // 배열의 중간값을 탐색
  // 정렬하다보면 left는 계속 증가하고 right는 계속 감소하므로 
  // left값이 right값을 넘어가게 됨 (base condition)
  while (left <= right) {
    while(pivot > arr[left]) left++
    while(pivot < arr[right]) right++
    if (left <= right) {
      let temp = arr[left];
      arr[left] = arr[right];
      arr[right] = temp;
      left++;
      right--;
    } 
  }
  return left;
}

퀵정렬의 단점은 기준점을 항상 잘못 선택하는 경우 시간 복잡도가 O(n의 제곱)이 될 수 있다는 것

퀵선택(quick select)은 정렬되지 않은 목록에서 k번째로 작은 항목을 찾는 선택 알고리즘으로 퀵정렬과는 달리 한쪽만 재귀적으로 수행함

// 정렬되지 않은 목록에서 k번째로 작은 항목을 찾기
const quickSelect = (arr, low, high, k) => {
  let p = partition(arr, low, high);
  if (p == (k-1)) return A[p];
  else if (p > (k-1)) return quickSelect(arr, low, p-1, k);
}

const medianQuickSelection = arr => {
  return quickSelect(arr, 0, arr.length-1, Math.floor(array.length/2))
} // O(n)의 시간복잡도

병합 정렬는 각 배열에 하나의 항목이 존재할때까지 나누고 순서대로 연결함

const merge = (leftArr, rightArr) => {
  let results = [], leftIdx = 0, rightIdx = 0;
  while (leftIdx < leftArr.length && rightIdx < rightArr.length){
    if (leftArr[leftIdx] < rightArr[rightIdx]) {
      results.push(leftArr[leftIdx++]);
    } else {
      results.push(rightArr[rightIdx++]);
    }
  }
  let leftReamins = leftArr.slice(leftIdx), 
      rightRemains = rightArr.slice(rightIdx);
  return results.concat(leftReamains).concat(rightRemains);
}

// 재귀함수로 배열을 전부 길이 1인 배열로 쪼개고 merge로 합하고를 반복한다
const mergeSort = arr => {
  if (arr.length <2) return arr;

  let mid = Math.floor(arr.length/2),
      leftArr = arr.slice(0, mid),
      rightArr = arr.slice(mid);
  
  return merge(mergeSort(leftArr), mergeSort(rightArr))
}

계수 정렬은 값들을 비교하지 않기 때문에 O(k+n)시간 안에 수행된다

계수 정렬은 숫자에 대해서만 동작하고 특정 범위가 주어져야 한다

const countSort = arr => {
  let hash = {}, countArr =[];
  // 해시 테이블을 생성하고 해시 테이블에 해당 값의 갯수를 셈
  for (let i = 0, len = arr.length; i < len; i++) {
    if (!hash[arr[i]]) hash[array[i]] = 1;
    else hash[array[i]]++;
  }
  // 값의 숫자를 센 해시테이블에서 값을 꺼내고 그 수 만큼 push를 반복
  for (let key in hash) {
    for (let i = 0; i < hash[key]; i++) {
      countArr.push(parseInt(key));
    }
  }
  return countArr;
} // O(k+n) 시간 복잡도를 가짐

자바스크립트의 내장 정렬 함수인 sort는 기본 오름차순으로 정렬하고 arr.sort((a,b) => a-b)와 같이 사용한다

수학 라이브러리를 사용하지 않고 정수의 제곱근 함수 구하기

const sqrtIntNaive = num => {
  if (num === 0 || num === 1) return num;

  let idx = 1, square = 1;
  while (square < number) {
    if (square === number) return square;

    idx++;
    square = idx*idx;
  }
  return idx;
}

이진 검색 알고리즘을 이용한 정수의 제곱근 함수 구하기

const sqrtInt = num => {
  if (num === 0 || num === 1) return num;

  let start = 1, end = num, ans;
  
  while (start <= end) {
    let mid = parseInt((start+end)/2)
    if (mid * mid === num) return mid;
    if (mid * mid < num) {
      start = mid+1;
      ans = mid
    } else {
      end = mid -1
    }
  }
  return  ans;
} // O(log2(n))

배열의 두 항목을 더해서 주어진 수가 될 수 있는지 확인하기

const findTwoSum = (arr, sum) => {
  for (let i = 0, len = arr.length; i < len; i++) {
    for (let j = i+1; j < len; j++) {
      if (arr[i]+arr[j] === sum) return true
    }
  }
  return false
}

배열에서 단 한번만 등장하는 항목 찾기

const findOnlyOnce = (arr, low, high) => {
  if (low > high) return null; // 배열의 길이가 0일때는 널값을 리턴
  if (low === high) return arr[low]; // 길이가 1일때
  
  let mid = Math.floor((high+low)/2); // 절반값을 구하고
  
  if (mid % 2 === 0) {
    if (arr[mid] === arr[mid+1]) // 오른쪽과 비교
      return findOnlyOnce(arr, mid+2, high);
    else 
      return findOnlyOnce(arr, low, mid)
  } else {
    if (arr[mid] === arr[mid-1]) // 왼쪽과 비교 
      return findOnlyOnce(arr, mid+1, high);
    else 
      return findOnlyOnce(arr, low, mid-1);
  }
}

const findOnlyOnceHelper = arr => {
  return findOnlyOnce(arr, 0, arr.length);
}

문자열을 길이순으로 정렬하는 자바스크립트 정렬 비교 함수

1
2
3

const sortByStringLength = arr => {
  return arr.sort((a, b) => a.length - b.length)
}

단어 세기 목록 구현하기

const wordCnt = sentence => {
  let wordsArr = sentence.replace(/[.]/g, "").split(''),
      occurenceList = {}, answerList = {};

  for (let i = 0, wordsLen = wordsArr.length; i < wordsLen; i++) {
    let currWord = wordsArr[i];
    if (!occurenceList[currWord]) occurenceList[currWord] = 1;
    else occurenceList[currWord]++;
  }
  
  let arrTemp = [];
  for (let prop in occurenceList) {
    arrTemp.push([occurenceList[props], prop])
  }

  arrTemp.sort((a,b) => b[0] - a[0]);

  for (let i = 0, len = arrTemp.length; i < len; i++) {
    let curr = arrTemp[i];
    answerList[curr[1]] = curr[0];
  }
  return answerList;
}

21-03-11 자바스크립트로 하는 자료구조와 알고리즘(5)

9장 집합

10장 검색과 정렬

Harry Kim