Merge Sort

병합정렬

시간 복잡도: O(nlogn)

공간 복잡도: O(n)

 

merge 함수는 두 배열을 합쳐 한 배열로 정렬합니다.

mergeSort 함수는 재귀적으로 배열을 나누고 merge 함수로 합칩니다.

/**
 * @param {int[]} leftArr 
 * @param {int[]} rightArr 
 */
const merge = (leftArr, rightArr) => {
  let result = []
  let leftIndex = 0
  let rightIndex = 0
  while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
    if (leftArr[leftIndex] < rightArr[rightIndex]) {
      result.push(leftArr[leftIndex])
      leftIndex++
    } else {
      result.push(rightArr[rightIndex])
      rightIndex++
    }
  }
  while (leftIndex < leftArr.length) {
    result.push(leftArr[leftIndex])
    leftIndex++
  }
  while (rightIndex < rightArr.length) {
    result.push(rightArr[rightIndex])
    rightIndex++
  }
  return result
}

/**
 * 
 * @param {int[]} arr 
 */
const mergeSort = (arr) => {
  if (arr.length <= 1) return arr
  let mid = Math.floor(arr.length / 2)
  let left = mergeSort(arr.slice(0, mid))
  let right = mergeSort(arr.slice(mid))

  let result = merge(left, right)
  return result
}

버블 정렬

시간 복잡도: O(n2)

공간 복잡도: O(1)

const swap = (arr, index, nextIndex) => {
  [arr[index], arr[nextIndex]] = [arr[nextIndex], arr[index]]
}

const bubbleSort = (arr) => {
  for (let i = arr.length; i >= 0; i--) {
    let noSwap = true
    for (let j = 0; j < i; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
        noSwap = false
      }
    }
    if (noSwap) break
  }
  return arr
}

선택 정렬

시간 복잡도: O(n2)

공간 복잡도: O(1)

const swap = (arr, index, nextIndex) => {
  [arr[index], arr[nextIndex]] = [arr[nextIndex], arr[index]]
}

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

삽입 정렬

시간 복잡도: O(n2)

공간 복잡도: O(1)

const insertionSort = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    console.log(arr)
    let currentValue = arr[i]
    for (let j = i - 1; j >= 0 && arr[j] > currentValue; j--) {
      arr[j + 1] = arr[j]
      arr[j] = currentValue
    }
  }
  return arr
}

1. Understand the problem

  • 문제를 자신의 방식으로 다시 말할 수 있는지?
  • 문제에 들어가는 입력 데이터는 무엇인지?
  • 해결책에서 얻을 수 있는 결과는 무엇인지?
  • 문제를 해결할 충분한 정보를 가지고 있는지?
  • 함수나 변수 등의 이름은 어떻게 정할 것인가?

2. Explore examples

  • 간단한 예제로 시작하기
  • 더 복잡한 예제 진행하기
  • 빈 입력값을 가진 예제로 테스트하기
  • 잘못된 입력값을 가진 예제로 테스트하기

3. Break it down

  • 수행해야 할 단계를 명시적으로 기록하기

4. Solve or Simplify

  • 문제를 해결하거나 더 간단한 문제 해결하기

5. Look back and Refactor

  • 결과를 확인할 수 있는지?
  • 결과를 다르게 할 수 있는지?
  • 한번에 코드를 이해할 수 있는지?
  • 다른 문제에서도 결과값이나 함수를 사용할 수 있는지?
  • 수행 시간이 적절한지?
  • 다른 방법으로 문제를 해결할 수 있는지?
  • 다른 사람들은 이 문제를 어떻게 풀었는지?
function charCount(input) {
  if (!input) {
    return {};
  }
  if (typeof input !== 'string') {
    throw new Error('Input is not String');
  }
  let result = new Object();
  //  문자열을 소문자로 바꾸고 문자 단위로 나눈 뒤
  // 소문자이고 숫자인지 정규식을 사용해 필터링하고 정렬합니다.
  let charArray = input
    .toLowerCase()
    .split('')
    .filter((c) => /[a-z0-9]/.test(c))
    .sort();
  for (let i = 0; i < charArray.length; i++) {
    let char = charArray[i];
    result[char] = result.hasOwnProperty(char) ? result[char]++ : 1;
  }
  return result;
}

출력 예시

