기본적인 알고리즘 정리

• 기본적으로 알아야하는 유형
  : 이해해서 외우고 코딩테스트 직전에 보고가야한다.

1. GCD

• 재귀를 이용한 유클리드 호제법 GCD 구하는 방법

function gcd(M, N){
  if( M % N === 0 ) return N;
  return gcd( N,  M % N );
}
let GCD = gcd(M,N)

2. 순열/조합

3. 정렬은 Array.prototype.sort 사용

4. DFS(재귀), BFS(큐)

5. 분할정복(재귀), DP => 감을 잡기 어렵기 때문에 케이스 스터디 필요 (Geeksforgeeks)

• 재귀를 이용한 factorial (순열)

function factorial(n){
  if(n <= 1) return 1;
  return n * factorial(n-1)  
}

• 피보나치 (memoization (O(n)))

function fibonacci(n){
  memo = [0,1];
  function aux(n){
    if(memo[n] !== undefined) return memo[n];
    else memo[n] = aux(n-1) + aux(n-2); 
    return memo[n]
  }
  return aux(n);
}