혼잣말처럼 넘기는 알고리즘 (파트1)

[이미지 출처: jkfran.com]
▼ 파트1
1. 알고리즘?	1)  개념  2) 수도코드(pseudocode)  3) 분석과 효율
2. 정렬	1)  O(n²)급 →선택 정렬, 버블 정렬, 삽입 정렬, 셸 정렬  2) O(n·logn)급 →퀵 정렬, 합병 정렬, 힙 정렬  3) O(n)급 →계수 정렬, 기수 정렬, 버킷 정렬
3. 탐색(search)	1)  개념  2) 기본형  3) 트리 탐색 →이진 탐색 트리, 2-3-4트리, B-트리, 레드-블랙 트리  4) 해시테이블 →해시함수, 충돌 해결
▷ 파트2  그래프 / 동적 프로그래밍
▷ 파트3  스트링 알고리즘 / NP-완전 문제 / 유전 알고리즘
기타. 참조자료

① 일반적인 강의형 포스팅보다는 개인적인 노트정리입니다.

// 💬 이 주석은 자체적인 언어(?)로 해석/재구성한 메모다.

② 참조 서적중 초판이 1994년 이고 2020년 이후에도 개정판이 나온거 같은데 그걸로 봐도 되지 않을까 싶지만 제가 가지고 있던건 구판이다보니 이걸 기준으로.

③ 참조한 주요 서적은 C기준이다보니 저는 예제코드를 JAVA, C#, 파이썬 3.x에서 오가고자 합니다.

④ 예제는 웹 컴파일로도 가능하긴 하지만, 가급적 브레이크 포인트를 걸면서 보는쪽이 좋을거 같아 로컬에서 구동할 개발 환경 세팅자료 참조 넣어둡니다.
→ 비주얼 스튜디오 코드(VS code)를 다용도 세팅 -자바, C#, 파이썬- [🔗티스토리][🔗블로거]

⑤ 클라우드 드라이브에 올려둔 소스 코드의 변경이력은 해당 포스팅에 별도로 남기지 않습니다.

⑥ 시간 날 때마다 작성을 하다보니 자체 제작한 예시 그림은 스타일이 균일치 못 한 경우가 있습니다.

▼ 1. 알고리즘❔

1) 개념 📂

 "간단한 문제일지라도 주어진 문제를 해결하기 위해서는 일련의 단계적인 처리 과정이 요구된다.

 한편, 이런 처리 방법과 과정은 같은 문제일지라도 부여되는 조건에 따라 충분히 달라질 수 있다. ...(중략)... 이런 일련의 문제 풀이 과정은 결국 비용과 효용성 등을 고려해서 선택되고 적용되기 마련이다.

 알고리즘(algorithm)은 주어진 문제를 해결하기 위한 일련의 단계적인 처리과정으로, 이는 음식을 만들기 위한 조리법(recipe)에 비유할 수 있다."

(p.3, 알고리즘, 2024)

 "알고리즘에는 우선 주어지는 문제가 있고, 이 문제를 해결하기 위한 순서적인 동작들이 있다. 이 동작들은 또한 자료 구조를 필요로 한다.

 알고리즘을 개발하는데 가장 먼저 선행되어야 할 것은 바로 주어진 문제를 잘 이해하는것이다. 주어지는 문제는 문제 그 자체만이 아니라, 문제가 주어지는 상황도 포함이 된다."

(p.27, C로 배우는 알고리즘, 1994)

/* 💬 범용적+다용도인 알고리즘은 있어도 모든 상황(처리되는 데이터 용량, 주어진 시간 등등)에서 전부 효율적인 알고리즘이 있다로 말하는 부류는 좀 많이 희안하게 보게 됨. 제한된 몇 가지 환경만 염두하고 말하는거 아닌지로. */

