개발하는데 다 이유가 있겠지

크래프톤 정글 키워드 복습하기(3)

 

해쉬 테이블(Hash Table)

---

해시 함수(Hash Function)을 사용해 변환한 값을 색인(index)으로 삼아 키(key)와 데이터(value)를 저장하는 자료구조

해시 함수(Hash Function)란?
- 임의의 길이의 값을 고정된 크기의 값으로 변환하는 단방향 함수
- 해시값으로 변환하면 원래의 값을 찾아내는 역변환 불가

해시 함수 종류
- MD5 : 초기에는 많이 사용되었지만, 충돌 공격에 취약하다는 단점이 있습니다.
- SHA-1 : MD5보다 안전하지만, 역시 충돌 공격에 대한 우려가 제기되었습니다.
- SHA-256, SHA-512 : 현재 가장 널리 사용되는 안전한 해시 함수입니다.
- SHA-3 : SHA-2의 후속 버전으로, 더욱 안전한 구조를 가지고 있습니다.

특징

- 데이터가 입력되지 않은 여유 공간이 많아야 제 성능을 유지할 수 있음
  (통계적으로 해시 테이블의 공간 사용률이 70 ~ 80%에 이르면 성능 저하가 나타남)

---

충돌 처리 방식

1. 체인법(Chaining) : 충돌이 발생했을 때, 이를 동일한 버킷(Bucket)에 저장하는데, 이를 연결리스트 형태로 저장하는 방법

index가 152에서 'John Smith'와 'Sandra Dee'가 충돌했지만, 연결리스트 방식으로 충돌을 처리함

 

2. 오픈 주소법(Open Addressing): 해시값에 이미 저장된 다른 데이터가 있을 경우 다른 주소를 찾아 데이터를 저장하는 기법

3가지 방법을 통해 해시 충돌을 처리함

• 삽입 : 계산한 해시 값에 대한 인덱스가 이미 차있는 경우 다음 인덱스로 이동하면서 비어있는 곳에 저장한다. 이렇게 비어있는 자리를 탐색하는 것을 탐사(Probing)라고 한다.
• 탐색 : 계산한 해시 값에 대한 인덱스부터 검사하며 탐사를 해나가는데 이 때 “삭제” 표시가 있는 부분은 지나간다.
• 삭제 : 탐색을 통해 해당 값을 찾고 삭제한 뒤 “삭제” 표시를 한다.

오픈 주소법의 충돌 처리기법(3가지)
1. 선형탐사(Linear Probing) : 바로 인접한 인덱스에 데이터를 삽입하기 때문에 데이터가 밀집되는 클러스터링(Clustering) 문제가 발생하고, 탐색과 삭제가 느려짐
2. 제곱탐사(Quadratic Probing) : 자연수 제곱으로 탐사를 하는 방식으로 탐색과 삭제에 효율적일 수 있지만, 초기 해시값을 같을 경우 클러스터링 문제가 발생
3. 이중해싱(Double Hashing) : 처음 해시함수로 해시값을 찾기 위해 사용하고 두번째 해시함수는 충돌이 발생했을 때 탐사폭을 계산하기 위해 사용되는 방식

3. 리해싱(Rehashing) : 해시 테이블의 성능 저하를 방지하기 위해 해시 테이블의 크기를 늘리고, 모든 데이터를 새로운 해시 테이블에 다시 삽입하는 작업

- 로드 팩터(Load Factor) : 해시 테이블에 저장된 데이터의 수를 버킷의 수로 나눈 값 / 특정 임계값을 넘어서면 충돌이 자주 발생해 성능이 저하될 가능성이 높아짐(일반적으로 0.7~0.8을 넘어서면 리해싱 권장)
- 모든 데이터를 재배치하는 작업이므로, 시스템 자원 소모가 큼
- 일반적으로 기존 크기보다 2배정도 늘림

---

해시 함수 개선법

1. 나눗셈법(Division Method)

- 해시 테이블의 크기인 N을 아는 경우에 사용 가능
- 해시함수를 적용하고자 하는 값을 N으로 나눈 나머지를 해시값으로 사용하는 방법
- N은 2의 제곱꼴을 사용하면 안됨(제곱꼴이 2의 p제곱으로 나타날 때 k 의 하위 p개의 비트를 고려하지 않음, N 은 소수(Prime Number)를 사용하는 것이 좋음)

