문제로 풀어보는 알고리즘 문제풀이

0.3_1.js

/*
* 0.3 생각해보기 
* k를 인자로 받아서 k만큼 오른쪽으로 회전시키는 함수를 작성하라. 오른쪽으로 회전하는 것을 k번 반복하면 되지만 이 방법은 느리다. 더 빠른 방법은?
*/
function rotateArray(arr, s, t, k) {
	console.log("start");
	
	var temp = [];
	
	for (var inx = 0; inx < k; inx++) {
		console.log("inx : " + inx);
		temp[inx] = arr[t - k + inx + 1];
	}
	
	for (var jnx = t; jnx > s - 1; jnx--) {
		console.log("jnx : " + jnx);
		arr[jnx + k] = arr[jnx];
	}
	
	for (var knx = 0; knx < k; knx++) {
		console.log("knx : " + knx);
		arr[s + knx] = temp[knx];
		arr.pop();
	}
	
	
	return arr;
}

console.log(rotateArray([1,2,3,4,5], 2, 4, 2));

0.4_1.js

/*
* 0.4 배열을 이용한 Queue 생성 (원형큐, 선형큐의 경우 메모리 관리가 효율적이지 않음)
* 연결리스트를 이용하면 고정된 배열의 크기에 대한 구애없이 큐를 사용할 수 있음
*/

// Queue 생성
var Queue = funciton (size) {
    this.capa = capa;
    this.storedValue = [];
    this.size = 0;
    this.head = 0;
    this.tail = -1;
}            


// 삽입
Queue.prototype.enqueue = function (val) {
    if (this.capa == this.size) {
        print("this queue is full");
        return;
    }

    this.tail = (this.tail + 1) % this.capa; // 원형큐
    this.size++;
    
    this.storedValue[tail] = val;
    
}    

// 처리
Queue.prototype.dequeue = function () {
    
    if (this.size == 0) {
        print("this queue is empty");
        return;
    }
    
    var returnVal = this.storedValue[head];
    
    this.head = (this.head + 1) % this.capa; // 원형큐
    this.size--;
    
    return returnVal;
}


// 출력
function print (str) {
    /*var printEl = document.getElementById("print");
    var pEl = document.createElement("P");
    pEl.innerHTML = str;
    printEl.appendChildNode(pEl);*/
    
    console.log(str);
}  


// 실행
function start() {

    var queue = new Queue(3);
    queue.enqueue(1);
    queue.enqueue(3);
    queue.enqueue(5);
    queue.enqueue(7);
    queue.dequeue();
    queue.dequeue();
    queue.dequeue();
    queue.dequeue();
    
    
}

start();

0.4_2.js

/*
* 0.4 생각해보기
* 배열을 이용하여 스택을 작성하라.
*/

var Stack = funciton (capa) {
    this.capa = capa;
    this.storedValue = [];
    this.size = 0;
    this.head = -1;
}

Stack.prototype.enStack = function (val) {
    
    if (this.capa == this.size) {
        console.log("stack is full");
        return;
    }
    
    this.head++;
    this.storedValue[head] = val;
    this.size++;
    
}

Stack.prototype.deStack = function () {
    if (this.size == 0) {
        console.log("this stack is empty");
        return;
    } 
    
    var val = this.storedValue[head];
    
    this.size--;
    this.head--;
    
    return val;
}

function test () {
    
    var stack = new Stack(3);
    stack.enStack(1);
    stack.enStack(3);
    stack.enStack(5);
    stack.enStack(7);
    stack.deStack();
    stack.deStack();
    stack.deStack();
    stack.deStack();
}

0.4_3.js

/*
* 0.4 풀이가 있는생각해보기
* 일반적인 데이터 타입을 다룰 수 있도록 큐를 수정하라.
*/

// javascript 의 경우 데이터타입의 제한이 없기 때문에 위의 큐 생성 코드로 해결 가능

0.6_0.b.js

/*
* 0.6 0.b 추가문제
* int형 배열의 모든 원소의 값이 k이면 1, 아니면 0을 반환하는 all_is() 함수를 작성하라.
* 배열과 배열의 길이, 그리고 정수 k를 인자로 받는다.
*/

function all_is (arr, size, k) {
    for (var inx = 0; inx < size; inx++) {
        if (arr[inx] !== k) {
            return 0;
        }
    } 
    
    return 1;
}