cs 스터디 (2주차)

6. Hash Table

해시 : 해시함수로부터 나온 결과값, 저장 위치의 역할을 한다.
해싱 : 해시함수를 통해 해시를 얻어내는 일련의 과정을 해싱이라고 한다.
 
(key,value) 형식으로 data를 저장한다.
 
key값에 해시함수를 적용해 배열의 고유한 index(해시)를 생성하고, 이 index를 활용해 값을 저장하거나 검색한다.
 
 

장점)

배열(버킷)을 사용하기 때문에 검색이 빠르다.
구체적으로는 key - value의 1대1 매칭 구조이기 때문에 삽입, 삭제, 검색 모두 평균적으로 (충돌이 없는 경우) O(1)의 시간 복잡도를 가져서 빠르다.
 
 

단점)

데이터가 저장되기 전에 미리 공간을 만들어놔야 하므로 공간 효율성이 떨어진다.
 
hash function이 복잡하다면 hash를 만들어내는데 시간이 많이 소모되므로 hash function의 의존도가 높다.
 
순서를 보장하지 않는다.
 
최악의 경우 ( 같은 인덱스에 모든 키값과 데이터가 저장된 경우 = 전부 충돌한 경우 )
O(key의 개수) 즉 O(n)의 시간 복잡도를 가질 수 있다.
 
 
[참고한 포스팅]

• https://think0wise.tistory.com/66

 
 
Q. 인덱스를 구할 때 왜 해시함수를 쓰는 거지? 안 쓰고 그냥 하면 안 되는 건가?
→  key를 그대로 data의 key로 사용하면 key의 길이만큼 메모리 공간을 차지하기 때문에 즉, 메모리 효율성이 떨어지기 때문에 hash function을 통해 고정된 길이를 가지는 hash값으로의 변환이 필요하다.
 
해시는 보안 분야에서도 널리 사용된다. 키와 해시값 사이에 직접적인 연관이 없기 때문에 해시값만 가지고는 키를 온전히 복원하기 어렵기 때문이다.
 
아울러 해시함수는 길이가 서로 다른 입력 데이터에 대해 일정한 길이의 출력을 만들 수 있어서 ‘데이터 축약’ 기능도 수행할 수 있다.
 
 
[참고한 포스팅]

• https://go-coding.tistory.com/30?category=967004 

 
해시충돌 : 해시함수에 서로 다른 key 값을 넣었는데 같은 해시값이 나온 것
 
해시충돌은 적을수록 좋다.
 
해쉬 충돌을 줄이기 위해선 일단 좋은 hash function을 사용해야 한다.
아래는 몇가지 해시 함수들에 대한 설명이다.
 
1) Division Method
숫자 Key를 테이블의 크기로 나누어 나온 나머지를 인덱스로 사용한다. ( index = Key % 테이블 크기 ) 이때 테이블의 크기를 소수(Prime Number)로 정하고 2의 제곱수와 먼 값을 사용하는 것이 효과가 좋다. 예를 들어 Key 값이 23일 때 테이블 사이즈가 7이라면 index는 2다. 
 
2) Digit Folding
Key의 문자열을 ASCII 코드로 바꾸고 그 값을 합해 테이블 내의 주소로 사용하는 방법이다. 위 예시와 비슷한0 상황에서 사용될 수 있다. "Ryan" 같은 문자열을 R->82 + y->121 +  a->97  + n->110 = 410 을 index로 사용하면 된다. 만약 이 때 index가 테이블의 크기를 넘어간다면 Division Method를 적용할 수 있을 것이다.
 
3) Multiplication Method
숫자로 된 Key 값 K와 0과1 사이의 실수 A, 보통 2의 제곱수인 m을 사용하여 다음과 같이 계산한 값을 index로 사용한다. index = (K*A mod 1)*m
 
이 외에도 많은 해시 알고리즘이 다양하게 존재한다. 사용자가 필요에 의해 직접 해시 알고리즘을 만들 수도 있다.
 
 
Q. 해시함수가 종류가 여러개 있는데 이중에서 좋은 hash function을 선정하는 기준은?
 

1. key를 고르게 분포시킬 수 있어야 한다.
2. 충돌 발생 빈도가 적어야 한다.
3. 연산이 빨라야 한다.

 
[참고한 포스팅]

