[데브코스 4일차] 큐, 해시테이블, 그래프

🤔 생각해볼 것

1. 자료구조 큐에 대해서 설명할 수 있나요?
- 큐를 구현해보세요.
- 연결 리스트를 이용한 큐를 구현해보세요.
- 원형 큐를 구현해보세요.

2. 자료구조 해시테이블에 대해서 설명할 수 있나요?
- 간단한 해싱 함수를 구현해보세요.
- 해시테이블을 구현해보세요.

3. 자료구조 그래프에 대해서 설명할 수 있나요?
- 그래프와 트리의 차이는 무엇일까요?

[1] 큐 (Queue)

Queue

큐(Queue) 는
- Front : 큐의 맨 앞
- Rear : 큐의 맨 뒤
- Enqueue : 큐에 원소를 집어 넣는 것, O(1)
- Dequeue : 큐에서 원소를 빼 내는 것, O(1)
기본적으로 삽입, 삭제는 O(1)의 시간복잡도를 가진다.
구현
1) 투 포인터를 이용해서 Array로 구현
2) 연결 리스트로 구현

원형 큐 (Circular Queue)

초기 생성 시 size가 정해져 있고, Front와 Rear가 이어져 있는 큐, 연결리스트로 구현 할 수는 있지만 Array로 구현하는 것이 더 낫다.

[2] 해시테이블 (Hash-table)

한정된 배열 공간에 key를 index(Bucket)로 변환하여 값들을 삽입한다. 이상적인 해시테이블은 삽입, 삭제, 탐색이 모두 O(1)이다.

[2-1] 충돌

충돌은 생각보다 쉽게 일어난다.

비둘기 집 원리

n개 아이템을 m개 컨테이너에 넣을 때, n > m이라면 적어도 하나의 컨테이너에는 반드시 2개 이상의 아이템이 들어있다.

생일 문제

사람 57명이 모이면 같은 생일인 사람이 있을 확률이 99%에 이른다.

[2-2] 해시 함수

임의 크기 데이터를 고정 크기 값으로 매핑하는데 사용할 수 있는 함수

좋은 해시 함수의 특징

1) 해시 함수 값 충돌의 최소화
2) 쉽고 빠른 연산
3) 해시 테이블 전체에 해시 값이 균일하게 분포
4) 사용할 키의 모든 정보를 이용하여 해싱
5) 해시 테이블 사용 효율이 높을 것

[2-3] 해시테이블 구현방식

선형탐사법, 제곱탐사법, 이중해싱, 분리연결법 등 다양함.

오픈 어드레싱 (선형 탐사 방식)

- 오픈 어드레싱도 많은 방법이 있지만 선형탐사방식이 가장 보편적이다.
- 파이썬, 루비
- Hash 충돌이 발생했을 때, 그 다음 주소를 확인하고, 비어있다면 그 자리에 대신 저장하는 해시테이블 기반 자료구조

개별 체이닝 (연결 리스트 방식)

- C++, 자바, 고(Go)
- 충돌이 일어나도 하나의 해시주소를 사용하며, 별도로 Linked-list를 병합 사용하여 충돌을 해결

[3] 그래프 (Graph)

1) 노드(Node)와 간선(Edge)로 표현된다. Node는 Vertex(정점)이라고도 한다.
- 정점은 여러개의 간선을 가질 수 있다.
2) 간선은 비용(가중치)을 가질 수 있다.
3) 간선은 방향을 가질 수 있다. (유향그래프, 무향그래프)
4) 그래프는 사이클이 발생할 수 있다.
- 연결그래프, 비연결그래프, 완전그래프
5) 인접리스트, 딕셔너리, 인접행렬로 표현할 수 있다.

예시 1) 비용이 있는 무향 그래프를 인접행렬, 인접리스트로 표현한다면?

비용이 있는 무향그래프

인접리스트

graph[A, B, C, D, E] =

[ [(B,1),(C,2)], [(A,1),(D,3),(E,4)], [(A,2),(E,5)], [(B,3)], [(B,4),(C,5)] ]

예시 2) 비용이 없는 유향 그래프를 딕셔너리로 표현한다면?

비용이 없는 유향 그래프

graph = {
    1: [2,3,4],
    2: [5],
    3: [5],
    4: [],
    5: [6,7],
    6: [],
    7: [3],
}

💡 오늘의 회고

간만에 알고리즘 문제를 풀어봤다. 프로그래머스 Lv2 프린터, Lv3 베스트앨범 문제였음.
프린터 문제 같은 경우는 전에 python, JavaScript 모두 풀어본 적이 있는데, python은 deque 라이브러리를 사용해서 문제가 없었지만 자바스크립트로 문제를 풀 때는 데이터의 수가 적고, 데이터가 적을 때는 shift, unshift의 성능이 꽤 괜찮기 때문에 쉽게 풀었었는데, 자바스크립트로 큐 자료구조를 직접 구현하면서 shift, unshift를 사용하지 않고 풀려니 꽤 만만치 않았다. 베스트앨범 문제 같은 경우는 한 30~40분 정도 밖에 안걸렸기도 했고, 나름 꽤 괜찮게 풀었다고 자부했지만, 선협멘토님의 함수형 프로그래밍 풀이에.... 바로 겸손해져버렸다. 역시 세상은 넓고 고수는 많다...

아참, 어제 연결리스트를 구현하면서 손으로 일일이 테스트를 하는 것이 번거로워 간단하게 값만 비교해서 테스트를 할 수 있는 툴(? 사실 툴이라고 하기도 뭐하지만... 이젠 TDD없이 살 수 없는 몸이 되어버ㄹ)을 만들어서 테스트코드를 작성하며 자료구조를 구현하고 있다. 이번에는 이렇게 해보고 다음에는 Jest같은 것을 한 번 사용해봐야지.

알고리즘 문제를 풀었다면 항상 블로그에 기록하고 있다. 그래서 간만에 문제 업데이트를 했읍니다🤗
(검색 엔진 최적화를 하긴 했는데 검색에 잘 안뜨는 것 같다... 😂)
https://ryong9rrr.github.io/pgm-lv3-%EB%B2%A0%EC%8A%A4%ED%8A%B8%EC%95%A8%EB%B2%94/

프로그래머스 Lv3) 베스트앨범