210120_TIL (자료구조 - 해시테이블, 그래프)

🍎 오늘 배운 것

---

✔️ 해시테이블 (자료구조)
해시 테이블의 메서드 중 삽입, 삭제, 리사이징을 하는 메서드들을 페어분과 직접 코드로 작성해봤다. 처음에 해시테이블의 전반적인 구조를 생각하지 않고 무작정 코드를 작성하려해서 자꾸 오류가 났는데, 잠시 리프레시할 시간을 갖고 구조를 그림으로 그려보니 조금씩 감이 잡히기 시작했던 것 같다. 특히 bucket의 존재를 잊고있어서,, 많이 해맸던 것 같다. 통과는 됐지만 왜인지 잘 이해가 가지 않아서 초기화하고 처음부터 다시 작성해보니까 숲을 봤어야 했는데 나무를 보고있었다는걸 깨닫기도 했다. 자료구조는 꼭 그림으로 하나씩 그려보자..!

✔️ 그래프 (자료구조)
연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조인 그래프(Graph)에 대해 공부했다. 그림만 봤을때는 그냥  데이터들끼리 연결돼있는거구나 하고 간단하게 생각했는데, 방향성 여부에 따라서도 구분되고, 특히 구현하는 방식도 인접 리스트 방식과 인접 행렬방식 두가지로 나누어져서 알아봐야할게 많았다. 인접 리스트는 그래프 내에 간선이 많이 없는 희소그래프일 때 많이 사용하고, 간선이 많아 관계가 복잡할 때는 인접 행렬을 주로 사용한다고 한다. 그래프를 탐색하는 방법도 깊이에 중점을 두는지, 너비에 중점을 두는지에 따라 달라서 상황에 맞게 뭐가 더 효율적인지 잘 판단해서 쓰는게 정말 중요할 것 같다는 생각이 들었다. 

그림으로 그려본 해시테이블 구조

 

🍎 기억할 것

---

✔️ 해시 함수의 세 가지 조건
1) 같은 key → (해시함수) → 같은 해시값 : 일관성
2) 다른 key → (해시함수) → 다른 해시값
3) 배열크기를 알 것 (유효한 인덱스만 반환) 

✔️ 해시테이블의 시간복잡도 (Big-O)
삽입, 삭제 : 평균 O(1), 최악 O(n)
검색 : 평균 O(1), 최악 O(n)
리사이징 : O(n)

 

🍎 더 공부할 것

---

✔️ 트리구조 (Tree)
✔️ 이진 탐색 트리 (Binary Search Tree)