Data structures & Algorithms with JavaScripts 스터디 9~11일차

210519 수요일 9~11일차

# 8일차 복습

CH3 리스트

- #1 : 현재 리스트의 모든 요소보다 클 때만 요소를 삽입하는 함수를 구현하시오. 여기서 크다는 의미는 숫자일 때는 크기를 비교하고, 텍스트일 때는 알파벳순으로 나중을 의미한다.

 

현재 리스트의 모든 요소보다 클 때라는 조건을 만족하는 지 확인하기 위한 함수를 만들었다.

모든 요소보다 크면 true, 큰 요소가 존재할 시 중간에 false를 반환해주는 함수를 구현했다.

 

먼저 삽입하고자 하는 요소 (after)를 find함수로 찾아서 인덱스를 받은 다음 인덱스가 존재한다면 그 위치에 slice함수를 이용해서 삽입하였다. 삽입 후에는 listSize를 1 증가시킨다.

 

- #2 현재 리스트의 모든 요소보다 작을 때만 요소를 삽입하는 함수를 구현하시오.

 

비교 연산자만 반대로 바꾸어 구현하였다.

 

- #3 사람의 이름과 성별을 저장하는 Person 클래스를 구현하시오. 최소한 10개의 Person 객체를 포함하는 리스트를 만드시오. 리스트에서 같은 성별을 가진 사람을 모두 출력하는 함수를 구현하시오.

 

filter는 주어진 조건을 통과하는 모든 요소를 모아 배열로 반환한다. 따라서 이를 통해 인자로 주어진 성별을 가진 객체만 모아서 배열을 구성하도록 했다.

 

CH4 스택

- 가장 윗 부분에서만 자료의 추가/삭제가 일어나므로 실행속도가 빠르고 구현이 쉽다.

 

- 후입선출로 밑바닥에 있는 요소에 접근하려면 모든 요소를 제거하는 수 밖에 없다. 

 

- Top은 pop으로 확인할 수 있지만 요소를 꺼내기 때문에 peek으로 내용을 확인한다. peek은 top - 1의 위치에 접근해 스택의 탑 요소를 확인한다. (스택의 요소가 3이면 top(length)는 3이고 배열의 가장 오른쪽 값은 가장 윗 값이므로 top-1이 top에 있는 요소의 인덱스다.

 

- 진법 변환

1. n의 가장 오른쪽 숫자는 n%b이다. 이 값을 스택에 추가한다.

=> s.push(num % base);

 

2. n을 n/b으로 치환한다.

=> num = Math.floor((num /= base)); // Math.floor는 소수값이 존재할 때 소수값을 버려주는 기능

 

3. n=0 이 되고 나머지가 없을 때까지 1번, 2번 과정을 반복한다.

=> do { } while( num > 0 ) ;

 

4. 스택에 저장된 숫자를 모두 꺼내 변환된 숫자 문자열을 만든다.

=> while(s.length() > 0 ) { converted += s.pop(); } // s의 요소가 pop을 통해 줄어들다가 0개가 되는 순간 while문은 종료된다.

return converted;

 

- 회문

문자열의 문자를 하나씩 넣고 다시 꺼내면서 만들어진 문자열과 원본 문자열을 비교하면 확인할 수 있다.

 

- 재귀

스택에 추가한 뒤 루프를 돌면서 꺼내서 수행하면 재귀적으로 사용할 수 있다.

 

 

210519 수요일 9~11일차

(책을 보면서 코딩은 했는데 인턴하면서 블로그에 작성할 시간이 없어 한번에 작성함)

CH5 큐

큐는 리스트의 일종으로 끝부분으로 데이터가 삽입되고 앞부분에서 데이터가 삭제되는 구조이다. 일어난 순서대로 데이터를 저장하지만 스택과 반대로 먼저 들어온 순서대로 처리한다. 은행에서 먼저 온 고객부터 원하는 업무를 처리하는 것과 같다. 선입선출(First In, First out). 운영체제의 프로세스 처리 순서, 프린트 스풀러, 대기줄 등에 사용한다.

 

5.1 큐 동작

인큐는 큐의 끝 부분에 요소 추가, 디큐는 큐의 앞부분의 요소 삭제, 큐의 앞부분 요소를 확인하는 peek, 요소 개수 length, 전체 삭제 clear

 

5.2 배열 기반의 Queue 클래스 구현

특히 자바스크립트 배열은 Queue 클래스 구현에 많은 도움을 준다. 배열의 끝부분에 데이터를 추가하는 push() 함수, 배열의 앞부분의 요소를 삭제하는 shift() 함수 등의 기능을 제공한다. 

 

function Queue() {
    this.dataStore = [];
    this.enqueue = enqueue;
    this.dequeue = dequeue;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
}

function enqueue(element) {
    this.dataStore.push(element);
}

function dequeue() {
    return this.dataStore.shift(); // 배열 앞부분에 저장된 요소를 삭제
}

function front() {
    return this.dataStore[0];
}

function back() {
    return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력
function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr += this.dataStore[i] + "\n";
    }
    return retStr;
}
// 큐가 비었는지 확인
function empty() {
    if (this.dataStore.length === 0) {
        return true;
    } else {
        return false;
    }
}