h(k)=k mod N

2. 곱셈법(Multiplication Method)

- 0<A<1 인 A 에 대해서 다음과 같이 구할 수 있음
- kA mod 1 의 의미는 kA 의 소수점 이하 부분을 말하며 이를 N 에 곱하므로 0부터 N 사이의 값이 됨
- N 이 어떤 값이더라도 잘 동작한다는 것이며 A를 잘 잡는 것이 중요

h(k)=⌊N(kA mod 1)⌋h(k)=⌊N(kA mod 1)⌋

 

DFS, BFS

---

DFS, BFS 모두 그래프를 탐색하는 방법
   -> 그래프에서 특정 노드나 경로를 찾기 위한 알고리즘

DFS(깊이 우선 탐색, Depth-First Search)

- 한 노드에서 시작해 가능한 한 깊이 내려가면서 탐색을 진행하는 알고리즘
- 스택(Stack) 자료구조를 사용해 구현, 재귀로 구현
- 탐색했던 노드를 다시 탐색하는 것을 방지하기 위해 '방문 처리' 필요!

function DFS(graph, start):
    visited = set()
    stack = [start]
    while stack:
        vertex = stack.pop()
        if vertex not in visited: // 노드에 방문하지 않은 경우
            visited.add(vertex)
            stack.extend(set(graph[vertex]) - visited)
    return visited

 

BFS(너비 우선 탐색, Breadth-First Search)

- 한 노드에서 시작해 인접한 노드를 먼저 탐색한 후, 그 다음 인접한 노드를 탐색하는 방식(같은 레벨부터 우선 탐색)
- 큐(Queue) 자료구조를 사용해 구현
- 탐색했던 노드를 다시 탐색하는 것을 방지하기 위해 '방문 처리' 필요!

function BFS(graph, start):
    visited = set()
    queue = [start]
    while queue:
        vertex = queue.pop(0)
        if vertex not in visited: // 노드 재방문을 방지
            visited.add(vertex)
            queue.extend(set(graph[vertex]) - visited)
    return visited

0-1 BFS 알고리즘
https://nicotina04.tistory.com/168

 

Graph, Tree

---

트리(Tree)

노드(Node)로 이루어진 자료구조

- 하나의 루트 노드를 가짐
- 루트 노드는 0개 이상의 자식 노드를 갖고 있음
- 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있음(반복적으로 정의됨)

특징

- 사이클(cycle)이 존재할 수 없음
- 노드들은 특정 순서로 나열될 수도 있고, 없을 수도 있음
- 각 노드는 부모 노드와의 연결이 있을 수도 있고, 없을 수도 있음

 

종류

1. 이진트리(Binary Tree) : 각 노드가 최대 두 개의 자식을 갖는 트리

2. 이진 탐색 트리(Binary Search Tree) : 특정 순서를 따르는 속성이 있는 이진 트리

`모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들`

오른쪽 트리의 경우 12가 8의 왼쪽에 있기 때문에 이진 탐색 트리가 아님3. 완전 이진 트리(Complete Binary Tree) : 트리의 계층에서 노드가 왼쪽부터 오른쪽으로 순서대로 채워진 트리

4. 전 이진 트리(Full Binary Tree) : 모든 노드의 자식이 없거나 정확히 두 개 있는 경우 / 자식이 하나만 있는 노드가 존재하면 안됨

5. 포화 이진 트리(Perfect Binary Tree) : 전 이진 트리이면서 완전 이진 트리인 경우

*트리 순회 방식

1. 전위 순회(pre-order traversal) : 현재 노드, 왼쪽 자식, 오른쪽 자식 순서로 방문
2. 중위 순회(in-order traversal) : 왼쪽 자식, 현재 노드, 오른쪽 자식 순서로 방문
3. 후외 순회(post-order traversal) : 왼쪽 자식, 오른쪽 자식, 현재 노드 순서로 방문

---

그래프(Graph)

노드와 그 노드를 연결하는 간선(edge)으로 이루어진 구조

