그림으로 배우는 알고리즘 Basic #6
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))
Author And Source
이 문제에 관하여(그림으로 배우는 알고리즘 Basic #6), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@k904808/그림으로-배우는-알고리즘-Basic-6저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)