삶 가운데 남긴 기록 AACII.TISTORY.COM
javascript 알고리즘 연습 본문
순차 검색
정렬된 배열로부터 특정 값을 찾아내는 알고리즘
<!DOCTYPE html>
<html>
<head>
<title> 순차 검색</title>
<script>
function linearSearch(x, a){
var i = 0;
var n = a.length;
while( i < n && x > a[i]){
i++;
if(x == a[i]){
return i;
}
}
return null;
}
var a = [1,3,5,7,9,12,15,35,46,50,61,77,83,94,99];
console.log(linearSearch(35, a)); /* 7 */
</script>
</head>
<body>
</body>
</html>
이진 검색
정렬된 데이터의 중간에 위치한 요소의 값을 비교해서 절반씩 검색 대상에서 제외 시켜서 이진트리 구조를 탐색하는 알고리즘
<!DOCTYPE html>
<html>
<head>
<title> 이진 검색</title>
<script>
function binarySearch(x, a){
var n = a.length;
var left = 0;
var right = n-1;
while(left < right){
var middle = Math.floor((left+right)/2);
if(x <= a[middle]){
right = middle;
}else{
left = middle+1;
}
}
if(x == a[right]) {
return right;
}
return null;
}
var a = [1,3,5,7,9,12,15,35,46,50,61,77,83,94,99];
console.log(binarySearch(35, a)); /* 7 */
</script>
</head>
<body>
</body>
</html>
퀵 정렬
배열을 두개로 나눈 후에 나눈 부분을 다시 퀵정렬로 정렬해 나가는 작업을 재귀적으로 반복
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>퀵정렬 </title>
<script>
function quickSort(x, first, last){
var p = x[Math.floor((first+last)/2)];
for (var i=first, j=last; ; i++, j--){
/* 왼쪽 부터 차례대로 p 이상의 값을 검색 */
while( x[i] < p) i++;
/* 오른쪽 부터 차례대로 p 이하의 값을 검색 */
while( p < x[j]) j--;
if(i >= j) break; /* i와 j가 교차하면 다음으로 이동 */
var w = x[i]; x[i] = x[j]; x[j] = w; /* x[i]와 x[j] 교환 */
}
/* 왼쪽에 두 개 이상 남아 있으면 왼쪽을 다시 정렬 */
if(first < i-1) {
quickSort(x, first, i-1);
}
/* 오른쪽에 두 개 이상 남아 있으면 오른쪽을 다시 정렬 */
if(j+1 < last){
quickSort(x, j+1, last);
}
}
var a = [17,12,15,11,18,19,13];
quickSort(a, 0, a.length -1);
console.log(a);
</script>
</head>
<body>
</body>
</html>
뉴턴-랩슨 법으로 제곱근 구하기
<!DOCTYPE html>
<html>
<head>
<title> 뉴턴-랩슨 법으로 제곱근 구하기 </title>
<script>
var EPSILON = 1.0e-10;
var d, xnew, xold;
var a = parseFloat(prompt("정수를 입력하세요."));
xold = ( a > 1) ? a : 1.0;
do {
/* 뉴턴 랩슨법 점화식이 EPSILON이 충분히 작을수록 값에 근사하게 됨. */
xnew = xold - (xold*xold -a)/(2.0*xold);
d = (xold - xnew)/xold;
xold = xnew;
}while( d > EPSILON);
document.write("sqrt("+ a + ") = " + xnew);
</script>
</head>
<body>
</body>
</html>
에라토스테네스의 체로 쌍둥이 소수 구하기
정수 n을 정하고 2이상 n 이하의 정수의 목록을 만듭니다.
가장 작은 소수인 2의 배수는 목록에서 지웁니다.
그다음 가장 작은 소수인 3의 배수도 목록에서 지웁니다.
이러한 작업을 반복하면 쌍둥이 소수를 구할 수 있습니다.
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>에라토스테네스의 체로 쌍둥이 소수 구하기</title>
<script>
var n = parseInt(prompt("정수 최대 값?"));
var p = []; /* 인덱스가 소수면 true, 합성수면 false로 처리 */
for(var i = 2; i <= n; i++){
p[i] = true;
}
var max = Math.floor(Math.sqrt(n)); /* 소수는 최대 루트n까지 구하면 충분 */
var x = 2;
while(x <= max){
for (var i = 2*x; i <= n; i += x){
p[i] = false; /* x의 배수는 합성수 */
}
while (!p[++x]); /* 다음 소수를 찾음 */
}
/* 쌍둥이 소수 출력 */
for(var i = 2; i <= n-2; i++){
if(p[i] && p[i+2]){
document.write(i+","+(i+2)+"<br>");
}
}
</script>
</head>
<body>
</body>
</html>
만델브로트 집합(mandelbrot set)
자기 닮음 구조의 프랙털(fractal) 도형입니다.
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title>만델브로트 집합 </title>
<script>
window.onload = function(){
var canvas = document.getElementById("mycanvas");
var ctx = canvas.getContext("2d");
var width = canvas.width;
var height = canvas.height;
/* 중심점을 설정하고 그림 */
var xc = -0.6, yc = 0;
draw();
/* 그리기 버튼을 클릭하면 그리기 시작 */
document.getElementById("button").onclick = draw;
/* canvas 위에서 마우스로 클릭한 지점을 중심 좌표로 설정 */
document.getElementById("mycanvas").onclick = function(event){
var ix = event.offsetX;
var iy = event.offsetY;
var mag = parseFloat(document.getElementById("magnification").value);
xc += (2*ix/width - 1)/mag;
yc += (2*iy-height)/mag/width;
draw();
};
/* 그리는 함수 */
function draw(){
/* 배율 */
var mag = document.getElementById("magnification").value;
/* 최대 반복 횟수 */
var maxit = document.getElementById("maxit").value;
/* 중심 좌표 표시 */
displayCenter(xc, yc);
/* 만델브로트 집합을 그림 */
mandelbrot(ctx,xc,yc,mag,maxit);
}
};
/* 중심 좌표를 표시하는 함수 */
function displayCenter(xc, yc){
document.getElementById("xc").innerHTML = xc.toFixed(3);
document.getElementById("yc").innerHTML = yc.toFixed(3);
}
/* 만델브로트 집합을 그리는 함수 */
/* c는 canvas의 랜더링 컨텍스트 */
/* xc, yc는 중심 좌표 */
/* mag는 확대 배율 */
/* maxit는 최대 반복 횟수 */
function mandelbrot(c, xc, yc, mag, maxit){
var w = c.canvas.width;
var h = c.canvas.height;
var xmin = xc - 1/mag;
var xmax = xc + 1/mag;
var ymin = yc - (xmax-xmin)*h/w/2;
var ymax = yc + (xmax-xmin)*h/w/2;
var dx = (xmax-xmin)/w;
var dy = (ymax-ymin)/h;
/* 색상 구분용 색상(반지름 2 안에 있던 횟수로 색을 구분) */
var color = [];
color[0] = "black"; /* 만델브로트 집합의 점 색상은 검정색으로 함 */
var L=255, dL=255/maxit;
for(var i = maxit; i > 0; i--){
color[i] = "rgb(255,"+Math.floor(L)+", 255)";
L -= dL;
}
/* X축 방향의 픽셀을 검사 */
for(var i = 0; i < w; i++){
var x = xmin + i*dx;
/* Y축 방향의 픽셀을 검사 */
for(var j = 0; j < h; j++){
var y = ymin + j*dy;
/* z1=x+iy */
var a = x, b = y;
var a2 = a*a, b2 = b*b;
/* 반지름 2안에 maxit번 이내면 반복 */
for(var count=maxit; a2+b2 <= 4 && count; count--){
/* z_n+1 = z_n^2 + x + iy */
b = 2*a*b + y;
a = a2 - b2 + x;
a2 = a*a;
b2 = b*b;
}
/* count 값에 따라 색을 구분하여 점을 그림 */
c.fillStyle = color[count];
c.fillRect(i,j,1,1);
}
}
}
</script>
<style>
#mycanvas { border: 1px solid gray;}
input{ margin:0 10px; width: 60px; text-align:center;}
div{ font-size:small; margin-bottom: 5px;}
</style>
</head>
<body>
<canvas id="mycanvas" width="800" height="640"></canvas>
<div>
중심좌표(<span id="xc"></span>,<span id="yc"></span>) : 마우스 클릭 후 변경
<label>확대 배율: <input id="magnification" type="number" value="0.65"></label>
<label>최대 반복 횟수: <input id="maxit" type="number" value="60"></label>
<input id="button" type="button" value="그리기">
</div>
</body>
</html>
피보나치 수열
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title> 피보나치 수열 </title>
<script>
function fibonacci(n){
if(n<2) return n;
if(!(n in fibonacci)){
fibonacci[n] = fibonacci(n-1) + fibonacci(n-2);
}
return fibonacci[n];
}
for (var i = 0; i <= 30; i++){
console.log((" "+i).slice(-2)+":"+fibonacci(i));
}
</script>
</head>
<body>
피보나치 수열
</body>
</html>
벽을 맞고 튕겨 나오는 공 애니메이션
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
<title> 튕기는 볼 애니메이션 </title>
<script>
window.onload = function(){
var NBALL = 200; /* 공 개수 */
var R = 5; /* 공의 반지름 */
var TIME_INTERVAL = 33; /* 애니메이션 인터벌 ms */
var BACK_ALPHA = 0.3; /* 배경 알파 값 */
/* 캔버스 랜더링 컨텍스트 */
var canvas = document.getElementById('mycanvas');
var ctx = canvas.getContext('2d');
/* 벽 객체 */
var wall = {left: 0, right: canvas.width, top:0, bottom: canvas.height};
var balls = [];
for(var i = 0; i < NBALL; i++){
balls[i] = new Ball(wall.right/2, wall.bottom/2, R);
balls[i].setVelocityAsRandom(2,7).setColorAsRandom(50,255);
}
/* 애니메이션 실행 */
setInterval(drawFrame, TIME_INTERVAL);
/* 프레임 그리기 */
function drawFrame(){
/* 배경색 칠하기 */
ctx.fillStyle = 'rgba(0,0,0,'+BACK_ALPHA+')';
ctx.fillRect(0,0,canvas.width, canvas.height);
/* 공의 위치를 갱신하여 그림 */
for(i=0; i<balls.length;i++){
balls[i].move().collisionWall(wall).draw(ctx);
}
}
};
/* Ball 생성자 */
function Ball(x,y,r,vx,vy,color){
this.x = x;
this.y = y;
this.r = r;
this.vx = vx; /* 공 속도의 x성분 */
this.vy = vy; /* 공 속도의 y성분 */
this.color = color;
}
/* Ball 생성자의 프로토 타입 */
Ball.prototype = {
/* 속도를 임의로 설정 */
setVelocityAsRandom: function(vmin, vmax){
var v = vmin + Math.random()*(vmax-vmin);
var t = 2*Math.PI*Math.random();
this.vx = v*Math.cos(t);
this.vy = v*Math.sin(t);
return this;
},
/* 색을 임의로 설정 */
setColorAsRandom: function(lmin, lmax){
var R = Math.floor(lmin+Math.random()*(lmax-lmin));
var G = Math.floor(lmin+Math.random()*(lmax-lmin));
var B = Math.floor(lmin+Math.random()*(lmax-lmin));
this.color = 'rgb('+R+','+G+','+B+')';
return this;
},
/* 공 그리기 */
draw: function(ctx){
ctx.fillStyle = this.color;
ctx.beginPath();
ctx.arc(this.x, this.y, this.r,0,2*Math.PI,true);
ctx.fill();
return this;
},
/* 공을 움직임 */
move: function(){
this.x += this.vx;
this.y += this.vy;
return this;
},
/* 벽과 공의 충돌 */
collisionWall: function(wall){
/* 왼쪽 벽과 충돌 */
if(this.x - this.r < wall.left){
this.x = wall.left + this.r;
if(this.vx < 0) this.vx *= -1;
}
/* 오른쪽 벽과 출돌 */
if(this.x + this.r > wall.right){
this.x = wall.right - this.r;
if(this.vx > 0) this.vx *= -1;
}
/* 위쪽 벽과 충돌 */
if(this.y + this.r < wall.top){
this.y = wall.top + this.r;
if(this.vy < 0) this.vy *= -1;
}
/* 아래족 벽과 충돌 */
if(this.y + this.r > wall.bottom){
this.y = wall.bottom - this.r;
if(this.vy > 0) this.vy *= -1;
}
return this;
}
}
</script>
</head>
<body>
<canvas id="mycanvas" width="800" height="600"></canvas>
</body>
</html>
728x90
'DEV&OPS > Javascript' 카테고리의 다른 글
| javascript 정규 표현식 (0) | 2022.03.03 |
|---|---|
| javascript array, map, set (0) | 2022.03.03 |
| JSON (0) | 2022.03.02 |
| javascript object property (0) | 2022.03.02 |
| javascript prototype (0) | 2022.02.23 |