알고리즘 14주차

 

공간으로 시간을 살 수 있나요?

Yes! 가능한 모든 입력에 대해 답을 미리 구해서 저장해 놓으면 가능하다.

However! 가능한 입력이 거의 무한한 대부분의 문제는 사용할 수 없다. 공간이 무한하지 않기 때문이다.

Therefore! 현실적인 수준에서 타협하여 이 전략을 사용할 수 있다.

---

해싱 hashing

해시 함수를 사용해 입력된 키(값)가 저장될 위치를 바로 계산한다

 

해싱의 구조

키 → 해시함수 → 해시 테이블(hash table)

해시함수 h(key) 는 키값을 통해 레코드의 위치인 해시 주소(버킷값)를 계산한다.

M x N 해시 테이블은 M개의 버킷으로 이루어졌으며, 하나의 버킷은 N개의 슬롯으로 이루어져 있다.

 

만약 서로 다른 키가 해시 함수에 의해 같은 해시 주소로 계산된다면?

(... 이를 충돌 collision 이라 부른다) 동일한 버킷의 서로 다른 슬롯에 저장한다.

 

좋은 해시 함수의 조건

- 충돌이 적게 발생한다

- 해시 주소(반환값)가 테이블의 주소 영역에서 고르게 분포되어야 한다

- 계산이 빨라야 한다

 

제산함수

h(key) = key % M

버킷의 수(M)이 소수 prime number인 것이 좋다 

 

만약 버킷에 존재하는 슬롯의 수가 부족하다면? 즉, 충돌이 슬롯의 수보다 많이 발생한다면?

(... 이를 오버플로 overflow 라 부른다) 개방주소법(선형 조사, 이차조사, 이중 해싱) 또는 체이닝을 통해 해결한다

 

이상적인 해싱: 충돌이 0회 발생하는 경우. 즉, 탐색 키 자체가 해시 주소가 되는 경우. 키의 범위가 클수록 공간을 많이 차지한다.

실제의 해싱: 충돌과 오버플로우가 빈번하게 발생할 수 있다. 

 

개방주소법 (1) 선형 조사법

계산된 주소에 빈 슬롯이 없을 경우, 순서에 따라 다음 슬롯으로 이동하여 빈 슬롯이 있으면 그 자리에 키를 저장한다

 

개방주소법 (2) 이차 조사법

선형조사법에서 다음 주소(+1)로 이동하는 것이 아니라, 제곱의 순으로 움직인다

 

개방주소법(3) 이중 해싱법

충돌이 발생하면 별개의 해시 함수를 이용해 다음 위치를 결정한다. 

 

---

백트래킹 backtracking

해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법이다

예) 미로에서 길을 찾을 때 막다른 길을 발견하면 분기접으로 돌아와 선택하지 않은 길을 탐색한다

 

상태 공간 트리: 어떤 문제에 대한 모든 상태를 노드로 포함하고 있는 트리

 

틱택토 게임: 오(5)목이 아니라 삼(3)목 

틱택토 게임의 상태 공간 트리: 단말 노드는 승부가 결정된 상태의 노드이다.

백트래킹 전략: 루트에서부터 깊이 우선 탐색을 통해 방문한 노드가 문제에서 요구하는 해가 아니라고 판단이 될 경우, 이전 노드로 되돌아 나온다

 

│ In Laymans Terms │ Brute-Force and Tic Tac Toe

 

N-Queen: NxN 체스 보드에 N개의 퀸을 배치한다. 단, 모든 퀸은 서로 가로/세로/대각선 방향으로 중복 배치될 수 없다.

유효성 검사

1. 상하좌우 같은 줄에 이미 위치한 퀸(Queen)이 있는가?
2. 대각선의 같은 줄에 이미 위치한 퀸(Queen)이 있는가?
3. 현재 놓는 퀸이 N번째(마지막) 퀸(Queen)인가?

 

백트레킹 전략: 첫 행/열부터 순서대로 퀸을 배치하되, 불가능한 위치에 퀸이 배치될 경우 탐색을 중지하고 백트래킹하여 다음 행으로 이동한다

https://yonghwankim-dev.tistory.com/262

 

 

---

 

해싱

 

2402-ECC-AlgorithmStudy/백준/Bronze/15829. Hashing at d61bdd4c02022ee2efd96ae916ae3ccd8c63daf8 · daj33/2402-ECC-AlgorithmSt

 

 

크면서 작은 수

2402-ECC-AlgorithmStudy/백준/Silver/2992. 크면서 작은 수 at d61bdd4c02022ee2efd96ae916ae3ccd8c63daf8 · daj33/2402

 

Cities and States

 

2402-ECC-AlgorithmStudy/백준/Silver/14171. Cities and States at d61bdd4c02022ee2efd96ae916ae3ccd8c63daf8 · daj33/2402-E

 

N-Queen

 

2402-ECC-AlgorithmStudy/백준/Gold/9663. N－Queen at 8ac06fa383ae09e32f13bf616e6608ae3c4a6e5b · daj33/2402-ECC-AlgorithmStu