console.log(charCount('abc'));
// { a: 1, b: 1, c: 1 }
console.log(charCount('c b a a a 1 2 3'));
// { '1': 1, '2': 1, '3': 1, a: 1, b: 1, c: 1 }
console.log(charCount(123));
// Error: Input is not String
console.log(charCount(''));
// {}
console.log(charCount());
// {}
console.log(charCount('Hi, my name is Jinsu!!'));
// { a: 1, e: 1, h: 1, i: 1, j: 1, m: 1, n: 1, s: 1, u: 1, y: 1 }

다른 방식

function charCount2(str) {
  let obj = new Object();
  for (const char of str) {
    char = char.toLowerCase();
    if (/[a-z0-9]/.test(char)) {
      obj[char] = ++obj[char] || 1;
    }
  }
  return obj;
}
let names = ["Michael", "Bab", "Andrea"];
let num = [4, 5, 6, 9, 8, 7, 1, 2, 3, 0, 11, 12, 13, 10];
let values = [true, false, {}, [], 1, "a"];
// [ 'Andrea', 'Bab', 'Michael' ]
// [ [], 1, {}, 'a', false, true ]
// [0, 1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9];
console.log(names.sort());
console.log(values.sort());
console.log(num.sort());

문자열은 알바벳 순으로 정렬됩니다.

 

배열, 숫자, 객체, 문자열, false, true 순으로 정렬이 됩니다.

 

숫자는 문자열의 유니코드 코드 포인트를 따르기 때문에

1 11 12 2 3 4 순서로 정렬됩니다. 

숫자 순서로 정렬하기 위해서는 sort() 안에 비교 함수를 넣습니다

console.log(num.sort((a, b) => a - b));

/*
오름차순
[
   0,  1, 2, 3,  4,  5,
   6,  7, 8, 9, 10, 11,
  12, 13
]
*/

console.log(num.sort((a, b) => b - a));

/*
내림차순
[
  13, 12, 11, 10, 9, 8,
   7,  6,  5,  4, 3, 2,
   1,  0
]
*/

Map을 이용한 정렬

let list = [
  'korea',
  'Ukraine',
  'Russia',
  'japan',
  'china',
  'America',
  'poland',
  'Rumania',
];

// 임시 배열은 위치 및 정렬 값이있는 객체를 보유합니다.
let mapped = list.map(function (element, index) {
  return { index: index, value: element.toLowerCase() };
});
console.log(mapped);
// 축소 치를 포함한 매핑 된 배열의 소트
mapped.sort(function (a, b) {
  return +(a.value > b.value) || +(a.value === b.value) - 1;
});
console.log(mapped);
// 결과 순서를 위한 컨테이너
let result = mapped.map(function (element) {
  return list[element.index];
});
console.log(result);​
/*
let mapped = list.map(function (element, index) {
  return { index: index, value: element.toLowerCase() };
});
[
  { index: 0, value: 'korea' },
  { index: 1, value: 'ukraine' },
  { index: 2, value: 'russia' },
  { index: 3, value: 'japan' },
  { index: 4, value: 'china' },
  { index: 5, value: 'america' },
  { index: 6, value: 'poland' },
  { index: 7, value: 'rumania' }
]
mapped.sort(function (a, b) {
  return +(a.value > b.value) || +(a.value === b.value) - 1;
});
[
  { index: 5, value: 'america' },
  { index: 4, value: 'china' },
  { index: 3, value: 'japan' },
  { index: 0, value: 'korea' },
  { index: 6, value: 'poland' },
  { index: 7, value: 'rumania' },
  { index: 2, value: 'russia' },
  { index: 1, value: 'ukraine' }
]
let result = mapped.map(function (element) {
  return list[element.index];
});
[
  'America', 'china',
  'japan',   'korea',
  'poland',  'Rumania',
  'Russia',  'Ukraine'
]
*/

[참조]

Array.prototype.sort()

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

수행시간 비교: 기본 for loop < forEach < for of < for in

기본 for loop가 가장 빠릅니다.

 

Example

기본 for loop 사용: 3.799ms
for in loop 사용: 359.135ms
forEach 사용: 21.931ms
for of 사용: 26.932ms

function Loop1(nList) {
  let total = 0;
  for (let i = 0; i < nList.length; i++) {
    total += nList[i];
  }
  return total;
}

