https://github.com/trekhleb/javascript-algorithms

문득 코딩 테스트 문제들을 풀다가 정답을 검색해 보는 경우가 늘고 다른 사람들이 설명하는 내용을 한 번에 이해하지 못하는 경우가 많아졌다.
"아 나 기초가 부족하구나", "알고리즘 공부 어떻게 하지?"라는 생각이 들어 고민하다가 이런 레포지토리를 찾게 됐다.

각 설명들이 여러 언어로 번역 돼있고 유튜브 설명도 있어서 입문이 쉬울 것 같다.

여기 나와있는대로 하나하나 다 직접 해보면서 기초를 다져보자.

우선 알고리즘 평가에 있어서 가장 중요한 기준이 되는 복잡도에 대해 알아보자.

복잡도

공간 복잡도

문제 처리를 위해 필요한 메모리의 크기.

시간 복잡도

문제 처리를 위해 특정 알고리즘이 수행되는 기본연산수.

알고리즘의 기본연산수는 각 연산의 수행 빈도를 합한 것으로 만일 연산의 수가 여러 개의 항으로서 표현된다면 그 중에서 가장 차수가 높은 것을 선택하는데 이러한 개념을 차수표기법(Order notation)이라 한다.

O-표기법(Big O)

예를 들어 아래 코드를 보자.

s = s + 1;
for(let i = 1; i <= n; i++) {
  for(let j = 1; j <=n; j++) {
    z = z + 1;
  }
}
for(let i = 1; i <=n; i++) {
  x = x + 1;
}

이는 아래와 같은 다항식으로 표현될 수 있다.
1 + n2 + n
차수표기법에 의해 가장 높은 항을 선택하면 O(n2)으로 표기된다.

이것 외에도 다양한 코드를 보고 시간 복잡도를 계산해 보자.

예1

const factorial = (n) => {
    if(n === 1) return 1;
    else return n * factorial(n - 1);
}

=> O(n)

자주 등장하는 팩토리얼 코드인데 잘 이해가 되지 않는다면 for문으로 바꿔 보면 이해가 쉽다.

const factorial = (n) => {
  let answer = 1;
  for(let i = 1; i <= n; i++) {
    answer = answer * i;
  }
  return answer;
}

보면 결국 1에서 n까지 곱하는 것이므로 n에 비례하여 선형적으로 증가하기 때문에 O(n)이다.

예2

let sum = 0;
for(i = 0; i < n; i++) {
  for(j = 0; j < n * n; j++) {
    sum++;
  }
}

=> O(n3)
바깥 for문은 n번, 내부 for문은 n2번 반복하기 때문에 O(n * n2) = O(n3)이다.

O-표기법의 대소관계

O(1) < O(logn) < O(n) < O(nlogn) < O(n2) < O(n3) < O(2n)

출처: https://www.bigocheatsheet.com/

---

일단 기본 지식은 이정도면 충분한 것 같다. 이제 하나씩 따라해 보면서 더 깊게 공부해 보자.