2) 수도코드(pseudocode)

 알고리즘을 설계하면서 표현하는데는 크게 3가지가 있습니다. 프로그래밍 언어, 순서도 그리고 수도코드(혹은 의사코드)입니다.

 물론 실행 자체를 놓고 보면 프로그래밍 언어가 우세지만, 메인스트림이 되는 언어가 바뀔때도 있고 해당 언어에만 가능한 문법도 있다보니 특정 언어를 모르는 사람에게 전달이 어려워집니다.

// 💬 한번 생긴 대세가 영원했으면, 2020년 이후에도 어셈블리나 파스칼, 베이직 등등...

 순서도는 도식을 통한 전달력은 가장 좋지만, 고대의 상형문자가 지금의 알파벳이나 한자로 바뀐것처럼 복잡도가 높은 알고리즘 문서화에는 그리 좋은 선택지는 아니죠.

 이렇게 3개중 남는건 수도코드입니다. 자연어로 프로그래밍 언어처럼 표기하고 기술하니 프로그래밍 언어쪽 문법에 자유롭고 다른 사람에게 전달 및 설명하는데 제약도 낮아집니다.

// 💬 어떻게 동작하는지만 설명한 수도 코드를 넘기니, 업무 지시나 전달 받을때 그것만 보고 구현들어가곤 했으니깐 프로젝트내 문서중 프로그램에 가까운 문서 중 하나가 됨.

3) 분석과 효율

3-1) 알고리즘의 조건

알고리즘은 기본적으로 4가지 조건을 만족해야 합니다.

입출력: 0개 이상의 입력, 1개 이상의 출력

명확성: 단순하고 명확하게 기술된 단계들

유한성: 실행된 알고리즘은 반드시 끝나야 합니다.//무한루프로 뻗으면 NG

유효성: 컴퓨터로 실행이 가능해야.

컴퓨터 과학이 아닌 공학 관점에서는 효율성도 중요도가 높은 항목.

3-2) 분석관련

공간복잡도	알고리즘 실행시 쓰이는 총 메모리 양. -> 컴파일시 고정적 할당, 실핼중 동적 할당 등등.
시간복잡도	알고리짐의 실행~완료까지의 수행시간으로 측정될수도. BUT! 실행환경 따라 유동적인 값이 됨.  입력되는 데이터 n에 대해서 최선 수행시간 B(n) 평균 수행시간 A(n) 최악 수행시간 W(n)이 나올때, 상한선인 W(n)이 알고리즘의 시간 복잡도에 대한 척도로 사용.
수행시간	코드내에서 각 문장이 수행되는 횟수의 합. 가령 for(i=0; i<n; i++)이 있을때, 수행시간은 n으로 처리.

- 데이터 입력 크기가 커질수록 알고리즘의 수행시간은 늘어나는데, 입력크기 n에 대한 함수로 표현된것으로 n의 최고차항 기준으로 어림값을 사용한다. //일종의 체급 분류 표기

예. f(n) = 2n³ - 10n의 시간복잡도는?

다항식내에서 n³이 가장 큰 차수를 가지고, 해당 계수인 2를 생략시키면

함수 f의 시간복잡도는 n³으로 분류된다.

3-3) 점근성능

[그림. 점근적 표기법 / 출처: dad-rock.tistory]

O-표기(빅 오) [점근적 상한]	c가 양의 정수이고 f(n) ≤ c·g(n)을 만족하면,  f(n) = O(g(n))
Θ-표기(빅 세타) [평균]	c1, c2가 양의 정수이고 c1·g(n) ≤ f(n) ≤c2·g(n)을 만족하는  즉, f(n) = O(g(n)) = Ω(g(n))이면  f(n) = Θ(g(n))
Ω-표기(빅 오메가) [점근적 하한]	c가 양의 정수이고 c·g(n) ≤ f(n)을 만족하면  f(n) = Ω(g(n))

 n의 값이 한자리수면 그리 큰 차이가 없겠지만, 점근성능 그래프처럼 n의 값이 커질수록 값이 덜 커지는쪽이 효율적이다.
예. T1=n^2와 T2=logn를 비교하면?

n=100이라 가정시,

T1=10000이고

T2=2 으로  logn급인 T2가 더 효율적인 알고리즘