let q = new Queue();
q.enqueue("M");
q.enqueue("C");
q.enqueue("J");
console.log(q.toString());
q.dequeue();
console.log(q.toString());
console.log("Front of queue: " + q.front());
console.log("Back of queue: " + q.back());

MCJ를 인큐하고 디큐를 한번 수행하고 나면 맨 앞의 요소인 M이 사라진 것을 볼 수 있다.

front()는 맨 앞의 요소, back()은 맨 뒤의 요소를 보여준다.

 

 

5.3 Queue 클래스 사용하기 : 스퀘어 댄스 파티에서 파트너 정하기

파티가 시작되면 첫 번째 남자와 여자가 파트너가 된다. 다음으로 각각의 성별에서 다음으로 줄을 선 남자가 앞으로 나오고 이름이 소개된다. 남녀의 줄이 줄어들면서 맨 앞줄의 남은 남자가 하나도 없으면 이 사실을 공지한다.

 

function Queue() {
    this.dataStore = [];
    this.enqueue = enqueue;
    this.dequeue = dequeue;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
    this.count = count;
}

function enqueue(element) {
    this.dataStore.push(element);
}

function dequeue() {
    return this.dataStore.shift(); // 배열 앞부분에 저장된 요소를 삭제
}

function front() {
    return this.dataStore[0];
}

function back() {
    return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력
function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr += this.dataStore[i] + "\n";
    }
    return retStr;
}
// 큐가 비었는지 확인
function empty() {
    if (this.dataStore.length === 0) {
        return true;
    } else {
        return false;
    }
}

function Dancer(name, sex) {
    this.name = name;
    this.sex = sex;
}

function getDancers(males, females) {
    // # : text file 읽기
    const fs = require("fs");
    const names = fs.readFileSync("dancers.txt").toString().split("\n");

    // # : trim()으로 앞뒤로 붙어 있는 공백을 없애준다.
    for (let i = 0; i < names.length; ++i) {
        names[i] = names[i].trim();
    }

    for (let i = 0; i < names.length; ++i) {
        // # : 각 행을 sex, name으로 구분하게 한다.
        let dancer = names[i].split(" ");
        // console.log(dancer[0], dancer[1]);

        let sex = dancer[0];
        let name = dancer[1];
        if (sex === "F") {
            females.enqueue(new Dancer(name, sex));
        } else {
            males.enqueue(new Dancer(name, sex));
        }
    }
}

function dance(males, females) {
    console.log("The dance partners are: \n");
    while (!females.empty() && !males.empty()) {
        // # : 남자, 여자 댄서를 짝 짓고 공표한다.
        let person1 = females.dequeue();
        let person2 = males.dequeue();
        console.log(
            "Female dancer is: " + person1.name,
            "and the male dancer is: " + person2.name
        );
    }
}

let maleDancers = new Queue();
let femaleDancers = new Queue();
getDancers(maleDancers, femaleDancers);
dance(maleDancers, femaleDancers);
// if (!femaleDancers.empty()) {
//     console.log(femaleDancers.front().name + " is waiting to dance.");
// }
// if (!maleDancers.empty()) {
//     console.log(maleDancers.front().name + " is waiting to dance.");
// }
// # : 여기서는 얼마나 많은 수의 댄서가 기다리고 있는지 알 수 없다. 큐의 요소 수를 출력하는 함수를 추가한다.

function count() {
    return this.dataStore.length;
}

if (femaleDancers.count() > 0) {
    console.log(
        "There are " +
            femaleDancers.count() +
            " female dancers waiting to dance."
    );
}
if (maleDancers.count() > 0) {
    console.log(
        "There are " + maleDancers.count() + " male dancers waiting to dance."
    );
}

