6장 그 외의 알고리즘들

[66] 미분을 활용하여 고차 방정식의 해를 구하는 ‘뉴턴법’

뉴턴법은 접선의 기울기를 ‘도함수’와 ‘x, y의 변화량’으로 표현하여 고차방정식의 해를 구하는 알고리즘이다.

const newtonMethod = (k, x) => {
  let count = 0;
  let guess;
  while (count < 5) {
    guess = x - (x ** 2 - k)/ (2*x)
    x = guess;
    count ++;
    console.log(count, guess)
  }
  return guess;
}
console.log(newtonMethod(5, 10))

[69] 그래프에서 최적 경로를 구하는 ‘데이크스트라 알고리즘’

출발점, 종착점, 경유 지점과 그들을 연결하는 경로를 그래프로 표현하여 데이크스트라 알고리즘으로 최적 경로를 구한다.

function PriorityQueue () {
  this._nodes = [];

  this.enqueue = function (priority, key) {
    this._nodes.push({key: key, priority: priority });
    this.sort();
  };
  this.dequeue = function () {
    return this._nodes.shift().key;
  };
  this.sort = function () {
    this._nodes.sort(function (a, b) {
      return a.priority - b.priority;
    });
  };
  this.isEmpty = function () {
    return !this._nodes.length;
  };
}

function Graph(){
  var INFINITY = 1/0;
  this.vertices = {};

  this.addVertex = function(name, edges){
    this.vertices[name] = edges;
  };

  this.shortestPath = function (start, finish) {
    var nodes = new PriorityQueue(),
        distances = {},
        previous = {},
        path = [],
        smallest, vertex, neighbor, alt;

    for(vertex in this.vertices) {
      if(vertex === start) {
        distances[vertex] = 0;
        nodes.enqueue(0, vertex);
      }
      else {
        distances[vertex] = INFINITY;
        nodes.enqueue(INFINITY, vertex);
      }

      previous[vertex] = null;
    }

    while(!nodes.isEmpty()) {
      smallest = nodes.dequeue();

      if(smallest === finish) {
        path = [];

        while(previous[smallest]) {
          path.push(smallest);
          smallest = previous[smallest];
        }

        break;
      }

      if(!smallest || distances[smallest] === INFINITY){
        continue;
      }

      for(neighbor in this.vertices[smallest]) {
        alt = distances[smallest] + this.vertices[smallest][neighbor];

        if(alt < distances[neighbor]) {
          distances[neighbor] = alt;
          previous[neighbor] = smallest;

          nodes.enqueue(alt, neighbor);
        }
      }
    }

    return path;
  };
}

var g = new Graph();

g.addVertex('A', {B: 7, C: 8});
g.addVertex('B', {A: 7, F: 2});
g.addVertex('C', {A: 8, F: 6, G: 4});
g.addVertex('D', {F: 8});
g.addVertex('E', {H: 1});
g.addVertex('F', {B: 2, C: 6, D: 8, G: 9, H: 3});
g.addVertex('G', {C: 4, F: 9});
g.addVertex('H', {E: 1, F: 3});

console.log(g.shortestPath('A', 'H').concat(['A']).reverse());

[70] 자연수 n이 소수인지 아닌지를 걸러 내는 ‘에라토스테네스의 체’

‘에라토스테네스의 체’는 자연수 중에서 소수가 아닌 값을 걸러내어 소수를 구하는 알고리즘이다.

const eratosthenes = (n) => {
  let array = [];
  let upperLimit = Math.sqrt(n);
  let output = [];

  for (let i = 0; i < n; i++) {
    array.push(true);
  }

  for (let i = 2; i <= upperLimit; i++) {
    if (array[i]) {
      for (let j = i * i; j < n; j += i) {
          array[j] = false;
      }
    }
  }
  for (let i = 2; i < n; i++) {
    if(array[i]) {
      output.push(i);
    }
  }
  return output;
};
console.log(eratosthenes(25))

[71] 재귀호출을 이용하여 N의 팩토리얼 구하기

재귀호출이란, 뱀이 자신의 꼬리를 삼키듯 함수가 자기 자신을 호출하는 것이다.

const fact = (n) => {
  if (n > 1) {
    return n * fact(n - 1)
  }
  return n;
}
console.log(fact(1), fact(5))

const fact = (n) => {
  let result = n;
  for(let i=n-1; i>0; i--){
    result *= i;
  }
  return result;
}
console.log(fact(1), fact(5))