3-4) 점화식

// 💬 점화식을 유심히 보면, 폐쇄형이 T(n) = Θ(n)쪽을 제외한 나머지 3종의 점화식 패턴을 읽을 수 있으니 그걸로 외우면 수월.

// 💬 고등학교 수학이 가물가물하신 경우를 위한 메모. log를 로그가 아니라, 10g(그램)이라 읽는 상황이 없으시게끔. (출처. 수학 선생님의 한탄)

폐쇄형	점화식
T(n) = Θ(n²)	T(n) = Θ(1)        = T(n-1) + Θ(n)
T(n) = Θ(n)	T(n) = Θ(1)      = T(n-1) + Θ(1) T(n) = Θ(1)      = T(n/2) + Θ(n) T(n) = Θ(1)      = 2T(n/2) + Θ(1)
T(n)  = Θ(n·logn)	T(n) = Θ(1)      = 2T(n/2) + Θ(n)
T(n) = Θ(logn)	T(n) = Θ(1)      = T(n/2) + Θ(1)

▼ 2. 정렬

* 데이터의 갯수는 n개고, 오름차순 정렬을 기준으로.

* 비교 기반은 O(n²)이나 O(n·logn)으로 수학적으로 n·logn이 최고 속도라 증명되었다 함.

* 예제용 소스 코드
📂구글 드라이브	[🔗JAVA][🔗C#][🔗PY3]
📂MS 드라이브	[🔗JAVA][🔗C#][🔗PY3]

1) O(n²)급

[🔗David Galles 교수, Comparison Sorting Visualization]

분류
① 선택 정렬 (Selection Sort)	- 제자리 정렬O, 안정적X. - 규칙. ⓐ data[i]이고 i=0 일때 ⓑ 미정렬된 부분(i~n-1)중 min값인 data[minIdx] 찾아냄. ⓒ 새로 찾은min값과 data[i]의 위치를 맞교환     i++; ⓓ (i<n-1)? ⓑ부터 다시 : 정렬 종료
② 버블 정렬 (Bubble Sort)	- 제자리 정렬O, 안정적O. - 규칙. 2중 for문내 data[i]와 data[i+1]를 비교&교환. 같은 값끼리 위치 교환X for문을 처음 돌릴때 정렬이 한번도 발생하지 않으면 정렬된 데이터로 판단하는걸로 최적화 가능.  데이터 입력에 따라 가변적→정렬된 데이터는 O(n)로 최적화 가능 // 💬 2칸 짜리 슬롯이 방향 따라 비교 및 위치 맞교환을 하면서 이동.
③ 삽입 정렬 (Insertion Sort)	- 제자리 정렬O, 안정적O. - 규칙. ⓐ data[i]이고 i=0 일때 ⓑ 미정렬된 부분(i ~ n-1)중 min값인 data[minIdx] 찾아냄. ⓒ tmp=data[minIdx];     data[i]~data[minIdx-1]의 값들을 옆으로 한 칸씩 ⓓ data[i]=tmp;     i++; ⓔ (i<n-1)? ⓑ부터 다시 : 정렬 종료  데이터 입력에 따라 가변적→정렬된 데이터는 O(n) // 💬 책꽂이 중간에 책을 빼내면 가장자리에서 그대로 밀어 중간의 공백을 없애고 가장자리쪽 빈 공간 넓히는거.
④ 셸 정렬 (Shell Sort)	제자리 정렬O, 안정적X.  삽입 정렬의 개량판. for문이 3중이나 n/2로 시작하는 부분 배열 때문에 k·n² // 💬 매 회차의 부분배열[i]끼리 비교해서 위치교환.

2) O(n·logn)급

[🔗David Galles 교수, Comparison Sorting Visualization]

[🔗David Galles 교수, Heap Sort Visualization]