위의 텍스트 파일을 읽어와서 줄을 세운 뒤 짝을 지어 주었는데 M(남성) 3명이 남아있다고 공지한다.

 

 

5.4 큐로 데이터 정렬하기

큐를 이용하여 기수정렬을 구현할 수 있다. 기수정렬은 두 번의 과정을 거쳐 데이터를 정렬한다. 0~99 정수 데이터를 이용한다. 처음에는 1의 자리 숫자를 기준으로 숫자를 정렬하고 두 번째는 10의 자리 숫자를 기준으로 데이터를 정렬한다. 

 

function Queue() {
    this.dataStore = [];
    this.enqueue = enqueue;
    this.dequeue = dequeue;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
    this.count = count;
}

function enqueue(element) {
    this.dataStore.push(element);
}

function dequeue() {
    return this.dataStore.shift(); // 배열 앞부분에 저장된 요소를 삭제
}

function front() {
    return this.dataStore[0];
}

function back() {
    return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력
function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr += this.dataStore[i] + "\n";
    }
    return retStr;
}
// 큐가 비었는지 확인
function empty() {
    if (this.dataStore.length === 0) {
        return true;
    } else {
        return false;
    }
}

function count() {
    return this.dataStore.length;
}

// @ : 큐로 데이터 정렬하기, 기수 정렬, 1의 자리 기준으로 숫자 정렬 후 10의 자리 기준으로 숫자 정렬. 각 숫자당 1개의 큐이므로 9개의 큐가 필요하다.
function distribute(nums, queues, n, digit) {
    for (let i = 0; i < n; ++i) {
        if (digit === 1) {
            queues[nums[i] % 10].enqueue(nums[i]);
        } else {
            queues[Math.floor(nums[i] / 10)].enqueue(nums[i]);
        }
    }
}
// @ : 큐에 저장된 숫자를 수집하는 함수
function collect(queues, nums) {
    let i = 0;
    for (let digit = 0; digit < 10; ++digit) {
        while (!queues[digit].empty()) {
            nums[i++] = queues[digit].dequeue();
        }
    }
}

function dispArray(arr) {
    for (let i = 0; i < arr.length; ++i) {
        console.log(arr[i] + " ");
    }
}

let queues = [];
for (let i = 0; i < 10; ++i) {
    queues[i] = new Queue();
}
let nums = [];
for (let i = 0; i < 10; ++i) {
    nums[i] = Math.floor(Math.floor(Math.random() * 101));
}
console.log("Before radix sort: ");
dispArray(nums);
distribute(nums, queues, 10, 1);
collect(queues, nums);
distribute(nums, queues, 10, 10);
collect(queues, nums);
console.log("\n\nAfter radix sort: ");
dispArray(nums);

랜덤한 숫자를 넣어서 기수정렬된 결과를 보여준다.

 

 

5.5 우선순위 큐

보통 큐에서는 먼저 넣은 요소부터 삭제된다. 하지만 선입선출이 아니라 우선순위같은 다른 기준으로 요소를 삭제해야 하는 애플리케이션도 있다. 이럴 때 우선순위 큐를 사용해야 한다.

응급실에서는 환자의 상태를 평가해 우선순위 코드를 부여한다. 우선순위가 높은 코드를 받은 환자는 우선순위가 낮은 코드를 받은 환자보다 먼저 진료를 받는다. 하지만 같은 우선순위 코드인 경우 선입선출 규칙을 적용한다.

 

code는 우선순위를 나타내며 가장 높은 우선순위는 1, 2, 3, 4,,, 순서이다.(숫자가 낮을수록 우선순위는 높다)

dequeue 함수를 수정하여 우선순위가 가장 높은 코드를 찾는다.

 

function Queue() {
    this.dataStore = [];
    this.enqueue = enqueue;
    this.dequeue = dequeue;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
    this.count = count;
}

function enqueue(element) {
    this.dataStore.push(element);
}

function dequeue() {
    return this.dataStore.shift(); // 배열 앞부분에 저장된 요소를 삭제
}

function front() {
    return this.dataStore[0];
}

function back() {
    return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력
function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr += this.dataStore[i] + "\n";
    }
    return retStr;
}
// 큐가 비었는지 확인
function empty() {
    if (this.dataStore.length === 0) {
        return true;
    } else {
        return false;
    }
}

function count() {
    return this.dataStore.length;
}