특징

- 방향성이 있을 수도 있고, 없을 수도 있음
- 여러 개의 고립된 부분 그래프로 구성될 수 있음
- 모든 정점 쌍간에 경로가 존재하는 그래프는 '연결 그래프'라고 부름
- 사이클이 존재할 수도 없고 존재하지 않을 수도 있음(트리는 사이클이 존재하지 않음)
- 인접 리스트(연결 리스트), 인접 행렬(2차원 배열)로 표현할 수 있음

 

 

Dynamic Programming, Greedy Algorithm

---

DP(동적 프로그래밍, Dynamic Programming)

- '문제의 일부분을 풀고 그 결과를 재활용하는 방법'
- 하나의 문제를 중복되는 서브 문제로 나누어 푸는 '분할 정복(Divide and Conquer)'와 유사한 개념

특징

- 반복되는 서브 문제(Overlapping Subproblems) : 메인과 서브 문제를 같은 방법으로 해결할 수 있어야 함
- 최적 부분 구조(Optimal Substructure) : 메인 문제 해결 방법을 서브 문제에서 구하여 재사용하는 구조여야 함

방법론

1. 메모이제이션(하향식 방법) : 메인 문제를 분할하면서 해결

- 문제의 구조가 재귀적인 형태로 표현되는 경우 스택을 사용하는 메모이제이션 활용
- 재귀를 사용하기 때문에 스택 오버 플러우 발생 가능성이 있음

2. 타뷸레이션(상향식 방법) : 가장 작은 문제를 먼저 해결하고 최종적으로 메인 문제를 해결

- 반복적인 계산이 필요한 경우 배열을 사용하는 타뷸레이션 활용
- 배열을 사용하므로 메모리 공간이 많이 필요함

---

탐욕 알고리즘(Greedy Algorithm)

무식한 알고리즘...
- 현재 상황에서 지금 당장 좋은 것만 고르는 방법
- 각 단계마다 최적해를 찾는 방법
- 해결해야 할 전체 문제의 개수를 줄이기 위해 개별적으로 문제를 해결
- 지금의 최적해가 반드시 전체 문제의 최적의 해를 보장하지 않음

 

 

균형 이진 트리(Balanced balanced search tree, BST)

---

모든 노드의 좌,우 서브 트리 높이가 1이상 차이나지 않는 트리

노드의 삽입과 삭제 일어날 때 균형을 유지하도록 하는 트리

-> AVL 트리, Red-Black 트리

AVL 트리

- 노드가 삽입, 삭제될 때 트리의 균형을 체크하고 유지하는 트리
- Balance Factor : 왼쪽 서브트리 높이 - 오른쪽 서브트리 높이 (차이가 절대값 1 이하가 되도록 균형 유지)

회전 연산

1. 단순 회전 : LL, RR

LL(Left-Left) : 오른쪽으로 1회 회전 (중앙 노드를 피벗)

RR(Right-Right) : 왼쪽으로 1회 회전 (중앙 노드를 피벗)

2. 이중 회전 : LR, RL

LR(Left-Right) : Left와 Right의 위치를 교체하고, 일자로 노드를 정렬 후 오른쪽으로 회전 (중앙 노드를 피벗)

RL(Right-Left) : Right와 Left의 위치를 교체하고, 일자로 노드를 정렬 후 왼쪽으로 회전 (중앙 노드를 피벗)

---

RB 트리(Red-Black Tree)

- 루트 노트와 리프 노드의 색은 black(NIL 노드는 black)
- red 색 노드의 자식은 black(Double red 불가)
- 모든 Leaf 노드에서 root노드 까지의 경로의 black 노드 수는 같음

위의 조건이 충족되지 않으면 Rebalancing!

 

[참고]
https://velog.io/@dnrwhddk1/%EA%B7%A0%ED%98%95-%EC%9D%B4%EC%A7%84-%ED%8A%B8%EB%A6%AC%EC%97%90-%EB%8C%80%ED%95%B4-%EC%9E%90%EC%84%B8%ED%9E%88-%EC%95%8C%EC%95%84%EB%B3%B4%EA%B8%B0-%EB%B9%84%EC%84%A0%ED%98%95-%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0