분류
① 퀵 정렬 (Quck Sort)	- 제자리 정렬O, 안정적X.  데이터 입력에 따라 가변적→피벗이 min혹은 MAX이면 O(n²)  피벗(pivot)을 기준으로 분할 함수가 동작.  보통은 data[0]을 피벗으로 두고 처리, 임의성만 보장되면 평균성능 가능. // 💬 피벗이 배열내 최소/최대값이면 O(n^2)이 되는데도, 왜 이리 분류될까 싶지만, n이 커질수록 확률상(?) 그런 극단적인 경우가 0에 수렴해 무마되는건지 뭔지.
② 합병 정렬 (Merge Sort)	- 제자리 정렬X, 안정적O.// 💬 비교 기반중 예외적으로 제자리X -규칙. ⓐ 더는 쪼갤수 없을때까지 분할 ⓑ 정렬된 부분배열을 합쳐간다  전형적인 분할정복. 동일한 크기의 부분 배열이니 배열 크기가 짝수
③ 힙 정렬 (Heap Sort)	- 제자리 정렬O, 안정적X. - 초기힙을 구축하는 2가지 방법. ⓐ 배열에 값을 넣을때마다 노드 정렬. 부모-자식 레벨간 균형만 확인. 형제간 균형은 신경 안 씀. ⓑ 입력 순서대로 배열 생성후, 레벨 균형에 맞게 정렬.  내부 동작은 완전 이진트리. 힙 구조상, 값의 삽입/삭제가 용이.

3) O(n)급

[🔗David Galles 교수, Counting Sort]

[🔗David Galles 교수, Radix Sort]

[🔗David Galles 교수, Bucket Sort]

분류
① 계수 정렬 (Counting Sort)	- 제자리 정렬X, 안정적O.  입력된 값의 범위를 알고 있어야.
② 기수 정렬 (Radix Sort)	- 제자리 정렬X, 안정적O.  데이터 값을 자릿수별로 나누고, 자릿수를 안정적인 정렬로 정렬(계수 정렬 등)
③ 버킷 정렬 (Bucket Sort)	- 제자리 정렬X, 안정적O.  데이터 범위를 (확률적으로) 균등하게 나눠 버킷들에 넣음.  계수 정렬을 일반화한 형태.

▼ 3. 탐색(search)

* 데이터의 갯수는 n개고, 트리의 높이는 h
* 예시 및 설명들은 데이터에 중복되는 값이 없다는 전제로 처리.

* 탐색할 데이터가 저장된 곳이 주기억장치의 내부(internal)인지 외부(external)인지로 최종 속도가 달라지지만, 데이터에 접근하는 횟수를 줄이는건 어디건 유효한 문제.

* 예제용 소스 코드
📂구글 드라이브	[🔗JAVA][🔗C#][🔗PY3]
📂MS 드라이브	[🔗JAVA][🔗C#][🔗PY3]

1) 개념

 "탐색(search)은 여러 개의 원소로 구성된 데이터가 주어졌을 때, 그중에서 원하는 값을 갖는 원소를 찾는 것을 말한다. 이때 데이터의 형태는 리스트, 트리, 그래프 등 다양한 형태가 가능한다. ...(중략)...

 한편, 탐색 알고리즘에서는 기본적인 탐색 연산 외에도 여러가지 연산이 함께 고려되어야 한다. 주어진 데이터를 효율적으로 탐색하기 위해 정렬 등의 초기화 연산이 함께 필요할 수 있고, 주어진 데이터에 새로운 원소가 추가되거나 기존 원소가 제외되는 경우를 위해 삽입 연산이나 삭제 연산도 필요하다."

(p.131, 알고리즘, 2024)

 "검색이란 특정한 구조로 구성되어 있는 자료의 집합에서 주어진 키(key)에 해당하는 레코드를 찾아내는 것을 말한다. 검색할 자료는 특정한 구조로 편성되어 있는 경우가 많다.

...(중략)...

 그래서 검색 알고리즘은 단순히 자료를 찾는것에만 국한되는 것이 아니라 자료가 새로 추가되고 삭제될 때 어떻게 이 자료들이 특정한 구조를 계속 유지하느냐하는 문제도 포함되어 있어 데이터베이스를 구축하는 기본이 된다.

...(중략)...

 앞에서 말했듯이 검색 알고리즘의 대부분은 자료를 특정한 방법으로 조직화한다. 이렇게 조직화되어 있는 자료 파일에서 임의로 하나의 자료를 삽입하거나 삭제하면 자칫 전체 파일의 구조를 깨뜨리는 경우가 많다. 이렇게 해서 검색 알고리즘에서는 반드시 삽입 동작과 삭제 동작을 함께 제공해야 한다."

(pp.443-444, C로 배우는 알고리즘, 1994)

// 💬 정렬을 1차 함수라 한다면, 탐색은 3차 함수 이상인 무언가.

2) 기본형

