자료구조

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

    

   해시 테이블을 이용할 것 같습니다. 해시 테이블의 경우 데이터의 삽입, 삭제, 접근, 수정이 O(1)의 성능을 가지기 때문에 매우 빠르지만 좋은 해시함수를 선정할 필요가 있으며 공간 효율성이 낮습니다. 하지만 교실의 학생 수는 많아봐야 40명이기에 메모리 공간을 크게 걱정하지 않아도 되며 학생번호를 순서대로 부여받기 때문에 간단한 해시 함수를 사용해도 해시 테이블 내의 key에 value가 고르게 분배될 것입니다. 또한 앞서 적었듯이 해시 테이블은 데이터 접근, 삽입, 삭제가 굉장히 빠르기 때문에 전학같은 이슈 발생 시에도 유연하게 대처가 가능합니다.

    

2. 여러분은 고객의 주문을 받는 프로그램을 개발하려고 합니다. 주문은 들어온 순서대로 처리됩니다. 이 때 여러분이라면 어떤 자료구조를 선택하실 건가요? 이유를 함께 적어주세요.

    

   FIFO의 특징을 가지는 Queue를 사용할 것입니다. DoublyLinkedList를 이용하면 Stack, Queue, Deque, hashTable을 비교적 쉽게 적용할 수 있으므로 구현은 DoublyLinkedList를 기반으로 하는 것이 좋을 것 같습니다.

    

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

   import { LinkedList } from '../LinkedList/linked_list.mjs';
   
   class Stack {
     constructor() {
       this.LinkedList = new LinkedList();
     }
   
     /**
      * 스택에 데이터 삽입
      * @param {number} data
      */
     push(data) {
       this.LinkedList.insertLast(data);
     }
   
     /**
      * 스택에서 데이터를 삭제하고 반환
      * @returns {Node}
      */
     pop() {
       try {
         return this.LinkedList.deleteLast();
       } catch (error) {
         return null;
       }
     }
   
     /**
      * 스택의 맨 위 데이터를 반환
      * @returns {Node}
      */
     peek() {
       return this.LinkedList.getNodeAt(0);
     }
   
     /**
      * 스택이 비어있는지 확인
      * @returns {boolean}
      */
     isEmpty() {
       return this.LinkedList.count == 0 ? true : false;
     }
   }
   
   export { Stack };
   
   

    

4. 해시테이블의 성능은 해시 함수에 따라 달라집니다. 수업 시간에 등번호를 이용해 간단한 해시 함수를 만들어봤습니다. 이번엔 등번호가 아닌 이름을 이용해 데이터를 골고루 분산시키는 코드로 수정해주세요. 힌트: charCodeAt() 함수를 이용 예시: name1 = "이운재"; name1.charCodeAt(0); // 51060 이운재의 0번 인덱스 ‘이’의 유니코드 출력

   hashFunction(input){
   	let changed = input.charCodeAt(0) + input.charCodeAt(1);
   	
   	return changed % 5;
   }
   
   /* 결과값
     4
     0
     2
     3
     2
     0
     4
     2
     3
     0
     1
   */