⚡ 자바스크립트로 보는 자료구조 Ⅳ
📌 해시 테이블 (Hash Table)
🔷 키와 값을 받아 키를 해싱하여 나온 index에 값을 저장하는 선형 자료구조
- 삽입 과정의 시간 복잡도는 O(1)이며 키를 알고 있다면 삭제와 탐색도 O(1)로 수행한다.
- 해시 함수를 이용한다.
💡 해시 함수
입력받은 값을 특정 범위 내 숫자로 변경하는 함수 (정해진 것이 없으므로 마음대로 구현할 수 있다)
🔷 함수의 결과값이 동일하여 겹쳤을 때 해시 충돌(Hash Collision)이 일어난다.
💡 해시 충돌
해시 함수가 서로 다른 두 개의 입력값에 대해 동일한 출력값을 내는 상황을 의미한다. 해시 함수가 무한한 가짓수의 입력값을 받아 유한한 가짓수의 출력값을 생성하는 경우, 비둘기집 원리에 의해 해시 충돌은 항상 존재한다.
🔷 해시 충돌 해결법
1) 선형 탐사법
- 충돌이 발생하면 옆으로 한 칸 이동한다.
- 이 방법은 특정 데이터가 몰리면 최악의 경우에 탐색에 O(n)만큼 소요될 수 있다.
2) 제곱 탐사법
- 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다.
- 데이터 몰림이 덜하다.
3) 이중 해싱
- 충돌이 발생하면 다른 해시 함수를 이용한다.
- 충돌이 발생하지 않을 때까지 새로운 해시 함수로 index를 계속해서 만들어낸다.
4) 분리 연결법
- 버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 리스트에 값을 추가한다.
- 하나의 버킷이 무한정 늘어날 수도 있다.
🔷 왜 해시 테이블을 사용하는가?
- 빠르게 값을 찾아야 하는 경우 키를 통해 바로 값을 찾을 수 있기 때문에 배열이나 연결 리스트보다 안정적이다.
🔷 자바스크립트에서 사용하기
1) 배열을 그대로 사용(올바른 이용 방법이 아님)
2) 객체를 사용(정석)
3) Map
- set을 이용하여 값을 넣고, get을 이용하여 값을 찾는다. 다양한 타입을 넣고 싶을 때 유리하고 메서드가 많으며 순회가 편리하다.
4) Set
- 일종의 집합 연산, 중복된 내용을 전부 제거할 때 사용한다.
📌 그래프(Graph)
🔷 정점(Node)과 정점 사이를 연결하는 간선(Edge)으로 이루어진 비선형 자료구조
-
정점 집합과 간선 집합으로 표현할 수 있다.
-
예시
1) 지하철 노선- 역은 정점, 역 사이 간선은 거리나 소요시간 등의 정보를 포함하고 있다.
2) 페이지랭크 알고리즘
- 하나의 페이지가 정점, 페이지에서 파생되는 링크들을 간선으로 취급한다.
- 페이지와 링크를 수집하여 우선도를 특정하고 검색 결과를 계산한다.
- 구글이 이 알고리즘을 좋아합니다. 👍
🔷 그래프의 특징
1) 정점은 여러 개의 간선을 가질 수 있다.
2) 크게 방향 그래프와 무방향 그래프로 나눌 수 있다.
3) 간선은 가중치를 가질 수 있다.
4) 사이클이 발생할 수 있다.
💡 사이클
그래프의 정점과 간선의 부분 집합에서 순환이 되는 부분
🔷 무방향 그래프
- 간선으로 이어진 정점끼리는 양방향으로 이동이 가능하다.
- 표현하기에 (A,B)와 (B,A)는 같은 간선으로 취급된다.
🔷 방향 그래프
- 간선에 방향성이 존재하는 그래프
- 양방향으로 갈 수 있더라도 <A,B>와 <B,A>는 다른 간선으로 취급된다.
🌟 연결 상태에 따라 달라지는 그래프 🌟
🔷 연결 그래프
- 모든 정점이 서로 이동 가능한 그래프
🔷 비연결 그래프
- 특정 정점쌍 사이에 간선이 존재하지 않는 그래프
🔷 완전 그래프
- 모든 정점끼리 연결된 상태인 그래프
- 한 정점의 간선 수 = 모든 정점의 수 - 1
- (모든 정점의 수 - 1) * 모든 정점의 수 = 모든 간선의 수
📌 그래프 구현
🔷 인접 행렬(2차원 배열)로 구현하기
🖥 구현 코드
// 2차원 배열 선언 및 초기화
const graph = Array.from(Array(5), () => Array(5).fill(false));
// 값을 넣어 그래프 구현
graph[0][1] = true; // 0 -> 1
graph[0][3] = true; // 0 -> 3
graph[1][2] = true; // 1 -> 2
graph[2][0] = true; // 2 -> 0
graph[2][4] = true; // 2 -> 4
graph[3][2] = true; // 3 -> 2
graph[4][0] = true; // 4 -> 0
🔷 인접 리스트(연결 리스트)로 구현하기
🖥 구현 코드
// 배열로 연결 리스트 선언
const graph2 = Array.from(Array(5), () => []);
// 값을 연결시켜 그래프 구현
graph2[0].push(1); // 0 -> 1
graph2[0].push(3); // 0 -> 3
graph2[1].push(2); // 1 -> 2
graph2[2].push(0); // 2 -> 0
graph2[2].push(4); // 2 -> 4
graph2[3].push(2); // 3 -> 2
graph2[4].push(0); // 4 -> 0
그림 제공: https://programmers.co.kr/