분류
① 순차 탐색 (Sequntial search)	1차원 배열/리스트. - 탐색 O(n). 머리에서 꼬리 방향으로 하나씩 순차적으로 확인하면서 최대 n번의 확인. - 삭제 O(n). 탐색+확인된 값을 삭제. - 삽입 O(1). 시간 복잡도에 오탈자가 의심스럽지만 1맞다. 그냥 기존 꼬리뒤에 붙임. // 💬 배열이면 길이-1, 리스트면 꼬리 노드 체크.
② 이진 탐색 (Binary search)	정렬된 배열. 분할 정복 방식. - 탐색 O(logn). 탐색할 부분 배열에서 mid=⌊(LeftIdx+RightIdx)/2⌋ 기준으로 왼쪽이나 오른쪽 부분 배열로 범위를 줄이고, mid값을 재설정해 탐색해감. - 삭제 O(n). 탐색후, 탐색에 성공하면 해당값 삭제. - 삽입 O(n).       신규값이 MAX? (맨 뒤에):(신규보다 큰 원소들 한 칸씩 오른쪽) // 💬 번역에 따라서는 '이분 검색'으로도 쓰이는듯?

3) 트리 탐색

[🔗David Galles 교수, B-Trees]

- 트리 구조상, 데이터를 가진 노드는 기본적으로 다음과 같은 형태.

class TreeNode

{

   int data;

   TreeNode 좌측자식, 우측자식;// 💬 자식노드가 2개 이상인 트리는 배열로?

   ... ...

}

- 이진 트리에 공통된 2가지 규칙(혹은 성질) 있다.

ⓐ 한 노드를 기준으로 좌측 자식/서브 트리 키값들은 그 노드보다 작다.

ⓑ 한 노드를 기준으로 우측 자식/서브 트리 키값들은 그 노드보다 크다.

// 💬 트리 탐색은 어지간한 연산이 logn이긴한데, '이진 탐색'이랑 '이진 탐색 트리'가 처음에는 이름이랑 탐색 시간상 때문에 은근히 헷갈림.

