Data structures & Algorithms with JavaScripts 스터디 8일차

210508 토요일 8일차

# 5~7일차 복습

- 리스트는 위치를 가리키는 프로퍼티(front, end)가 있다.

 

- next() 함수로 리스트의 현재 요소에서 다음 요소로 이동할 수 있다.

 

- prev() 함수로 현재 요소에서 이전 요소로 이동할 수 있다.

 

- moveTo(n) 함수를 이용하면 n 번째 위치로 한 번에 이동할 수 있다.

 

- currPos() 함수는 리스트의 현재 위치를 가리킨다.

 

- List 클래스 구현

생성자 함수

function List() {
    this.listSize = 0;
    this.pos = 0;
    this.dataStore = [];
    this.clear = clear;
    this.find = find;
    this.toString = toString;
    this.insert = insert;
    this.append = append;
    this.remove = remove;
    this.front = front;
    this.end = end;
    this.prev = prev;
    this.next = next;
    this.length = length;
    this.currPos = currPos;
    this.moveTo = moveTo;
    this.getElement = getElement;
    this.contains = contains;
}

 

- Append : 리스트에 요소 추가(listSize 위치에 요소를 추가한다.)

function append(element) {
    this.dataStore[this.listSize++] = element;
}

 

- Find : 리스트의 요소 검색(length 함수 필요, 인덱스 값 반환)

function find(element) {
    for (let i = 0; i < this.dataStore.length; ++i) {
        if (this.dataStore[i] == element) {
            return i;
        }
    }
    return -1;
}

 

- Remove : 리스트의 요소 삭제

// remove() : find()의 반환값을 splice 함수에 넘겨주어 원하는 요소를 삭제한 다음 dataStore 배열을 연결한다. 요소를 삭제하면 true, 못하면 false 반환
function remove(element) {
    let foundAt = this.find(element);
    if (foundAt > -1) {
        this.dataStore.splice(foundAt, 1);
        --this.listSize;
        return true;
    }
    return false;
}

(splice의 두 번째 인자에 0을 주면 요소 추가, 1 이상은 숫자만큼 요소를 삭제한다.)

 

- Length : 리스트의 요소 개수

function length() {
    return this.listSize;
}

 

- toString : 리스트의 요소 확인

function toString(){
	return this.dataStore;
}

 

- Insert : 리스트에 요소 삽입(기존 요소 뒤에 새로운 요소 삽입. find로 기존 요소의 위치를 찾아 수행한다.)

function insert(element, after) {
    let insertPos = this.find(after);
    if (insertPos > -1) {
        this.dataStore.splice(insertPos + 1, 0, element);
        ++this.listSize;
        return true;
	}
    return false;
}

 

- clear : 배열을 삭제한 다음 빈 배열을 다시 만든다. listSize, pos도 0으로 초기화한다.

function clear() {
    delete this.dataStore;
    this.dataStore.length = 0;
    this.listSize = this.pos = 0;
}

 

- contains : 리스트에 특정 값이 있는지 판단(true, false)

function contains(element) {
    for (let i = 0; i < this.dataStore.length; ++i) {
        if (this.dataStore[i] == element) {
            return true;
        }
    }
    return false;
}

 

- iterator : List 클래스의 내부 저장소를 직접 참조하지 않고 리스트를 탐색할 수 있다. front, end, prev, next, currPos를 이용해 구현할 수 있다. 

배열의 인덱스에 비해 장점은 아래와 같다.

• 리스트 요소에 접근할 때 내부 데이터 저장소가 무엇인지 걱정할 필요가 없다.
• 리스트에 새 요소를 추가했을 때 현재 인덱스가 쓸모 없는 값이 되는 반면 반복자를 이용하면 리스트가 바뀌어도 반복자를 갱신할 필요가 없다.
• List 클래스에 사용하는데이터 저장소의 종류가 달라져도 이전과 같은 방식으로 요소에 접근할 수 있다.

for (names.front(); names.currPos() < names.length(); names.next()) {
    console.log(names.getElement);
}