function Loop2(nList) {
  let total = 0;
  for (const num in nList) {
    total += num;
  }
  return total;
}

function Loop3(nList) {
  let total = 0;
  nList.forEach((num) => {
    total += num;
  });
  return total;
}

function Loop4(nList) {
  let total = 0;
  for (const num of nList) {
    total += num;
  }
  return total;
}

let n = 1000000;
let nList = new Array();
for (let i = 1; i <= n; i++) {
  nList.push(i);
}

console.time("기본 for loop 사용");
Loop1(nList);
console.timeEnd("기본 for loop 사용");

console.time("for in loop 사용");
Loop2(nList);
console.timeEnd("for in loop 사용");

console.time("for Each 사용");
Loop3(nList);
console.timeEnd("for Each 사용");

console.time("for of 사용");
Loop4(nList);
console.timeEnd("for of 사용");

1. forEach 문은 배열에서만 사용이 가능합니다.

2. for in 문은 모든 객체에서 사용이 가능하지만 key에만 접근합니다. value는 key를 사용해 접근해야 합니다.

3. for of 문은 컬렉션 개체가 [Symbol.iterator] 속성]을 가져야 합니다.

let sample = [1, 2, 3, 4, 5];
sample.Case = "I'am in the Cafe";

for (const key in sample) {
  if (sample.hasOwnProperty(key)) {
    console.log(key, sample[key]);
  }
}

// 0 1
// 1 2
// 2 3
// 3 4
// 4 5
// Case I'am in the Cafe

for (const iterator of sample) {
  console.log(iterator);
}

// 1
// 2
// 3
// 4
// 5

'코딩 테스트 > 알고리즘' 카테고리의 다른 글

Problem Solving Approach  (0) 2020.07.09
자바스크립트. 문자 세기  (0) 2020.07.08
자바스크립트. 정렬 순서  (0) 2020.07.04
Analyzing Performance of Arrays and Objects  (0) 2020.07.04
Big O Notation  (0) 2020.07.02

Big O of Objects

  1. 삽입 O(1)
  2. 제거 O(1)
  3. 탐색 O(n)
  4. 접근 O(1)

Big O of Object mehtods

  1. Object.keys() O(n)
  2. Object.values() O(n)
  3. Object.entries() O(n)
  4. Object.hasOwnProperty("키 이름") O(1)

Big O of Arrays

  1. 탐색 O(n)
  2. 접근 O(1)

Big O of Array methods

  1. push O(1)
  2. pop O(1)
  3. shift O(n)
  4. unshift O(n)
  5. concat O(n)
  6. slice O(n)
  7. splice O(n)
  8. sort O(nlogn)
  9. forEach/map/filter/reduce 등 O(n)

'코딩 테스트 > 알고리즘' 카테고리의 다른 글

Problem Solving Approach  (0) 2020.07.09
자바스크립트. 문자 세기  (0) 2020.07.08
자바스크립트. 정렬 순서  (0) 2020.07.04
자바스크립트. for 반복문 수행시간 비교  (0) 2020.07.04
Big O Notation  (0) 2020.07.02

What does better mean?

1. Faster?

2. Less memory-intensive?

3. More readable?

 

The Problem with Time

1. Different machines will record different times

2. The same machine will record different times

 

다른 performance 측정법

Counting Operations이 있지만 연산자를 세는 방법은

힘들고 시간이 오래 걸린다.

 

Big O 정의

간단한 연산들은 컴퓨터가 최대 f(n)번 해야한다면 알고리즘은 O(f(n))이다.

f(n)은 상수형, 선형 등 형태가 다양하다.

 

1. f(n)이 2n일 때 상수는 무시되고 O(n)이 된다.

2. f(n)의 최고차항만 남긴다.

 

O(1)

O(n)과 같이 보이지만 i가 10 이후부터 연산 개수가 증가하지 않기 때문에 O(1)이다!!

function logAtMost10(n) {
  for (var i = 1; i <= Math.min(n, 10); i++) {
    console.log(i);
  }
}

 

Space Complexity

boolean, number, undefined, null은 상수이다.

String 공간 복잡도는 O(n)이다.

참조형은 일반적으로 O(n)이고 n은 배열 길이나 object key 개수이다.

+ Recent posts