[인프런 워밍업 클럽 CS 3기] 1주차 자료구조 미션

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

학생 정보의 조회와 데이터 수정은 빈번히 발생할 수 있다.
학생의 전학이 빈번하지 않다면, 데이터의 삽입 및 추가가 자주 발생하지 않을 것이다.

교실 내의 학생 수가 고정된다는 가정하에 데이터의 조회와 수정의 성능이 좋은 배열을 사용하는 것이 좋을 것 같다.
단, 전학이 빈번하게 발생한다면 배열이 아닌 연결리스트를 사용하는 것이 좋다.
또한 학생의 출석번호를 key로 하는 해시테이블 사용을 고려해봐도 괜찮을 것 같다.

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

들어온 순서대로 작업이 처리되는 구조를 가진 Queue를 선택할 것이다.

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

import sys
import os

sys.path.append(os.path.abspath(os.path.join(os.path.dirname(__file__), "..", "linkedlist")))

from linked_list import LinkedList

class Stack:
    def __init__(self):
        self.stack = LinkedList()

    def push(self, data):
        self.stack.insert_last(data)

    def pop(self):
        try:
            return self.stack.delete_last()
        except AttributeError:
            return None

    def peek(self):
        return self.stack.get_node_at(last)

    def is_empty(self):
        return self.stack.count == 0

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

⁉ charCodeAt() 메서드란?

String 값의 charCodeAt() 메서드는 주어진 인덱스의 UTF-16 코드 단위를 표현하는 0과 65535 사이의 정수를 반환합니다.
https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/String/charCodeAt

즉, 매개변수 인덱스(default=0)의 문자를 아스키코드로 변환하여 반환하는 메서드이다.

console.log("a".charCodeAt()); // 97
console.log("A".charCodeAt()); // 65
console.log("박예은".charCodeAt(0)); // 48149
console.log("박예은".charCodeAt(1)); // 50696
console.log("박예은".charCodeAt(2)); // 51008

charCodeAt 메서드를 사용하여 hash 함수를 구현하면 아래와 같다.

function hashFunction(name, size) {
  let hashValue = 0;
  for (let index = 0; index < name.length; index++) {
    hashValue += name.charCodeAt(i);
  }
  return hashValue % size;
}

해시 충돌을 줄이기 위해서 곱셈이나 시프트 연산을 추가하는 방식도 고려할 수 있다.

python에서는 ord() 함수를 통해 문자를 아스키코드로 변환할 수 있다.

  def hash(self, name):
      hash_value = 0

      for char in name:
          hash_value += ord(char)
      return hash_value % len(self.array)

이전의 main문의 key - value를 바꿔서 확인해보았다.

from hash_table import HashTable

if __name__ == "__main__":
    map = HashTable()

    map.set("정현우", 13);
    map.set("푸이그", 66);
    map.set("카디네스", 4);
    map.set("이주형", 2);
    map.set("송성문", 24);
    map.set("최주환", 53);
    map.set("김동엽", 38);
    map.set("전태현", 97);
    map.set("김건희", 12);
    map.set("김태진", 1);

    print("250308 키움 히어로즈 선발선수 해시테이블")
    for index in range(10):
        values = map.array[index]
        node = values.head
        print(index, end=" : ")
        while node:
            print(str(node.data.key) + "의 등번호 : " + str(node.data.value), end=" ➡ ")
            node = node.next
        print("None")

    print()
    print("이주형 등번호: ", map.get("이주형"))
    print("김혜성 등번호: ", map.get("김혜성"))
    print("정현우 등번호: ", map.get("정현우"))

    print()
    print("선발투수(정현우) 제거")
    map.remove("정현우")
    print("정현우 등번호: ", map.get("정현우"))

250308 키움 히어로즈 선발선수 해시테이블
0 : 전태현의 등번호 : 97 ➡ None
1 : None
2 : None
3 : 정현우의 등번호 : 13 ➡ None
4 : 김건희의 등번호 : 12 ➡ 김동엽의 등번호 : 38 ➡ 송성문의 등번호 : 24 ➡ 카디네스의 등번호 : 4 ➡ None
5 : None
6 : 최주환의 등번호 : 53 ➡ None
7 : 이주형의 등번호 : 2 ➡ None
8 : 김태진의 등번호 : 1 ➡ 푸이그의 등번호 : 66 ➡ None
9 : None

이주형 등번호:  2
김혜성 등번호:  None
정현우 등번호:  13

선발투수(정현우) 제거
정현우 등번호:  None