그나마 직전 학기에 알고리즘 강의 들어서 다행이다 ^^,,,,
✏️ 새롭게 배운 것
자료구조
해시 테이블
사실 해시 테이블을 배운 적은 있는데 딱 각 잡고(?) 응용해서 문제를 푼다든지 해본 적은 없는 것 같다. 그래서 새로 배우는 셈 치고!!
해시 테이블은 키와 값을 받아 해시 함수를 이용해 키를 해싱하고, 해싱한 값을 인덱스 = 버켓으로 해서 값을 저장하는 선형 자료구조다. 삽입, 삭제, 탐색 모두 O(1)! 완전 효율적인 자료구조다. (단, 키를 알고 있을 때,,,) js에서는 Array, Object, Map, Set으로 구현할 수 있다.
Object가 가장 간단한 것 같고, Map은 다양한 타입 사용 가능하고 여러 메서드가 제공돼서 편하기 때문에 Map을 자주 사용할 것 같다.
문제점 & 해결법
탐색, 삭제가 빠르다고 해서 무작정 사용하면 아무렇게나 사용하면 안된다. 만약 서로 다른 키 값을 해시 함수에 돌렸는데 결과가 같다면?! 같은 인덱스로 값을 넣으려고 하면 충돌이 생길 것이다. 이럴 때 몇 가지 해결 방법이 존재한다.
선형 탐사법- 충돌이 일어나면 버켓을 한 칸 이동한다.제곱 탐사법- 충돌이 일어나면 충돌 발생 횟수의 제곱만큼 옆으로 이동한다.이중 해싱- 해시 함수를 추가로 만들어서 충돌이 발생하지 않을 때까지 2번째 해시함수로 계속 인덱스를 만든다.분리 연결법- 인덱스가 겹치더라도 버킷을 연결 리스트로 사용해서 리스트에 값을 추가한다.
트라이 Trie
알고리즘 스터디도 했었는데 트라이는 처음 들어봤다. 아마 초급 스터디여서 제일 기본적인 것만 진행했나보다 🤨
트라이는 문자열을 저장하고 효율적으로 탐색하기 위한 트리 형태의 자료구조다. js에서는 해시 테이블과 연결 리스트를 이용해서 구현할 수 있다.
특징
- 문자열의 길이가 L일 때, 탐색,삽입에 O(L)이 걸린다. -> 단순 비교해서 탐색하는 것보다 효율적이다.
- 각 노드가 자식에 대한 링크를 전부 가지고 있다. -> 저장공간을 더 많이 차지한다.
구조
- 루트는 비어있다.
- 각 간선은 추가될 문자를 키로 가진다.
- 각 노드의 value = 이전 노드의 value + 간선의 키
🔥 더 공부해 볼 것
js로 알고리즘 구현
어제 가장 먼 노드 실습 문제를 풀다가 문제 조건을 확인하지 않아서 시간 초과가 발생했다. 바로 간선 개수가 50,000개 이하라는 조건이였는데, 이를 확인하지 않고 그냥 플로이드 와샬이 생각나서 구현을 했다가 시간 초과 폭탄을 맞았다. 문제 자체에서 1번 노드로부터의 거리만 구하면 된다고 나와있는데 모든 노드 간의 최단 경로를 구하느라 O(n^3)의 시간이 소요됐다. 그래서 다시 알고리즘 강의록 보다가 다익스트라를 발견해서 통과할 수 있었다. 항상 알고리즘은 C++로 하다가 js로 구현하려니깐 내 의도대로 된건지 잘 모르겠다. js로 최단 경로 알고리즘 뿐만 아니라 다양한 알고리즘을 구현해봐야겠다. 그리고 알고리즘 자체도 거의 까먹어서 다시 공부해보자.
자료구조 구현
마찬가지로 자료구조도! C++로 문자열 다루는 걸 어려워해서 항상 구박했는데, 우선순위 큐, 벡터, 스택,,, 좀 그립다 🥲 내가 느끼기에 js는 Array랑 Object를 굉장히 자유롭게 사용할 수 있는 반면, 다른 자료구조들을 직접 구현하는 게 힘든 거 같다. 원할 때 마음대로 구현해서 사용할 수 있게 연습하자. 특히 포인터와 클래스 기피증으로 맨날 회피해오던 연결 리스트!
코딩 습관(?)
멘토님께서 피가 되고 살이 되는 ㅋㅋ 말씀을 해주신 거 같다. 난 엣지 케이스를 생각하는 능력이 부족하다. 알고리즘 스터디를 할 때도 분명히 맞는 코드인 거 같은데 왜 틀리지?해서 스터디원들의 도움을 받기도 했다. 심지어 데브코스 코테에서도! 3번 문제 테케 몇 개가 실패가 떴는데 아직도 이유를 모른다. 항상 다양한 예외 상황이 있다는 걸 인지하고 생각해보자.
마무리
1학기에 알고리즘분석 강의를 들어서 그런지,js 기본 개념 강의보다는 머리에 잘 들어왔다. 사실 알고리즘은 큰 숙제 같다. 강의도 듣고 스터디도 했지만, 아직도 잘 모르겠고 회피하고 싶은 존재다. 하지만 개발자로서 더 성장하기 위해 피하지 않고 부딪히면서 공부해보려고 한다!
세 번째 TIL인만큼 글 쓰는 건 쪼금 편해졌다. 하지만 제대로 쓰고 있는 건지는 아직도 의문이다. 너무 대충 쓰는 건가,,,? 이번에 피드백도 받고 계속 쓰다보면 감이 생길거라고 믿는다 🤔