현재 위치를 리스트 앞으로 설정(front())한다. 그리고 currPos() 가 리스트 길이보다 작을 때 루프를 반복한다. 루프를 돌 때마다 next()로 한 요소씩 전진한다.

 

 

CH3 리스트

3.5 연습문제

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

 

# 구현

현재 리스트보다 모든 요소가 클 때만 요소를 삽입하는 함수이므로 모든 요소를 탐색하는 함수가 필요하다고 생각했다.

find 함수는 삽입(추가가 아니라 삽입이라고 했으므로 insert() 함수)을 위해 추가해두었다.

모든 요소보다 삽입하려는 요소가 큰지 확인하여 끝까지 확인했을 때 return true를 반환하고 중간에 삽입하려는 요소보다 큰 요소가 존재할 경우 false를 리턴하는 함수 bigger()을 구현했다.

 

bigger() 함수 구현

 

insertBigger() 함수 구현

// # : 현재 리스트의 모든 요소보다 클 때만 요소를 삽입하는 함수를 구현하시오. 여기서 크다는 의미는 숫자일 때는 크기를 비교하고, 텍스트일 때는 알파벳순으로 나중을 의미한다.
function List() {
    this.listSize = 0;
    this.pos = 0;
    this.dataStore = [];
    this.append = append;
    this.length = length;
    this.find = find;
    this.insertBigger = insertBigger;
}

function length() {
    return this.listSize;
}

function append(element) {
    this.dataStore[this.listSize++] = element;
}

function find(element) {
    for (let i = 0; i < this.dataStore.length; ++i) {
        if (this.dataStore[i] == element) {
            return i;
        }
    }
    return -1;
}

let nums = new List();
nums.append(1);
nums.append(2);
nums.append(3);
nums.append(4);
nums.append(5);
nums.append(6);

function bigger(element) {
    for (let i = 0; i < this.dataStore.length; ++i) {
        console.log(this.dataStore[i], element);

        if (this.dataStore[i] >= element) {
            return false;
        }
    }
    return true;
}

function insertBigger(element, after) {
    // 삽입 함수이므로 insert와 비슷한 구조
    if (bigger(element)) {
        let insertPos = this.find(after);
        if (insertPos > -1) {
            this.dataStore.splice(insertPos + 1, 0, element);
            ++this.listSize;

            return;
        }
    } else {
        console.log(
            "fail : 리스트의 요소 중에 해당 요소보다 큰 요소가 존재합니다. "
        );

        return;
    }
}
nums.insertBigger(7, 2);
console.log(nums.dataStore);

 

여기서 텍스트일 경우 알파벳 순으로 나중인 것으로 판단해야 하므로 우선 텍스트인지 숫자인지를 구별할 함수를 구현하였다.

function check(num) {
    if (isNaN(num) == true) {
        return true;
    } else {
        return false;
    }
}

check() 함수에는 isNaN 메소드를 사용하였는데 Not-a-Number라는 뜻으로 숫자가 아닌 경우 true를 반환해준다.

그런데 sort() 함수의 경우에는 compare() 함수를 두어 숫자 비교를 수행해야 제대로 정렬이 되는 것과 혼동하여 비교연산자로 비교하는 경우에는 문자열은 알파벳순으로, 숫자는 숫자 크기순으로 비교해준다는 것을 뒤늦게 알게 되었다.

check() 함수를 따로 추가할 필요가 없어졌고 아래와 같이 함수를 구현하였다.

 

# 전체 코드

// # : 현재 리스트의 모든 요소보다 클 때만 요소를 삽입하는 함수를 구현하시오. 여기서 크다는 의미는 숫자일 때는 크기를 비교하고, 텍스트일 때는 알파벳순으로 나중을 의미한다.
function List() {
    this.listSize = 0;
    this.pos = 0;
    this.dataStore = [];
    this.append = append;
    this.length = length;
    this.find = find;
    this.bigger = bigger;
    this.insertBigger = insertBigger;
}

function length() {
    return this.listSize;
}

function append(element) {
    this.dataStore[this.listSize++] = element;
}

