CH 11 더 공부해야할 것
- 이진 탐색 트리 : 왼쪽에는 더 작은 값은 가진 정점, 오른쪽에는 더 큰 값을 가진 정점이 위치
> 항목 탐색 시 평균적으로 O(log n), 최악의 경우 O(n)
> 단점 : 임의 접근 불가, 트리가 얼마나 균형 잡혀 있는가에 따라 평균 성능 달라짐
** B-트리 : 하나의 노드가 여러 데이터를 가질 수 있는 트리
** 레드-블랙 트리 : 스스로 균형을 맞추는 이진 탐색 트리
** 힙 트리 : 가장 크거나 가장 작은 값을 빠르게 찾기 위해 만든 트리
** 스플레이 트리 : 자주 탐색하는 키를 가진 노드가 루트에 가깝게 위치한 트리
- 역 인덱스 : 데이터 값과 위치를 매핑한 자료 구조 (검색 시스템에 유용)
ex. 안녕 이라는 단어 검색 시 웹페이지 A, B를 보여줌
- 퓨리에 변환 : 임의의 입력 신호를 다양한 주파수를 갖는 주기 함수들의 합으로 분해하여 표현 (시간 영역의 함수를 주파수 영역의 함수로 변환)
ex. 신호 처리에 유용 (음악 압축, 중저음 영역 확대 등)
- 병렬 알고리즘 : 여러 개의 코어에서 동시에 처리되도록 하는 방법
> 속도 향상이 항상 선형적이지는 않음 (이유 : 병렬화 관리 부담, 로드 밸런싱)
- 맵 리듀스 : 분산 알고리즘의 일종, 아주 많은 일련의 작업 처리 시 시간 단축에 유용, 아파치 하둡 등을 통해 사용 가능
> 맵 함수 : 배열을 입력 받아 모든 원소에 같은 함수 적용
> 리듀스 함수 : 리스트 전체의 원소를 하나의 원소로 축소
- 블룸 필터 : 특정 원소가 집합에 속하는지 검사하는데 사용하는 확률형자료구조, 저장 공간이 아주 작음
> 틀린 답을 맞다고 판단할 가능성 … O
> 맞는 답을 틀렸다고 판단할 가능성 … X
- 하이퍼로그로그 : 집합에 있는 똑같은 원소의 갯수를 대략적으로 세기 가능 (근사값)
- SHA 알고리즘 : 문자열을 받아 문자열에 대한 해시값 반환, 패스워드 확인 시 사용 (보안 해시 알고리즘)
ex. hello > 2cf25bdbn …
- 지역 민감 해시 함수 : 문자열이 ‘조금’ 바뀌면 해시값도 ‘조금’ 바뀌는 함수, 비슷한 항목을 찾아낼 때 유용
** SHA : 지역 민감적이지 않음 … 입력 문자열이 비슷해도 해시값은 완전히 다름
- 디피-헬만 키 교환 : 공개키-개인키 보유, 공개키로 암호화, 개인키로 복호화
- 선형 프로그래밍 : 제한 조건에서 최대화 시 사용
** 심플렉스 알고리즘 : LP문제를 푸는 대표적인 알고리즘, 임의의 가능해로 탐색을 시작해 최적해를 찾는 알고리즘
참고자료
Hello Coding 그림으로 개념을 이해하는 알고리즘