// # : 우선순위 큐
// # : 예진 간호사가 환자 검사 >> 환자상태평가로 우선순위 코드 부여 >> 우선순위 높으면 먼저 진료받음(우선순위 코드가 같으면 선입선출)
function Patient(name, code) {
    this.name = name;
    this.code = code; // 우선순위 or 심각성
}
// # : 가장 높은 우선순위(1 > 2 > 3 > 4 > ,,,) 삭제
function dequeue() {
    let entry = 0;
    for (let i = 0; i < this.dataStore.length; ++i) {
        if (this.dataStore[i].code < this.dataStore[entry].code) {
            console.log(
                "deq",
                this.dataStore[i].code,
                this.dataStore[entry].code
            );

            entry = i;
            console.log("ent: ", entry);
        }
    }
    return this.dataStore.splice(entry, 1);
}
// # : 출력
function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr +=
            this.dataStore[i].name + " code: " + this.dataStore[i].code + "\n";
    }
    return retStr;
}
// # : work
let p = new Patient("Smith", 5);
let ed = new Queue();
ed.enqueue(p);
p = new Patient("Jones", 4);
ed.enqueue(p);
p = new Patient("Fehrenbach", 6);
ed.enqueue(p);
p = new Patient("Brown", 1);
ed.enqueue(p);
p = new Patient("Ingram", 1);
ed.enqueue(p);
console.log(ed.toString());
let seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());
// 다음 환자 치료
seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());
seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());

 

 

5.6 연습문제

# 1. Queue 클래스를 고쳐서 Deque 클래스를 만드시오. Deque는 큐와 비슷한 자료구조로 리스트의 앞부분과 끝부분 모두에서 요소의 삽입과 삭제가 일어난다. 프로그램을 이용해 구현한 Deque 클래스를 테스트하시오.

 

push_front 는 맨 앞 인덱스(0)에 요소를 추가하게끔 splice 메서드를 이용해 구현하였고 pop_back 은 length 프로퍼티를 이용해서 맨 뒤의 요소의 인덱스를 length-1로 가져와서 해당 위치의 요소를 1개 지우도록 splice 메서드를 이용해 구현하였다.

 

// # : # 1. Queue 클래스를 고쳐서 Deque 클래스를 만드시오.
// # : Deque는 큐와 비슷한 자료구조로 리스트의 앞부분과 끝부분 모두에서 요소의 삽입과 삭제가 일어난다.
// # : 프로그램을 이용해 구현한 Deque 클래스를 테스트하시오.
function Deque() {
    this.dataStore = [];
    this.push_front = push_front;
    this.push_back = push_back;
    this.pop_front = pop_front;
    this.pop_back = pop_back;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
}
// # :  push_front() : 맨 앞에 새로운 요소를 삽입한다.
// # :  push_back() : 맨 뒤에 새로운 요소를 삽입한다.
// # :  pop_front() : 맨 앞에 요소를 제거한다.
// # :  pop_back() : 맨 뒤에 요소를 제거한다.
// ! : splice(맨 앞 인덱스, 0, 추가하려는 요소)를 이용한다. 두 번째 인자의 길이만큼 삭제하지만 0이면 추가.
function push_front(element) {
    this.dataStore.splice(0, 0, element);
}
function push_back(element) {
    this.dataStore.push(element);
}
function pop_front() {
    return this.dataStore.shift(); // 배열 앞부분에 저장된 요소를 삭제
}
// ! : back함수에서 length-1을 사용하듯 맨 뒤의 요소에 대한 인덱스를 가져와서 해당 인덱스를 splice로 삭제한다.
function pop_back() {
    return this.dataStore.splice(this.dataStore.length - 1, 1); // 배열 앞부분에 저장된 요소를 1개 삭제
}

function front() {
    return this.dataStore[0];
}

function back() {
    return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력
function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr += this.dataStore[i] + "\n";
    }
    return retStr;
}
// 큐가 비었는지 확인
function empty() {
    if (this.dataStore.length === 0) {
        return true;
    } else {
        return false;
    }
}

let dq = new Deque();
dq.push_front("M");
dq.push_front("C");
dq.push_front("J");
console.log(dq.toString());
dq.pop_front();
console.log(dq.toString());
dq.pop_back();
console.log(dq.toString());
dq.push_back("A");
dq.push_back("B");
console.log(dq.toString());
console.log("Front of dequeue: " + dq.front());
console.log("Back of dequeue: " + dq.back());

 

 

# 2. 1번에서 구현한 Deque 클래스를 이용해 주어진 단어가 회문인지 검사하는 프로그램을 만드시오.

 