function find(element) {
    for (let i = 0; i < this.dataStore.length; ++i) {
        if (this.dataStore[i] == element) {
            return i;
        }
    }
    return -1;
}

function bigger(element) {
    for (let i = 0; i < this.dataStore.length; ++i) {
        console.log(this.dataStore[i], element);

        if (this.dataStore[i] >= element) {
            return false;
        }
    }
    return true;
}

function insertBigger(element, after) {
    if (this.bigger(element)) {
        let insertPos = this.find(after);
        if (insertPos > -1) {
            this.dataStore.splice(insertPos + 1, 0, element);
            ++this.listSize;
            console.log("리스트 요소 삽입 성공!");
            return;
        }
    } else {
        console.log(
            "fail : 리스트의 요소 중에 해당 요소보다 큰 요소가 존재합니다. "
        );
        return;
    }
}
// # : 숫자인 경우
let nums = new List();
nums.append(1);
nums.append(2);
nums.append(3);
nums.append(4);
nums.append(5);
nums.append(6);
nums.insertBigger(2, 2);
console.log(nums.dataStore);

// # : 텍스트인 경우
let names = new List();
names.append("C");
names.append("R");
names.append("Cy");
names.append("J");
names.append("B");
names.append("D");
names.insertBigger("A", "B");
console.log(names.dataStore);

 

 

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

모든 요소보다 작을 때이므로 비교연산자를 반대로 바꾸어 아래처럼 구현하였다.

 

# 전체 코드

function List() {
    this.listSize = 0;
    this.pos = 0;
    this.dataStore = [];
    this.append = append;
    this.length = length;
    this.find = find;
    this.smaller = smaller;
    this.insertSmaller = insertSmaller;
}

function length() {
    return this.listSize;
}

function append(element) {
    this.dataStore[this.listSize++] = element;
}

function find(element) {
    for (let i = 0; i < this.dataStore.length; ++i) {
        if (this.dataStore[i] == element) {
            return i;
        }
    }
    return -1;
}

function smaller(element) {
    for (let i = 0; i < this.dataStore.length; ++i) {
        console.log(this.dataStore[i], element);

        if (this.dataStore[i] <= element) {
            return false;
        }
    }
    return true;
}

function insertSmaller(element, after) {
    if (this.smaller(element)) {
        let insertPos = this.find(after);
        if (insertPos > -1) {
            this.dataStore.splice(insertPos + 1, 0, element);
            ++this.listSize;
            console.log("리스트 요소 삽입 성공!");
            return;
        }
    } else {
        console.log(
            "fail : 리스트의 요소 중에 해당 요소보다 작은 요소가 존재합니다. "
        );
        return;
    }
}
// # : 숫자인 경우
let nums = new List();
nums.append(1);
nums.append(2);
nums.append(3);
nums.append(4);
nums.append(5);
nums.append(6);
nums.insertSmaller(2, 2);
console.log(nums.dataStore);

// # : 텍스트인 경우
let names = new List();
names.append("C");
names.append("R");
names.append("Cy");
names.append("J");
names.append("B");
names.append("D");
names.insertSmaller("A", "B");
console.log(names.dataStore);

 

 

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

리스트 내부는 데이터 저장소가 배열로 되어있기 때문에 ch2에서 배웠던 배열 함수중에 filter를 이용해서 원하는 객체 요소를 포함하는 배열만을 반환하도록 생각했다. (filter는 주어진 조건을 통과하는 모든 요소를 모아 배열로 반환한다.)

// # : 사람의 이름과 성별을 저장하는 Person 클래스를 구현하시오. 최소한 10개의 Person 객체를 포함하는 리스트를 만드시오. 리스트에서 같은 성별을 가진 사람을 모두 출력하는 함수를 구현하시오.
function List() {
    this.listSize = 0;
    this.dataStore = [];
    this.append = append;
    this.length = length;
    this.sameSex = sameSex;
}

function length() {
    return this.listSize;
}

function append(element) {
    this.dataStore[this.listSize++] = element;
}

let persons = new List();

