각종 알고리즘 소스 모음 (직접 짜본 소스)

gistfile1.js

// DFS (Depth First Search)

var n = 8; // 정점의 총 개수
var map = [];
var visit = [];

function dfs(v) {
	
	visit[v] = 1;
	
	for (var inx = 1; inx <= n; inx++) {
		// 정점 v와 정점 inx가 연결되었고, 정점 inx를 방문하지 않았다면,
		if (map[v - 1][inx - 1] == 1 && !visit[inx]) {
			console.log(v + " to " + inx + " move!!");
			dfs(inx); // 재귀호출
		}
	}	
}


function dfsStart() {

	// 연결된 간선 데이터 
	var con = [
	            [1,2]
	          , [1,3]
	          , [2,4]
	          , [2,5]
	          , [4,8]
	          , [5,8]
	          , [3,6]
	          , [3,7]
	          , [6,8]
	          , [7,8]
	          ];
	
	var start = 1; //dfs 시작 정점
	
	// 자바스크립트 이차원 배열 선언 및 초기화
	for (var inx = 0; inx < n; inx++) {
		map[inx] = [];
		
		for (var jnx = 0; jnx < n; jnx++) {
			map[inx][jnx] = 0;
		}
	}
	
	// 인접행렬 설정
	var length = con.length;
	for (var inx = 0; inx < length; inx++) {
		
		var v1 = con[inx ][0];
		var v2 = con[inx ][1];
		
		map[v1 - 1][v2 - 1] = 1;
		map[v2 - 1][v1 - 1] = 1;
		
		
	}
	
	console.log(map); // 인접 행렬 확인
	
	dfs(start);
}

dfsStart();

gistfile2.js

// DFS를 통한 최단 경로
var n = 5;
var min = n * n; // 모든 map의 정점 통과했을 때, 즉 최장경로

//인접 행렬 데이터
var adjacencyMatrix = [
    [1, 1, 1, 1, 1],
    [0, 0, 0, 0, 1],
    [1, 1, 1, 1, 1],
    [1, 0, 1, 0, 0],
    [1, 1, 1, 1, 1]
];


function shortDistDFS(x, y, d) { // d는 이동거리

	console.log("adjacencyMatrix["+ y +"]["+ x + "] : " + adjacencyMatrix[y][x]);
	
	console.log(y, x, d);
	if (x == n - 1 && y == n - 1) {
		console.log("end");
		if (min > d) {
			min = d;
		}
		return;
	}
	
	if (adjacencyMatrix[y][x] == 0) {
		return;
	}
	
	adjacencyMatrix[y][x] = 0; // 방문했음을 표시
	
	// 위로 이동할 수 있으면 위로 이동
	if (y > 0 && adjacencyMatrix[y - 1][x] !== 0) shortDistDFS(x, y, d + 1);
	
	// 아래로 이동
	if (y < n - 1 && adjacencyMatrix[y + 1][x] !== 0) shortDistDFS(x, y + 1, d + 1);
	
	// 왼쪽으로 이동
	if (x > 0 && adjacencyMatrix[y][x - 1] !== 0) shortDistDFS(x - 1, y, d + 1);
	
	// 오른쪽으로 이동
	if (x < n -1 && adjacencyMatrix[y][x + 1] !== 0) shortDistDFS(x + 1, y, d + 1);
	
	adjacencyMatrix[y][x] = 1; // 지나간 자리를 원상태로 돌림 
	
	return min;
}

console.log("answer is " + shortDistDFS(0, 0, 1));

gistfile3.js

//  재귀함수 예시
function recursive(val) {
	
	console.log(val);
	
	if (val == 10) {
		return;
	}
	
	recursive(val + 1);
}

recursive(1);

gistfile4.js

// 재귀함수를 이용한 팩토리얼 계산

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

// 재귀함수는 반복문을 이용해 바꿀 수 있다. 
// 역으로 반복문은 재귀함수로 바꿀 수도 있다.
// 재귀함수의 경우 스택을 이용하기 때문에 스택오버플로우를 유의해야한다.
function repeat(n) {
    var r = 1;
    
    for (var inx = 2; inx < n; inx++) {
        r *= inx;
    }
    
    return r;
}

gistfile5.js

// 피보나치 수 구하기

// 1. 재귀함수 이용 (50이상의 n에 대해 성능이 좋지 않음)
function fibo(n) {
    if (n ==  1 || n == 2) {
        return 1;
        
    } else {
        return fibo(n-1) + fibo(n-2);
    }
}

// 이차원 배열을 이용한 메모이제이션 기법
// fn을 한 번 계산하고 나면 배열에 저장하여 중복 계산을 막는다
function fibo2(n) {
    var memo = [];
    
    if (memo[n] > 0) {
        return memo[n];
    }
    
    if (n == 1 || n == 2) {
        return memo[n] = 1;
    } else {
        return memo[n] = fibo2(n - 1) + fibo2(n -2);
    }
}

gistfile6.js

// 금액 맞추기 (1, 2, 5, 10, 20, 50만 6가지 지폐로 100만원 지불하기)

// 1. 무식한 방법 don't do this
function countMoney() {
    var bills[6] = {1, 2, 5, 10, 20, 50};
    var count = 0;
    var money = 100;
    
    for (var a = money; a >= 0; a -= biles[0]){
        for (var b = ){
            for (var c =) {
                for (var d = ) {
                    for (var e = ) {
                        if (e % bills[5] == 0){
                            count++;
                        }
                    }
                }
            }
        }
    }
    
    return count;
}

// 2. 재귀적으로 작성하기
// 50만원 권을 1장만 쓴느 경우의 수는 1,2,5,10,20으로 50만원을 지불하는 경우의 수와 같다
// 6종류의 지폐문제가 5종류의 지폐문제로 바뀜

gistfile7.js

// n/m 수분할 (n을 m 이하의 수로 수분할할 경우 개수 구하기)
function partition(n, m) {
    var count = 0;
    
    if (n < m) { // m<m 이면 n/m 수분할은 n/n 수분할과 같다
        m = n;
    }
    
    if (n ==0) {
        return 1;
    }
    
    for (var inx = 1; inx <= m; inx++) {
        count += partition(n-i, i);
    }
    
    return count;
}

// n/m 수분할을 모두 출력하는 프로그램
function partition_print(n,m,arr[],arr_len) {
    var count = 0;
    
    if (n < m) { // m<m 이면 n/m 수분할은 n/n 수분할과 같다
        m = n;
    }
    
    if (n ==0) {
        print_arr(arr, arr_len);
        return 1;
    }
    
    for (var inx = 1; inx <= m; inx++) {
        arr[arr_len] = i;
        count += partition(n-i, i, arr, arr_len + 1);
    }
    
    return count;
}