// # : # 2. 1번에서 구현한 Deque 클래스를 이용해 주어진 단어가 회문인지 검사하는 프로그램을 만드시오.
function Deque() {
    this.dataStore = [];
    this.push_front = push_front;
    this.push_back = push_back;
    this.pop_front = pop_front;
    this.pop_back = pop_back;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
}
function push_front(element) {
    this.dataStore.splice(0, 0, element);
}
function push_back(element) {
    this.dataStore.push(element);
}
function pop_front() {
    return this.dataStore.shift(); // 배열 앞부분에 저장된 요소를 삭제
}
function pop_back() {
    return this.dataStore.splice(this.dataStore.length - 1, 1); // 배열 앞부분에 저장된 요소를 1개 삭제
}
function front() {
    return this.dataStore[0];
}
function back() {
    return this.dataStore[this.dataStore.length - 1];
}
// # : 문자열이 한줄로 나오도록 수정
function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr += this.dataStore[i];
    }
    return retStr;
}
function empty() {
    if (this.dataStore.length === 0) {
        return true;
    } else {
        return false;
    }
}
function palindrome(str) {
    let dq = new Deque();

    for (let i = 0; i < str.length; ++i) {
        dq.push_front(str[i]);
    }
    console.log(dq.toString());
    if (str === dq.toString()) {
        console.log("회문입니다.");
    } else {
        console.log("회문 아닙니다.");
    }
}

palindrome("reaer");
palindrome("alsdjfalsdjf");
palindrome("racecar");
palindrome("hello");

 

 

# 3. 5.5의 우선순위 큐 예제에서 낮은 수가 아니라 높은 숫자를 높은 우선순위를 갖도록 프로그램을 고치시오. 테스트 프로그램으로 제대로 작동하는지 확인하시오.

 

function Queue() {
    this.dataStore = [];
    this.enqueue = enqueue;
    this.dequeue = dequeue;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
    this.count = count;
}

function enqueue(element) {
    this.dataStore.push(element);
}

function dequeue() {
    return this.dataStore.shift(); // 배열 앞부분에 저장된 요소를 삭제
}

function front() {
    return this.dataStore[0];
}

function back() {
    return this.dataStore[this.dataStore.length - 1];
}
// 모든 요소 출력
function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr += this.dataStore[i] + "\n";
    }
    return retStr;
}
// 큐가 비었는지 확인
function empty() {
    if (this.dataStore.length === 0) {
        return true;
    } else {
        return false;
    }
}

function count() {
    return this.dataStore.length;
}

// # : 우선순위 큐
// # : 예진 간호사가 환자 검사 >> 환자상태평가로 우선순위 코드 부여 >> 우선순위 높으면 먼저 진료받음(우선순위 코드가 같으면 선입선출)
function Patient(name, code) {
    this.name = name;
    this.code = code; // 우선순위 or 심각성
}
// ! : 가장 높은 우선순위(,,, > 4 > 3 > 2 > 1) 삭제
function dequeue() {
    let entry = 0;
    for (let i = 0; i < this.dataStore.length; ++i) {
        if (this.dataStore[i].code > this.dataStore[entry].code) {
            console.log(
                "deq",
                this.dataStore[i].code,
                this.dataStore[entry].code
            );

            entry = i;
            console.log("ent: ", entry);
        }
    }
    return this.dataStore.splice(entry, 1);
}
// # : 출력
function toString() {
    let retStr = "";
    for (let i = 0; i < this.dataStore.length; ++i) {
        retStr +=
            this.dataStore[i].name + " code: " + this.dataStore[i].code + "\n";
    }
    return retStr;
}
// # : work
let p = new Patient("Smith", 5);
let ed = new Queue();
ed.enqueue(p);
p = new Patient("Jones", 4);
ed.enqueue(p);
p = new Patient("Fehrenbach", 6);
ed.enqueue(p);
p = new Patient("Brown", 1);
ed.enqueue(p);
p = new Patient("Ingram", 1);
ed.enqueue(p);
console.log(ed.toString());
let seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());
// 다음 환자 치료
seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());
seen = ed.dequeue();
console.log("Patient being treated: " + seen[0].name);
console.log("Patients waiting to be seen: ");
console.log(ed.toString());

 

# 4. 사용자가 응급실의 활동을 제어할 수 있도록 응급실 예제(5.5)를 고치시오. 사용자가 다음과 같은 활동을 선택할 수 있도록 시스템 메뉴를 만들어 제공하시오.

a. 환자가 응급실에 들어옴.

 

b. 의사가 환자를 검사함.

 

c. 대기 환자 목록을 출력함.