자료구조와 알고리즘

1. 여러분은 교실의 학생 정보를 저장하고 열람할 수 있는 관리 프로그램을 개발하려고 합니다. 이 때 여러분이라면 학생의 정보를 저장하기 위한 자료구조를 어떤 걸 선택하실 건가요? 이유를 함께 적어주세요.

해시테이블을 사용

키 - 값 구조로 되어있기 때문에 학생의 번호, 이름을 키로 설정하면 O(1)로 조회 할 수 있음
새로운 학생을 추가하거나 삭제하기 쉬움

2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다.

주문은 들어온 순서대로 처리됩니다.

이 때 여러분이라면 어떤 자료구조를 선택하실 건가요?

이유를 함께 적어주세요.

큐를 선택

주문이 들어온 순서대로 처리되어야 하기 때문에 선입선출의 기능을 가지고 있는 큐를 사용

3. 우리가 구현한 스택은 0번 인덱스, 즉 입구쪽으로 데이터가 삽입되고 나오는 구조입니다. 반대로 마지막 인덱스, 즉 출구쪽으로 데이터가 삽입되고 나오는 구조로 코드를 변경해주세요.

class Node {
    constructor(data, next = null) {
        this.data = data;
        this.next = next;
    }
}

class Stack {
    constructor() {
        this.head = null;
        this.count = 0;
    }

    isEmpty() {
        return this.count === 0;
    }

    getLastNode() {
        if (this.isEmpty()) return null;

        let current = this.head;
        while (current.next !== null) {
            current = current.next;
        }
        return current;
    }

    push(data) {
        let newNode = new Node(data);

        if (this.head === null) {
            this.head = newNode;
        } else {
            let lastNode = this.getLastNode();
            lastNode.next = newNode;
        }
        this.count++;
    }

    pop() {
        if (this.isEmpty()) {
            throw new Error("스택이 비어있습니다.");
        }

        if (this.count === 1) {
            let deletedData = this.head.data;
            this.head = null;
            this.count--;
            return deletedData;
        }

        let current = this.head;
        while (current.next.next !== null) {
            current = current.next;
        }

        let deletedData = current.next.data;
        current.next = null;
        this.count--;

        return deletedData;
    }

    peek() {
        if (this.isEmpty()) {
            throw new Error("스택이 비어있습니다.");
        }
        return this.getLastNode().data;
    }

    printAll() {
        let current = this.head;
        let result = "[";
        while (current !== null) {
            result += current.data;
            current = current.next;
            if (current !== null) result += ", ";
        }
        result += "]";
        console.log(result);
    }
}

4. 해시테이블의 성능은 해시 함수에 따라 달라집니다.

수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다.

이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요.

힌트: charCodeAt() 함수를 이용

예시:

name1 = "이운재";

name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력

hashFunction(name){

}

수정한 코드

function hashFunction(name, hahSize = 100) {
    let hash = 0;
    for (let i = 0; i < name.length; i++) {
        hash += name.charCodeAt(i); 
    return hash % hashSize; 
}