바닐라코딩 2주차 정리

강의

이번주의 강의 내용은 자료구조였습니다. 

Stack
-First In Last Out
- 삽입: O(1)
- 삭제: O(1)
- 조회: O(n)
- 사용처: 브라우저의 앞/뒤로가기기능, 자바스크립트의 콜스택 등등...

Queue
-First In First Out
- 삽입: O(1)
- 삭제: O(1)
- 조회: O(n)
- 사용처: 대기줄, 자바스크립트의 콜백큐 등등...

Linked List
- 삽입: O(1)
- 삭제: O(1) *여기서 말하는 삭제는 원하는 값을 '조회' 후 삭제하는것이 아니라 말그대로 해당 노드를 삭제 하는 행위만을 의미 합니다. 
- 조회: O(n)
- 사용처:  해시테이블의 충돌 해결법, 웹브라우저의 히스토리 저장방식 등등..

Hash Table
- 삽입: O(1) 
- 삭제: O(1)
- 조회: O(1)
- 해시충돌이 자주 일어나는 경우 삽입 삭제 조회 전부 O(n)까지 늘어날 수 있습니다. => 최적화된 해시 함수를 쓰는 것이 중요합니다.
- 해시충돌의 해결법으로는 Separate Chining(i.e. 동일 인덱스의 연결리스트에 키-값을 저장), Linear Probing(i.e.충돌한 해시값에 다음값으로 값 지정)등이 있습니다. 
- 사용처: 전화번호부, 블록체인, 사전 등등...

Tree

-노드와 간선으로 구성된 자료구조입니다.
-사용처: DOM트리, 부모자식의 관계가 필요한 자료구조 등등...

Binary Search Tree
- 부모노드의 왼쪽에는 항상 부모노드보다 작은 값이, 오른쪽에는 항상 큰값이 삽입되는 자료구조입니다. 
- 삽입: O(logn) 
- 삭제: O(logn) 
- 조회: O(logn) 
- 트리가 편향된(Skewed)된 형태로 구성될 경우 (i.e. 루트 노드보다 큰값만 계속 삽입되거나, 작은값만 계속삽입되면...) => 삽입, 삭제, 조회 전부 최악의 경우 O(n)의 시간 복잡도를 지닙니다. 
- 이러한 단점을 해결하기 위해 균형을 자동으로 잡는 알고리즘을 지닌  Red Black Tree나 AVL Tree를 사용할 수 있습니다.

배열 vs 링크드리스트

- 배열의 경우 메모리 구조에 연속된 공간에 저장되기때문에 삽입과 삭제가 느릴수 있는 반면 링크드리스트의 경우 메모리에 연속된 공간에 저장되지 않기 때문에 삽입 삭제는 더빠릅니다. 
- 조회의 경우 배열은 인덱스로 랜덤 엑세스가 가능하지만 링크드 리스트의 경우 헤드노드부터 테일노드까지 차례로 순회해야하기 때문에 배열보다 더 느립니다. 
- 다만 자바스크립트의 배열은 실제로 다른 언어의 배열과는 다르게 객체의 형태로 존재하기 때문에 위의 일반적인 배열과 링크드 리스트의 비교는 적용되지 않는 부분이 존재합니다. 
https://poiemaweb.com/js-array-is-not-arrray

Array | PoiemaWeb

---

과제

이번주 과제는 배운 자료구조를 실제로 구현해보는 것이 목표 였습니다.

1. 필요한 수치는 상수화 시키는 것이 차후 재활용성 측면에서 더 좋습니다. 

처음에는 해시테이블의 용적률을 따로 위의 사진과 같이 변수에 담아 사용하지 않고 함수에 그대로 담아 사용했는데 만약 함수가 길어지고 나중에 해당함수에서 용적률을 바꾸고 싶다면 해당위치로 가서 수치를 수정하는것 보다 위에서 미리 변수화 시켜놓은 수치를 바꾸는게 더 효율적일것입니다. 

2. 재귀를 사용해보자

개인적으로 재귀함수는 스택 오버플로우 때문에 사용하기가 좀 꺼려지는 느낌이 있습니다..... 그런데 이번 과제를 진행하면서 재귀를 많이 사용해보니 실제로 잘만 활용하면 가독성이 더 좋은경우가 많은것 같습니다. 앞으로는 while등으로 반복을 돌릴때 재귀로는 돌릴 수 없을지 항상 한번더 고민해 봐야겠습니다. 

---

부족하다고 느낀점

바닐라 코딩 오피스까지의 거리가 너무멀어서 (왕복 4시간) 버려지는 시간이 너무 많습니다..... 어떻게든 대중교통안에서 버려지는 시간을 활용해야하는데 고민입니다.....