• https://yoongrammer.tistory.com/82

 
 
하지만 좋은 hash function을 써도 해쉬 충돌은 일어난다.
 
그러면 어떻게 해야 되나?
→ 2가지 방법이 있다.
 
 

1) Separate Chaining (분리 연결법)

 
버킷에 다음 data의 주소를 저장하는 것이다.

장점)

• 해시 테이블의 확장이 필요없다.
• 구현이 간단하다.
• 원소를 쉽게 삭제할 수 있다.

 
단점)

• 데이터의 수가 많아지면 동일한 버킷에 chaining 되는 data가 많아져 캐시의 효율성이 감소한다.

 
연결리스트를 사용해서 구현한다.
각각의 버킷(bucket)들을 연결리스트(Linked List)로 만들어 해시충돌이 발생하면 해당 bucket의 list에 추가하는 방식이다.
 
트리 (Red Black Tree)를 사용한 구현도 가능하다.
 
 
 

2) Open Addressing (개방 주소법)

 
개방 주소법이란 추가적인 메모리를 사용하는 chaining 방식과 다르게 비어있는 해시 테이블의 공간을 활용하는 방법이다. 개방 주소법을 구현하기 위한 방법으로는 다음과 같은 3가지 방식이 존재한다.
 
1. Linear Probing 
현재의 버킷 index로부터 고정폭만큼 이동하여 차례대로 검색해 비어 있는 버킷에 데이터를 저장한다.
 
2. Quadratic Probing
해시의 저장순서 폭을 제곱으로 저장하는 방식. 예를 들어 처음 충돌이 발생한 경우 1만큼 이동하고, 그 다음 충돌이 발생하면 2^2, 3^2 칸 씩 옮기는 방식이다.
 
3. Double Hasing Probing
해시된 값을 한 번 더 해싱하여 해시의 규칙성을 없애버리는 방식. 해시된 값을 한번 더 해싱하여 새로운 주소를 할당하므로 기존 방식보다 더 많은 연산을 하게 된다.
 
[참고한 포스팅]

• https://code-lab1.tistory.com/m/14
• https://velog.io/@protect-me/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-05-%ED%95%B4%EC%8B%9C%ED%85%8C%EC%9D%B4%EB%B8%94-JS

---

 

7. Graph

https://velog.io/@deannn/CS-%EA%B8%B0%EC%B4%88-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-Graph

[CS 기초 - 자료구조] Graph

 
 

Graph 용어정리
 

정점(vertex) : 위치 개념. node라고도 불림
간선(edge) : 정점들을 연결하는 선. 정점과의 관계. 분기(branch)라고도 불림
사이클(cycle) : 단순 경로의 시작 정점과 종료 정점이 동일한 경우
 

 
 
 
Graph 구현

인접 행렬, 인접 리스트로 구현이 가능하다.
 
인접 행렬

가중치가 있는 그래프라면 1 대신 가중치를 넣는다.
 
방향 그래프일 경우 방향에 맞는 간선만 표기한다.
 
 
인접 리스트

 

인접 행렬은 연결 여부를 바로 알 수 있다는 장점이 있지만
연결되지 않은 것들까지도 행렬로 표현해야하니 공간 효율성이 떨어진다는 단점이 있다.
 
인접 리스트는 특정 노드와의 연결 여부를 바로 확인할 수 없고 탐색을 해야 해서 시간이 소모된다는 단점이 있다.
하지만 연결된 것들로만 리스트를 구성하기 때문에 공간 효율성이 좋다.
 
간선이 많은 그래프의 경우, 인접 행렬을 통해 빠르게 연결 여부를 확인할 수 있다.
간선이 적은 그래프의 경우는 인접 리스트를 통해 인접 노드를 빠르게 확인할 수 있다.
 
 
[참고한 포스팅]
https://born2bedeveloper.tistory.com/42

 
 
Graph 탐색

1) DFS (Depth Frist Search, 깊이 우선 탐색)
그래프 상에 존재하는 임의의 한 정점을 기준으로 잡고(루트 노드) 시작하여 다음 정점을 탐색하기 전에 해당 정점을 완벽하게 탐색 후 다음 정점을 탐색하는 방법이다.
즉, 넓게 탐색하기 보다는 깊게 탐색하는 것이 우선인 방법이다.
 
