정렬

선택정렬

가장 작은 데이터를 선택하여 맨 앞에 있는 데이터와 바꾸고, 그다음 작은 데이터를 맨앞 다음의 데이터와 바꾸는 것을 반복하는 정렬방식.

시간복잡도: O(N²)

삽입정렬

데이터를 확인하여 알맞은 위치에 데이터를 삽입하는 정렬

두번째 데이터부터 데이터를 확인하면서 앞에서부터 데이터를 정렬하는데, 앞의 데이터들은 정렬되어있기 때문에 데이터를 확인할 때 삽입될 데이터보다 작은 데이터를 만나면 그 위치에서 멈추게 된다. 따라서 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 동작한다 (O(N))

시간복잡도:O(N²)

퀵정렬

가장 많이 사용되는 알고리즘으로 기준데이터를 선택하여 큰 데이터와 작은 데이터의 위치를 바꾸는 방식.

기준데이터를 설정할 때 마다 절반씩 나뉘기 때문에 O(NlogN)의 시간복잡도를 가진다.

시간복잡도: O(NlogN)

계수정렬

특정 조건이 부합되어야 사용할 수 있지만, 조건이 충족되면 매우 빠른 알고리즘

선언된 리스트(배열)에 데이터의 갯수를 넣고 출력하는 방식.

모든 범위를 담을 수 있는 리스트를 선언해야 하기 때문에 메모리가 많이 필요하며, 가장 작은 데이터와 가장 큰 데이터 +1개의 리스트가 필요하다. 가장 작은 수와 큰 수의 차이가 크고, 갯수가 적다면 상당히 비효율적인 정렬방식

시간복잡도:O(N+K) 데이터 중 최대값의 크기: K

이진탐색

절반씩 나눠가며 탐색하는 것으로, 전화번호부의 전화번호를 찾을 때 절반씩 페이지를 나눠 펼쳐보는 것과 같다.
정렬된 데이터에서만 사용이 가능하며 O(logN)라는 짧은 시간복잡도를 가진다.
시간복잡도: O(logN)

반복문 사용

const binary_search = (array, target, lt, rt) => {
  if (lt > rt) return null
  const mid = parseInt((lt + rt) / 2);
  if (array[mid] === target) {
    return mid
  } else if (array[mid] > target) {
    return binary_search(array, target, lt, mid - 1);
  } else {
    return binary_search(array, target, mid+1, rt)
  }
}

const n = 10
const target = 7
const array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]

binary_search(array, target, 0, n - 1)
  ? console.log(binary_search(array, target, 0, n - 1) + 1)
  : console.log("원소가 존재하지 않습니다.");

while문 사용

const binary_search = (target, arr) => {
  let answer;
  arr.sort((a, b) => a - b);
  let lt = 0, rt = arr.length - 1;
  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2);
    if (arr[mid] === target) {
      answer = mid + 1;
      break;
    } else if (arr[mid] > target) {
      rt = mid - 1;
    } else lt = mid + 1;
  }
  return answer;
}

const n = 10
const target = 7
const array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19]
  
console.log(binary_search(target, array) || "원소가 존재하지 않습니다");

예시문제풀이

이코테 197p 부품찾기

문제 입출력

const input = `5
8 3 7 9 2
3
5 7 9
`.split('\n'); // no yes yes
const N = Number(input[0]);
const M = Number(input[2]);
const sell = input[1].split(" ").map(a=>Number(a))
const buy = input[3].split(" ").map(a => Number(a))

계수정렬 풀이

function counting_sort(target, arr) { // 계수정렬
  arr.sort((a,b)=>a-b)
  const array = Array.from({ length: Math.max(...arr)+1 }, () => [])
  arr.map(v => array[v].push(1));
  return array[target].length ? "yes" : "no"
}
console.log(buy.map(item => counting_sort(item, sell)));

이진탐색 풀이

function binary_search(target, arr) {
  let answer = "no";
  arr.sort((a, b) => a - b);
  let lt = 0, rt = arr.length - 1;
  while (lt <= rt) {
    let mid = parseInt((lt + rt) / 2);
    if (arr[mid] === target) {
      answer = "yes"
      break;
    } else if (arr[mid] > target) {
      rt = mid - 1;
    } else lt = mid + 1;
  }
  return answer;
}
console.log(buy.map(item => binary_search(item, sell)));