[TIL] 프론트엔드 Day 4

공부한 내용

1. 해시 테이블

index가 아닌 key값으로 데이터에 접근하는 자료구조, key값을 해시함수에 대입한 결과를 가지고 데이터의 위치를 구한다.

- Hash Collision

서로 다른 key 값을 가지는 두 데이터가 같은 위치를 가르킬 때 이를 충돌(collision)이라고 한다. 충돌에 대응하는 방법은 여러가지가 있다.

- 선형 탐사법

충돌이 발생했을 때, 그 다음 위치에 중복된 값을 저장한다. 충돌이 지속 될 경우 연속된 메모리가 사용될 수 있다.

- 제곱 탐사법

충돌이 발생했을 때, 충돌한 횟수의 제곱만큼 이동한 위치에 값을 저장한다. 선형 탐사법 대비 연속된 메모리 사용이 적다.

- 이중 해싱

충돌이 발생한 값을 별도의 해시함수에 다시 입력으로 사용한다. 별도의 해시함수의 결과가 다시 충돌됐다면, 충돌이 발생하지 않을 때 까지 해시함수의 입력으로 사용한다.

- 분리 연결법

충돌이 발생할 시 연결리스트를 사용해 값을 추가한다.

2. 그래프

2-1. 특징

비선형 자료구조의 형태로 사이클이 존재하기도 한다. 그래프를 완전탐색하는 경우 이로인한 무한루프에 주의해야한다.

2-2. 분류

• 방향성 : 무방향 그래프, 방향 그래프
• 정점의 연결 상태: 완전 그래프, 연결 그래프, 비연결그래프

2-3. 구현방식

• 인접행렬
  n개의 정점이 있을 때 $n \times n$만큼의 행렬로 연결 상태를 표시한다. 무 방향 그래프라면 성분이 대칭으로 나타난다. 두개의 정점의 연결 여부를 $O(n)$시간내에 알아낼 수 있지만, 공간복잡도가 크다.
• 인접리스트
  n개의 정점이 있을 때 n개의 리스트로 연결 상태를 표시한다. 공간복잡도가 작지만 두 정점의 연결 여부를 알아낼 때 최악의 경우 $O(n)$만큼의 시간이 걸린다.

3. 힙

우선순위에 따라서 우선순위가 가장 높은 노드를 루트 노드에 위치시키는 이진트리의 일종이다.

• 새로운 노드를 추가시에 가장 최하위에 추가되며, 부모노드와 우선순위를 비교해가며 부모노드의 우선순위가 추가한 노드보다 커질 때까지 자리를 바꾼다.
• 루트 노드를 제거할 때, 가장 최하위의 노드가 루트의 위치로 이동한다. 이후 자식노드와 비교해가며 자리를 바꾼다. 두개의 자식 노드 중 우선순위가 더 높은 노드와 자리를 바꾸며, 자식노드의 우선순위가 자신보다 낮을 때 까지 반복한다.

4. 이터러블과 이터레이터

• 이터러블
  이터레이터를 반환하는 심볼이 존재하는 값.

• 이터레이터
  {value, done} 객체를 반환하는 next()가진 값.

• 이터러블/이터레이터 프로토콜
  ES6에서 for-of 등의 기능과 상호작용하도록 만든 규약

다시 볼 내용

이터러블/이터레이터 프로토콜, 코딩테스트 실습문제

느낀점

코딩테스트에서 유용하게 쓰일 알고리즘과 자료구조에 대해서 배울 수 있던 하루였다. 대학교(또학교)에서 배웠던 내용이지만, 이론적인 내용과 실제 코딩 테스트 문제에 적용하는 내용의 차이가 큰거같다. 전혀 피곤하지 않고 재미있게 들을 수 있었고, 자기반성의 시간도 가졌다. 백준에서 시간좀 쓰면서 알고리즘 문제에 어느정도 능숙해졌다고 생각했지만 실습에서 한번 좌절하고, 너무 쉽게 풀리는 풀이에 두번 좌절했다. 하지만 그만큼 목표의식도 생겼다. 우물안의 개구리를 벗어나 한번 더 도약할 기회다!

Reference

프로그래머스 프론트엔드 데브코스