== 검색 알고리즘
선형 검색 : 무작위로 늘어놓은 데이터 집합에서 검색
이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색
해시법 : 추가, 삭제가 자주 일어나는 데잍 ㅓ집합에서 아주 빠른 검색
- 체인 법 : 같은 해시값 데이터를 연결 리스트로 연결
- 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시
-- 선형 검색
선형 검색 (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)
- 아래쪽부터 쌓아 올리며 분석하는 방법
'필기노트' 카테고리의 다른 글
[Python 코딩의 기술] Chapter 2 리스트와 딕셔너리 (0) | 2021.10.16 |
---|---|
[Python 코딩의 기술] Chapter 1 파이썬 답게 생각하기 (0) | 2021.10.12 |
[Javascript 코딩의 기술] Chapter 4 조건문을 깔끔하게 작성하라 (0) | 2021.10.04 |
[Javascript 코딩의 기술] Chapter 3 특수한 컬렉션을 이용해 코드 명료성을 극대화하라 (0) | 2021.10.04 |
[필기노트] Event -Driven, Event Loop, Task Queue (0) | 2021.09.29 |