[내일배움캠프_spring] 3주차_알고리즘(~3-9)

실시간 강의로 객체지향 프로그래밍 강의를 들음. 소프트웨어의 가치는 변화가 가능한지에 달려있다는데..변화가 필요 없는 소프트웨어는 실패한 소프트웨어라는 점이 인상깊었다..나머지는 너무 어려웠음

---

11.17
***객체지향 프로그래밍 강의

***알고리즘
3-7.해쉬-1
*해쉬 테이블 : 컴퓨터에서 키를 값어 매핑할 수 있는 구조인, 연관 배열 추가에 사용되는 자료 구조이다. 해시 함수를 사용하여 색인(index)을 버킷(bucket)이나 슬롯(slot)의 배열로 게산, 데이터를 다루는 기법 중 하나로 데이터 "검색과 저장"이 아주 빠르게 진행
-딕셔너리 = 해쉬테이블
-키를 통해 바로 데이터를 받아올 수 있으므로 속도가 획기적으로 빨라진다.
-임의의 길이를 갖는 메시지를 입력하여 고정된 길이의 값이 

*충돌
: 같은 어레이의 인덱스로 매핑이 되어서 데이터를 덮어 써버리는 결과가 발생
-해결방법
링크드리스트 : 체이닝(chaining)이라고 함 / 링크드리스트를 이용해서 테스트를 늘리자!(노드로 이어주자), key값을 저장해주어야 함(나중에 찾아야 하기 때문에,,)

class LinkedTuple:
    def __init__(self):
        self.items = list()

    def add(self, key, value):
        self.items.append((key, value))   # key와 value를 가지고 있는  Tuple을 넣어준다.

    def get(self, key):  # Tuple내에서 값을 찾기 위해서는 키가 또 하나 필요하다.
        for k, v in self.items:
            if key == k:
                return v

class LinkedDict:
    def __init__(self):
        self.items = []
        for i in range(8):
            self. items.append(LinkedTuple())

    def put(self, key, value):
        index = hash(key) % len(self.items)
        self.items[index].add(key, value)
        return

    def get(self, key):
        index = hash(key) % len(self.items)

        return self.items[index].get(key)

3-8.해쉬-2
*출석체크 문제

all_students = ["나연", "정연", "모모", "사나", "지효", "미나", "다현", "채영", "쯔위"]
present_students = ["정연", "모모", "채영", "쯔위", "사나", "나연", "미나", "다현"]

# all_students 에서 present_students의 내용을 빼주면 출석하지 않은 학생의 이름만 남는다!

def get_absent_student(all_array, present_array):
    # 구현해보세요!
    student_dict = {}
    for key in all_array:  # 시간복잡도O(N)
        student_dict[key] = True  # 공간복잡도 O(N)

    for key in present_array:
        del student_dict[key]  # del : 제거해 주는 함수

    for key in student_dict.keys():
        return key


print(get_absent_student(all_students, present_students))

-->해쉬함수는 시간복잡도는 최소화 할 수 있지만 공간복잡도가 크다.

3-9.끝 & 숙제설명
HOMEWORK