persons.append({ name: "F", sex: "female" });
persons.append({ name: "G", sex: "female" });
persons.append({ name: "H", sex: "female" });
persons.append({ name: "I", sex: "female" });
persons.append({ name: "J", sex: "female" });
persons.append({ name: "A", sex: "male" });
persons.append({ name: "B", sex: "male" });
persons.append({ name: "C", sex: "male" });
persons.append({ name: "D", sex: "male" });
persons.append({ name: "E", sex: "male" });

function sameSex(sex) {
    return this.dataStore.filter((x) => {
        if (x.sex === sex) {
            return x;
        }
    });
}

console.log(persons.sameSex("female"));
console.log("\n");
console.log(persons.sameSex("male"));

 

 

CH4 스택

리스트는 특히 데이터 저장 순서가 중요하지 않거나, 저장된 데이터를 검색할 필요가 없을 때 요긴하다. 일부 어플리케이션에서는 일반 리스트보다 좀 더 복잡한 자료구조가 필요할 때가 있다.

리스트와 비슷하지만 더 다양한 문제를 해결할 수 있는 스택은 가장 윗부분에서만 자료의 추가/삭제가 일어나므로 실행속도가 빠르고 구현이 쉬운 효율적인 자료구조다. 

 

4.1 스택 동작

스택은 요소 리스트로 구성되며 Top이라 불리는 한쪽 끝으로만 요소에 접근할 수 있다. 후입선출(Last-In, First-Out)이다. 

후입선출이라는 특성 때문에 밑바닥에 있는 요소에 접근하려면 모든 요소를 제거하는 수 밖에 없다.

 

보통 스택은 Top에 있는 요소를 확인하는 기능도 제공한다. pop으로도 확인할 수 있지만 요소를 꺼내기 때문이다. peek으로 요소를 제거하지 않고 내용만 확인한다. 

clear 프로퍼티는 스택의 모든 요소를 제거한다. length는 포함된 요소의 수를 저장한다. empty는 스택에 요소가 있는지 여부를 알려준다.(length로도 확인할 수 있다.)

 

4.2 스택 구현

function Stack() {
    this.dataStore = [];
    this.top = 0;
    this.push = push;
    this.pop = pop;
    this.peek = peek;
    this.clear = clear;
    this.length = length;
}

function push(element) {
    // this.top++이므로 요소 추가후 top을 1 증가시킨다.
    this.dataStore[this.top++] = element;
}
// 반환하고 top 변수값을 감소시킨다.
function pop() {
    return this.dataStore[--this.top];
}
// this.top-1이면 가장 우측(스택상 맨위)의 요소를 가리킨다.
function peek() {
    return this.dataStore[this.top - 1];
}

function length() {
    return this.top;
}

function clear() {
    this.top = 0;
}

let s = new Stack();
s.push("D");
s.push("R");
s.push("B");
console.log("length: " + s.length());
console.log(s.peek());
let popped = s.pop();
console.log("The popped element is : " + popped);
console.log(s.peek());
s.push("C");
console.log(s.peek());
s.clear();
console.log("length: " + s.length());
console.log(s.peek());
s.push("C");
console.log(s.peek());

 