A -> B -> D -> E -> H -> C -> F -> G
 
 
2) BFS (Breadrh Frist Search, 너비 우선 탐색)
그래프 상에 존재하는 임의의 한 정점을 기준으로 잡고(루트 노드) 시작하여 인접한 정점을 먼저 탐색하는 방법이다.
즉, 깊에 탐색하기 보다는 넓게 탐색하는 것이 우선인 방법이다.
 
A -> B -> C -> D -> E -> F -> G -> H
 
 
 
Q. 그래프랑 트리랑 차이가 뭐지? 생긴 것만 보면 비슷한 거 같은데
 

→  트리와 그래프의 차이점

	그래프	트리
정의	노드와 그 노드를 연결하는 간선으로 구성된 자료 구조	그래프의 한 종류, 방향성이 있는 비순환 그래프
방향성	방향, 무방향 모두 존재	방향 그래프만 존재
사이클	순환, 비순환 모두 존재, 노드 한 개의 자체 순환도 가능	비순환 그래프만 존재
루트 노드	루트 노드의 개념이 없음	한 개의 루트 노드만이 존재
부모-자식	부모-자식의 개념이 없음	루트 노드를 제외한 노드는 1개의 부모노드만을 가짐
모델	네트워크 모델	계층 모델
순회	DFS, BFS	DFS, BFS 방식의 전위, 중위, 후위 순회
간선의 수	간선의 개수는 자유, 없을 수도 있음	N개의 노드를 가진 트리는 항상 N-1개의 간선을 가짐
경로		임의의 두 노드 간의 경로는 유일
예시 및 종류	지도, 지하철 노선도의 최단 경로, 전기 회로의 소자들, 선수 과목	이진 트리, 이진 탐색 트리, 균형(Red-Black 트리), 이진 힙

 
[참고한 포스팅]

• https://gusrb3164.github.io/computer-science/2021/04/16/graph,tree/

 
 

---

 

최소신장트리 (Minimum Spanning Tree)

 
 
크루스칼 알고리즘(Kruskal algorithm)
 
완전탐색 같은 느낌이다. 처음부터 끝까지 다 해보는 것이다.
 
연결될 수 있는 node들의 가짓수를 구하고 (ex. A-B, B-C ...)
그것들의 가중치 합을 오름차순으로 정렬한다음 (ex. A-B(3), B-C(5) ...) 하나씩 채택해나간다.
이 과정에서 기존에 선택했던 node랑 싸이클이 생성되면 해당 node는 채택하지 않고 skip한다.
 

그런데!

 
계산해야 할 node가 많아지면 시간이 오래 걸리니까 이럴 땐 그냥 임의로 하나를 출발점으로 정한다음 거기서부터 당장 앞에 놓인 선택지들 중에 좋은 것(가중치가 작은 것)들을 차례로 선택해나가는 방법이 있다.
 
이것이 프림 알고리즘(Prim algorithm)이다.
 
그리디 같은 느낌이다. 당장 눈 앞의 이익을 쫒되 뒤돌아보지 않는 것이다.
 
프림의 시간 복잡도는 O(ElogV), 크루스칼의 시간 복잡도는 O(ElogE)
즉, 그래프 내의 간선이 많은 경우는 프림 알고리즘, 간선이 적은 경우는 크루스칼 알고리즘이 유리하다.
 
 
[참고한 포스팅]
https://4legs-study.tistory.com/m/111
https://chanhuiseok.github.io/posts/algo-33/
 
 
 
Q. 그러면 프림은 처음 선택하는 node가 제일 중요할 것 같은데 이거는 사용자의 임의로만 정하는 건가? 무슨 기준을 갖고 정하는 거지? 그냥 무작위로 정하는 거면 할 때마다 다른 결과값이 나올 것 같은데
 
→ 임의로 정한다고 한다. 구글링을 해보니 프림과 크루스칼이 구하는 해는 최적해로 같은데, 그걸 구해내는 시간에 차이가 있기 때문에 상황에 따라 적절한 알고리즘을 사용해야 한다는 흐름인 것 같다.