분류
① 이진 탐색 트리	- 탐색 O(logn) ~ O(n). - 삭제 O(logn) ~ O(n). - 삽입 O(logn) ~ O(n).  최악의 성능은 경사트리 형태(노드n개=트리 높이h)가 될 경우.
② B-트리	- 탐색 O(logn). - 삭제 O(logn). 삭제키 기준으로 좌측 서브 트리내 max나 우측 서브 트리내 min을 끌어오고 규칙에 맞게 정렬 [🔗geeksforgeeks, 예제] - 삽입 O(logn). 새 키값이 오고 키값이 만석이다? 전체 키중 중간이 되는 키값을 기준으로 노드를 쪼개고 나서 부모(노드)로 보냄. - 규칙. (t는 자연수인 상수) 1 ≦ 루트(노드)의 키 갯수 ≦ 2t-1 (t-1) ≦ 루트(노드)외 키 갯수 ≦ 2t-1 각 k-노드는 (k-1)개의 키와 k개의 자식 이진 트리에 공통된 2가지 규칙 모든 리프(노드)의 레벨은 동일  트리 최대높이=logkn (k: 트리내 최대 자식수)  ✅ 균형 탐색 트리. // 💬 DB 시스템에 B+트리가 쓰이지만, 혼동은 NG
③ 2-3-4트리	B-트리 기반이라서 B-트리의 규칙 준수. - 탐색 O(logn). - 삭제 O(logn). - 삽입 O(logn). - 규칙. 각 k-노드는 (k-1)개의 키와 k개의 자식 이진 트리에 공통된 2가지 규칙 모든 리프(노드)의 레벨은 동일  BUT! 경사트리 막고,  2-3트리 삽입/삭제 연산보다 유리해도 (상대적으로)복잡한 구조가...  ✅ 균형 탐색 트리.
④ 레드-블랙 트리	노드 구조에 2가지 색상 표기 추가. - 탐색 O(logn). - 삭제 O(logn).  - 삽입 O(logn). - 규칙. 모든 노드는 검정이거나 빨강 루트는 무조건 검정이고, 모든 리프는 null 리프까지 가는 경로내 검정(노드)은 동일갯수(빨강은 해당X) 이진 트리에 공통된 2가지 규칙 모든 리프(노드)의 레벨이 같지는 않음.  2-3-4 트리를 이진 탐색 트리로 표현.//💬 그러니 B-트리 계열  ✅ 균형 탐색 트리. 리프(노드)의 레벨 차이가 2배를 넘지 않음.

4) 해시테이블

- 해싱: 해시함수를 이용해 테이블 주소값을 직접 생성. 주소값을 변환시 상수 시간이 걸림.
- 충돌(collision) 문제: 좋은 해시 함수는 상수 시간 탐색을 위해 계산 시간이 길지않고, 충돌시 발생하는 탐색/삽입/삭제를 위한 추가 작업을 최소화를 위해 충돌이 적어야 한다.
// 💬 해시함수는 정보보안에서는 암호에 쓰이고, DB 시스템에서는 해시 함수로 저장될 버킷을 배분한다. 상이한 레코드들이 동일한 버킷에 배분되어 '충돌'난 해당 레코드를 동거자(synonyms)라 하는데, 쉽게 말하면 다른 입력값이여도 해시함수를 거치면 동일한 값이 나오는 '충돌'문제가 존재하고 이를 해결하는 방법들도 개발된 상태다.

4-1) 해시 함수

① 정수 기반 [K: 키값, M:해시 테이블 크기]

제산 잔여법	해시함수1(int argKey) {    return (argKey % M); } → h(K) = K mod M
비닝(binning)	해시함수2(int argKey) {    return argKey / n; // n = 키 값범위 / M } → h(K) = K div n
중간 제곱법(mid-square)	해시함수3(int argKey) {    return ((argKey*argKey)/2^미사용 하위비트) % (2^사용하는 비트) } → h(K) = ((K²)/2^m)) mod 2^r // 💬 몇 개의 슬롯으로 해시한다 == 2^x

② 문자열 기반 [K: 키값, M:해시 테이블 크기]

비닝	문자_해시함수1(문자배열) {    return (int)(문자열[0].아스키코드값) - (int)("A".아스키코드값); } → h(K) = K[0] - A.아스키코드값  정수 기반과 달리, 문자열의 앞 부분을 이용 가능. 알파벳에서는 A를 0으로 둔 순서값을 쓰면 간편하나, 해시 결과 분포가 다소 쏠림.
단순합	문자_해시함수2(문자배열K) {    int sum = ∑ 문자열K[i].아스키코드값;// i:1~문자열길이    return (sum % TBL_SIZE); } → h(K) = (∑ K[i]) mod M  문자열내 코드값(졍수)를 합한후 제산 잔여법 처리. 코드값의 합을 쓰다보니 문자열의 순서는 고려X. 예. aBcD와 DBac는 상이한 문자열이라도 동일한 해시값
가중합	문자_해시함수3(문자배열K) {    int result = 0;    for i는 0~(문자열 길이-1)       result = (result * 가중치 + K[i]) % M;    return result; }  단순합의 단점을 보완한 방식. // 💬 가중치가 순서idx에 따른 차등된 포인트 부여하는 역할

4-2) 충돌해결법, 개방 해싱

