[필기노트] 검색 알고리즘, 재귀 알고리즘

== 검색 알고리즘 
선형 검색 : 무작위로 늘어놓은 데이터 집합에서 검색
이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색
해시법 : 추가, 삭제가 자주 일어나는 데잍 ㅓ집합에서 아주 빠른 검색
 - 체인 법 : 같은 해시값 데이터를 연결 리스트로 연결
 - 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시


-- 선형 검색
선형 검색 (linear search) : 직선 모양(선형)으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을 때 까지
 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘


보초법 (Sentinel method)
보초(Sentinel) : 검색하고자 하는 키 값을 배열 맨 끝에 저장하는 값


-- 이진 검색 (binary search)
이진 검색 (binary search) : 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘
 - 배열의 데이터가 정렬되어 있어야한다.



-- 해시법 (Hashing)
해시법 (Hashing) : 데이터를 저장할 위치 = 인덱스를 간단한 연산으로 구현하는 것

해시 함수 (hash function) : key를 해시값으로 변환하는 과정 

버킷 (bucket) : 해시 테이블에서 만들어진 원소 

충돌 (collision) : 저장할 버킷이 중복되는 현상 

체인법 (chaining) : 해시값이 같은 원소를 연결리스트로 관리한다.
오픈 해시법 (open hashing) : 빈 버킷을 찾을 때까지 해시를 반복한다.

체인법 (chaining) : 해시값이 같은 데이터를 체인 모양의 연결리스트로 연결하는 방법
 - 배열의 각 버킷(해시 테이블)에 저장하는 것은 Index를 해시값으로 하는 연결리스트의 앞쪽 노드를 참조하는 것


SHA256 : RSA의 FIPS 알고리즘을 바탕으로 하며, 주어진 Byte 문자열의 해시값을 구하는 해시 알고리즘 생성자

encode() : key를 str 형 문자열로 변환한 뒤 그 문자열을 encode() 함수에 전달하여 바이트 문자열을 생성

hexdigest() : 해시값을 (16진수) 문자열로 꺼낸다.


-- 오픈 주소법 (Open Addressing)
오픈 주소법 (Open Addressing) : 충돌이 발생했을 때 Rehashing을 수행하여 빈 버킷을 찾는방법
 - 닫힌 해시법 (Closed Hashing)이라고도 함


-- 실행 결과 비교
체인법
 - 해시값이 같은 데이터를 연결하는 연결 리스트가 Bucket 1 에 연결되어 있다.

오픈 주소법
 - 나중에 추가한 데이터는 재해시 결과 Buekct 2 에 등록되어 있다.
 - 데이터를 삭제한 뒤 Buekct 2는 Status.DELETED로 삭제 완료 속성이 들어있다.

 

 

== 재귀 알고리즘

재귀 (Recursion) : 자기자신을 포함하고 다시 자기 자신을 사용하여 정의되는 경우 
 - 풀어야 할 문제나 계산할 함수 또는 처리할 자료구조가 재귀적으로 정의되는 경우에 적용

재귀 호출 (Recursive Call)
 - 팩토리얼값을 구하기 위해 다시 자신과 똑같은 Factorial() 함수를 호출 한다.
 - 이런 함수의 호출을 재귀 호출이라 한다.

직접 재귀 (Direct recursion)
 - 자신과 동일한 함수를 호출하는 방식

간접 재귀 (Indirect recursion)
 - a() 함수가 b() 함수를 호출하고 다시 b() 함수가 a() 함수를 호출하는 구조


최대 공약수 (GCD : Greatest common divisor)
 - 두 정숫값이 주어질 때 큰 값을 작은 값으로 나누어 떨어지면 작은 값이  최대 공약수
 - 나누어 떨어지지 않으면 작은 값과 나머지에 대해 같은 과정을 나누어 떨어질 때까지 재귀적으로 반복한다.


유클리드 호제법 (Euclidean algorithm) ☆
 - y가 0이면 : x
 - y가 0이 아니면 : GCD(y, x%y)


순수한 재귀 (Genuinely recursion)
 - 하나의 함수 안에서 재귀 호출을 여러 번 실행 하는 함수

하향식 분석 (Top-down analysis)
 - 가장 위쪽에 위치한 상자의 함수 호출부터 시작하여 게단식으로 자세히 조사해 나가는 분석 방법

상향식 분석 (bottom-up analysis)
 - 아래쪽부터 쌓아 올리며 분석하는 방법