[programmers] TIL_DAY-04

2022.03.24(목)

🗒 목차

1. 큐

2. 해시 테이블

3. 그래프

✅ 1. 큐

FIFO - 먼저온 사람 먼저 들어가기

 자바스크립트에는 큐가 없다. C++이나 다른 언어처럼 Queue를 바로 사용할 수 없기 때문에 직접 구현해야 한다.
자바스크립트에서 큐를 구현하는 방법은 2가지가 있다. 바로 배열과 연결 리스트를 사용하는 방법이다!

  배열로 큐를 구현하는 방법은 간단하지만 삭제할 때 배열이 이동되지 않기 때문에 새로운 요소를 추가할 경우 인덱스가 기존의 마지막 인덱스부터 시작해서 추가된다. 자바스크립트 배열은 배열의 크기가 동적으로 변화하기 때문에 배열의 크기에 별로 큰 영향을 받지는 않지만, 삭제와 추가를 반복하다보면 리어와 프론트의 값이 무한정 커질 수 있다는 단점이 있다.

  알고리즘 문제를 해결 할 때 배열로 큐를 구현하는 방법이 연결 리스트를 사용하는 방법보다 구현이 간단하기 때문에 코딩테스트를 위해서 큐가 필요할 경우 배열로 사용하는 것도 좋은 방법이다!

  연결 리스트로 큐를 구현하는 방법은 배열로 구현하는 것보다는 조금 복잡하지만 연결 리스트에서 헤드가 프론트가 되고 리어가 테일이 된다고 생각하면, 연결 리스트를 사용해서 어렵지 않게 큐를 구현할 수 있다.

✅ 2. 해시 테이블

사물함의 주인을 찾아라!

  해시 테이블은 키와 값을 받아 키를 해싱해서 나온 값을 인덱스로 저장하는 선형 자료구조를 말한다.
해시 테이블은 각각의 키값에 해시함수를 적용해 배열의 고유한 인덱스를 생성하고 이 인덱스를 활용해 값을 저장하거나 검색하게 된다. 값이 저장되는 장소를 버킷이라 부른다.

  해시 함수는 특정한 구현방법이 있지는 않다. 원하는대로 구현해서 사용할 수 있다. 해시 테이블은 완벽해 보이지만 문제점이 있다. 키 값을 해싱해서 나온 인덱스가 동일할수 도있다. 이럴 경우 충돌이 발생했다고 말한다.

  해시 함수 충돌을 해결하기 위한 4가지 방법이 있다.

1. 선형 탐사법 : 충돌이 발생할 경우 인덱스를 한 칸 옆으로 이동한다.
2. 제곱 탐사법 : 충돌이 발생하면 충돌이 발생한 횟수의 제곱만큼 옆으로 이동한다.
3. 이중 해싱 : 충돌이 발생하면 다른 해시 함수를 사용해서 새로운 인덱스를 만든다. 또 다시 충돌이 발생한다면 두 번째 해시함수를 사용해서 충돌이 발생하지 않을때까지 인덱스를 만든다.
4. 분리 연결법 : 버킷의 값을 연결 리스트로 사용하여 충돌이 발생하면 연결 리스트에 추가한다.다른 방법과 달리 새로운 인덱스를 구하지 않는다. 치명적인 단점으로 하나의 버킷이 무한정 많이 늘어날 수있다.

  해시 테이블은 언제 사용하는가?
연결 리스트를 사용하면 노드를 추가하거나 제거하는 것은 어렵지 않지만 탐색을 할 경우에는 선형시간 만큼이 소요된다. 그렇다고 탐색을 쉽게 하기 위해 배열을 사용한다 하더라도 인덱스를 모를 경우 마찬가지로 탐색에 선형시간 만큼 소요된다. 이럴 경우 해시 테이블을 사용하는 것이 유리하다! 키 값과 해시 함수를 사용해서 버킷에 저장하기 때문에 탐색과 삽입 삭제가 모두 상수 시간만에 끝난다.

  자바스크립트에서 사용하는 방법.

1. 배열로 만들기
2. 객체로 만들기
3. Map 사용하기
4. Set 사용하기

 Map을 사용하면 set함수와 get함수를 이용해서 값을 추가하거나 찾을 수 있다. 또한 기존 객체와 달리 키값으로 오브젝트나 배열같은 타입도 사용 가능하다. 객체를 사용하는 방법은 정수가 아닐경우 전부 문자열로 바꿔버리기 때문에 다양한 타입이 필요하다면 Map함수를 사용하는 것이 좋다.

✅ 그래프

비선형 자료구조. 벌써 부터 머리가 아프다!

 그래프는 정점과 정점사이를 연결하는 간선으로 이루어진 비선형 자료구조를 의미한다. 정점집합과 간선 집합으로 표현할 수 있다. 여기서 정점은 Node 간선은 Edge라고도 불린다.

 비선형 자료구조인 그래프의 특징으로 정점은 여러개의 간선을 가질 수 있고. 간선의 방향성을 부여하는것에 따라 방향 그래프와 무방향 그래프로 나눌 수 있다. 또한 간선마다 가중치를 가질 수있기 때문에 최단거리 또는 최장거리를 구할 수 있다. 주의할 점으로 사이클을 가질 수 있다는 특징이 있는데, 사이클은 잘못하면 무한 루프에 빠질수 있다. 따라서 사이클을 잘 관리해야 한다.

 무방향 그래프는 노드와 노드를 연결하는 간선에 방향성이 없기 때문에 양방향 이동이 가능하다. A - B에서 A -> B도 가능하고 A <- B도 가능하다. 방향그래프의 경우 노드와 노드간 양방향 이동이 가능하지만 간선이 두 개여야 한다. 한 개만 있을 경우 단방향 이동만 가능하다.

 간선의 방향성이 아닌, 전체 그래프의 연결 상태에 따른 분류를 할 수 있다. 연결 그래프와 비연결 그래프, 완전 그래프가 있다.
연결 그래프는 모든 정점이 서로 이동 가능한 상태인 그래프를 말한다. 여기서 모든 노드에서 각 노드에 간선이 연결되어 있다는 뜻은 아니다. 특정 시작노드로 부터 모든 노드에 접근 가능한 것을 말한다.
비연결 그래프는 특정 정점쌍 사이에 간선이 존재하지 않는 그래프를 말한다.
완전 그래프는 모든 정점끼리 연결된 상태인 그래프를 말한다.한 정점의 간선 수는 (전체 정점수 - 1)이고,
(모든 정점의 수 - 1) * (모든 정점의 수)는 모든 간선의 수를 의미한다.

  자바스크립트에서 사용하는 방법

1. 인접행렬 : 정점의 크기만큼 2차원 배열을 만든다. 열 부분은 시작 정점을 의미하고 행 부분은 도착 정점을 의미한다.
2. 인접리스트 : 자바스크립트의 배열은 연결 리스트처럼 무한정 늘어날 수 있기 때문에 정점의 수만큼 배열을 만든 후 연결할 정점을 배열에 추가한다.

✅ 정리

알고리즘 공부를 하면서 개념은 쉽게 이해하는듯 했으나 막상 문제를 만나면 어떤 자료구조를 사용해야 하는지 문제 파악을 제대로 하지 못하고 있다. 반복과 연습만이 살길이다...