라빈카프, 카운팅 정렬, 선택 정렬, 퀵 정렬
Hash
해싱
- 가변길이 데이터를 그 데이터를 표현하는, 식별할 수 있는 고정길이의 데이터로 변환
해시함수
- 데이터를 입력 받아 고정길이의 데이터로 변환해주는 함수
- 반환값 : 해시, 해시코드
해시 주요 사용 목적
- 데이터를 빠르게 검색, 저장하기 위해 사용
- 데이터의 무결성체크 (위/변조) (눈사태효과)
- 민감한 데이터의 보안처리 (해시: 단방향)
해시함수의 성질
- 결정론적 : 같은 input에 대해서는 같은 output 반환 -> salting으로 해결
- 고르게 분포되는 해시값 생성
- 고유한 해시값 생성(최대한 충돌 최소화)
- 데이터의 빠른 검색을 목적으로 하는 경우 해시함수의 처리 속도도 빠르도록 -> Key Streching으로 해결
해시 충돌
- 다른 데이터인데 같은 해시값을 갖는 경우
- 다른 데이터이고 해시값도 다른데 나머지 연산 처리해서 같은 결과를 얻게되는 경우
해시 충돌 해결
- open addressing : 선형탐사, 이차탐사
- seperate chaining : 같은 해시를 갖는 데이터를 연결리스트나 트리로 관리하는 방법
- bucket resizing :
보완 방법
- Salting : 원본 + salt => hashing
- key Streching : 해싱 과정을 반복처리
종류
PBKDF -> BCRYPT -> SCRYPT -> ARGON
라빈 카프
문자열 검색을 위해 해시 값 함수를 이용
패턴 내의 문자들을 일일이 비교하는 대신에 패턴의 해시 값과 본문 안에 있는 하위 문자열의 해시값만을 비교
최악의 시간 복잡도는 O(MN)이지만 평균적으로는 선형에 가까운 빠ㅏ른 속도를 가지는 알고리즘
패턴의 길이가 커지면 길이를 일정 자리수로 맞추기 위해 mod연산을 취해주는 것 주의
카운팅 정렬 O(n+k)
n은 리스트 길이, k는 정수의 최대값
빈도수를 저장한 배열과 빈도수의 누적합 배열을 만들어준다
맨 뒤에서부터 누적합의 배열을 이용하여 정렬 배열을 만들어준다!
선택 정렬 O(n^2)
주어진 리스트중에서 최소값을 찾는다
그 값을 맨 앞과 교환한다.
앞을 제외한 나머지 리스트를 대상으로 과정을 반복한다.
퀵 정렬 O(nlogn)
주어진 배열을 두개로 분할하고 각각을 정렬한다.
pivot item을 중심으로, 이보다 작은 것은 왼편, 같거나 큰 것은 오른편에 위치시킨다.
숙제
정처기 실기 공부, 1 알고리즘
기록하고 공유하는 개발자