[🔗David Galles 교수, Open Hash Tables (Closed Addressing)]

① 연쇄법

- 이미 값이 존재하는 주소로 해싱이 되어 출동이 나면, 해당 테이블 슬롯은 연결 리스트의 헤드가 되며 연결리스트들은 서로 별개로 존재.

- 해시 테이블과 연결 리스트가 주기억장치에 유지될 때 적합.

4-3) 충돌해결법, 폐쇄 해싱

- 해시 테이블 외의 저장공간X. 개방 주소법 사용됨. (개방 해싱에서 쓰이는게 아님.)

- 홈위치: 

[🔗David Galles 교수, Closed Hash Tables, using buckets]

[🔗David Galles 교수, Closed Hash Tables (Open Addressing)]

분류
① 버킷 해싱 (bucket hashing)	해시 테이블 = n의 버킷들 + 1개의 오버플로 버킷(공용)  버킷 전체가 메모리에. - 삽입: (일반)버킷의 빈슬롯에 순차적으로. 꽉 차면 오버플로 버킷에. - 탐색: (일반)버킷에서 탐색을 실채하면, 오버플로 버킷도 추가 탐색.
② 선형 탐사 (linear probing)	- 삽입: 충돌나면, 해당 위치부터 순차적으로 빈 슬롯을 찾아서 처리. BUT! 1차 클러스터링(primary clustering) 문제가 발생. →간단해도, 채워진 슬롯이 늘어날수록 평균 탐사 시간도 덩달아.
③ 2차 탐사 (quardratic probing)	1차 클러스터링 문제를 개선. - 삽입: 충돌이 나면,  빈 슬롯 찾을때까지 (h(K) + i²) mod M으로 새 주소(i=0부터 시작) BUT! 2차 클러스터링(secondary clustering) 문제가 발생. →개선을 위한 i²부분 때문에 오히려 쓰던 슬롯값만 나오게 됨.
④ 이중 해싱 (double hashing)	2차 클러스터링 문제까지 해결.  키값만 다르면, 같은 충돌 지점에서 출발해도 다른 탐사 순서. 좋은 이중 해싱은 탐사 순서의 상수가 M과 서로소. - 삽입: 충돌이 나면,  빈 슬롯 찾을때까지 (h(K) + i * h₂(K)) mod M으로 새 주소(i=0부터 시작) - 삭제: 삭제된 데이터가 있던 슬롯에는 비석(tomstone) 표시. 이를 통해 탐색 순서에 방해되지 않으면서 재사용 가능케.

▼ 기타. 참조자료

1) 서적

이관용, 김진욱 저. 알고리즘, 한국방송통신대학교출판문화원, 2024년.

이재규 저. C로 배우는 알고리즘, 세화, 1994년.

손진곤 저. 이산수학, 한국방송통신대학교출판문화원, 2021년.

2) 대학교 공개자료

Data Structure Visualizations, 미국 샌프란시스코 대학교 (by. David Galles) [🔗링크]

> Algorithms (접속: 2024-06-30)

3) 튜터링 사이트

사이트명
algorithmtutor	Binary Search Trees (BST) with code in C++, Python, and Java
Baeldung	Baeldung on CS [#]  Baeldung/Algorithms [#]
geeksforgeeks	Binary Search Tree [#] - Insertion in Binary Search Tree (BST) (갱신: 2023-07-28) - Searching in Binary Search Tree (BST) (갱신: 2023-12-21) - Deletion in Binary Search Tree (BST) (갱신: 2024-04-17)

4) 개인 블로그

티스토리

[Algorithms] Asymptotic Notation | 점근적 표기법 (접속: 2024-06-18)

블로거

혼잣말처럼 넘기는 자료구조 (파트4) (접속: 2024-07-07)

▼ 기타. 변경 내력

일자	변경 내력
2024-07-10	초안 및 일반 공개. [🔗blogger] [🔗티스토리].