peek() 함수는 top-1 위치의 요소에 접근해 스택의 탑 요소를 반환한다. (만약 스택의 요소가 3개라면 top(length)은 3일 것이고 위 코드에 따르면 배열의 가장 오른쪽 값이 가장 윗 값으로 볼 수 있다. peek()을 보면 this.top -1 의 인덱스에서 내용을 확인하고 있는데 실제 요소의 개수가 3이라면 가장 오른쪽(스택으로는 맨 위)에 있는 요소를 확인하기 위해서 this.top-1로 지정한 것이다.

 

 

4.3 Stack  클래스 이용하기

4.3.1 진법 변환

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;

 

 

NOTE : 이 알고리즘은 2진수 ~ 9진수 사이에서만 작동한다.

 

function Stack() {
    this.dataStore = [];
    this.top = 0;
    this.push = push;
    this.pop = pop;
    this.peek = peek;
    this.clear = clear;
    this.length = length;
}

function push(element) {
    // this.top++이므로 요소 추가후 top을 1 증가시킨다.
    this.dataStore[this.top++] = element;
}
// 반환하고 top 변수값을 감소시킨다.
function pop() {
    return this.dataStore[--this.top];
}
// this.top-1이면 가장 우측(스택상 맨위)의 요소를 가리킨다.
function peek() {
    return this.dataStore[this.top - 1];
}

function length() {
    return this.top;
}

function clear() {
    this.top = 0;
}

function mulBase(num, base) {
    let s = new Stack();
    do {
        s.push(num % base);
        num = Math.floor((num /= base));
    } while (num > 0);
    let converted = "";
    while (s.length() > 0) {
        converted += s.pop();
    }
    return converted;
}

let num = 32;
let base = 2;
let newNum = mulBase(num, base); // 32를 2진법으로 변환하겠다.
console.log(num + " converted to base " + base + " is " + newNum);
num = 125;
base = 8;
newNum = mulBase(num, base); // 125를 8진법으로 변환하겠다.
console.log(num + " converted to base " + base + " is " + newNum);

 

 

4.3.2. 회문

"racecar"나 "A man, a plan, a canal: Panama"(구두점 무시), 1001 등이 회문이다. 

스택을 이용하면 원래 문자열을 역순으로, 마지막 문자는 스택의 Top에, 첫 문자는 스택의 Bottom에 위치한다. 

 

스택에 문자열을 모두 추가했으면

=>

for (let i = 0; i < word.length; ++i) {

s.push(word[i]);

}

 

각 문자를 다시 꺼내 새 문자열을 만들 수 있다.

=>

    while (s.length() > 0) {
        rword += s.pop();
    }

 

이렇게 역순으로 바뀐 문자열과 원래 문자열을 비교한다. 비교 결과가 같으면 문자열은 회문이다. 

=>

if (word == rword) {
        return true;
    } else {
        return false;
    }

 

function Stack() {
    this.dataStore = [];
    this.top = 0;
    this.push = push;
    this.pop = pop;
    this.peek = peek;
    this.clear = clear;
    this.length = length;
}
function push(element) {
    this.dataStore[this.top++] = element;
}
function pop() {
    return this.dataStore[--this.top];
}
function peek() {
    return this.dataStore[this.top - 1];
}
function length() {
    return this.top;
}
function clear() {
    this.top = 0;
}

function isPalindrome(word) {
    let s = new Stack();
    for (let i = 0; i < word.length; ++i) {
        s.push(word[i]);
    }
    let rword = "";
    while (s.length() > 0) {
        rword += s.pop();
    }
    if (word == rword) {
        return true;
    } else {
        return false;
    }
}

let word = "hello";
if (isPalindrome(word)) {
    console.log(word + " is a palindrome");
} else {
    console.log(word + " is not palindrome");
}
word = "racecar";
if (isPalindrome(word)) {
    console.log(word + " is a palindrome");
} else {
    console.log(word + " is not palindrome");
}

 

 

4.3.3. 재귀

스택을 이용해 재귀 프로세스를 흉내낼 수 있다. 팩토리얼 함수의 재귀 구현을 이용해 어떻게 스택으로 재귀를 구현하는지 확인할 수 있다. 

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

console.log(factorial(5));

 

스택 이용 : 5부터 1을 스택으로 추가한다.

=>

    while (n > 1) {
        s.push(n--);
    }

루프를 돌면서 각 숫자를 꺼내 결과를 곱해가면 120이 나온다.

=> 

let product = 1;
    while (s.length() > 0) {
        product += s.pop();
    }
    return product;

 

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

function Stack() {
    this.dataStore = [];
    this.top = 0;
    this.push = push;
    this.pop = pop;
    this.length = length;
}
function push(element) {
    this.dataStore[this.top++] = element;
}
function pop() {
    return this.dataStore[--this.top];
}
function length() {
    return this.top;
}

function fact(n) {
    let s = new Stack();
    while (n > 1) {
        s.push(n--);
    }
    let product = 1;
    while (s.length() > 0) {
        product *= s.pop();
    }
    return product;
}

console.log(factorial(5));
console.log(fact(5));