hashing (2) 썸네일형 리스트형 88. Rabin-Karp 라빈-카프 알고리즘(Rabin-Karp Algorithm)은 해싱을 이용하여 문자열을 검색하는 알고리즘이다. 이 알고리즘은 주로 부분 문자열들이 동일한지의 여부를 빠르게 판별해야 하는 경우에 쓰이는데, 각각의 부분 문자열을 일일히 해싱하는 것은 시간이 너무 오래 걸리므로 더 빠른 방법이 요구된다. Rabin Fingerprint는 이러한 문제를 해결할 수 있는 해싱 방법으로, 다음과 같은 형태로 나타낼 수 있다.$$f(x, n) = \sum_{k=0}^n(s_k \cdot x^k) = s_0 + s_1x + s_2x^2 + \ldots + s_{n-1}x^{n-1} + s_nx^n$$일반적인 라빈-카프 알고리즘은 이 식을 약간 변형해서 다음과 같이 만든 다음 해시값을 계산한다.$$f(x, n) = \su.. 85. Hashing 해싱(Hashing)은 길이가 정해지지 않은 임의의 데이터를 길이가 정해진 데이터로 변환하여 표현하는 것을 말한다. 일반적으로 해싱의 대상이 되는 '길이가 정해지지 않은 임의의 데이터'는 문자열인 경우가 많으며, 해싱의 결과인 '길이가 정해진 데이터'는 정수값으로 나오는 경우가 많다. 이런 이유로 이 블로그에서는 문자열을 정수로 해싱하는 경우만 다루지만, 해싱의 대상과 결과가 항상 이렇게 될 필요는 없다. 해싱에 대해 알아보기 전에 왜 해싱이 필요한지를 알아야 한다. 문자열을 해싱하는 것이 그다지 특이한 일이 아니라는 것은 문자열을 그대로 사용할 경우 큰 단점이 생기는 상황이 있다는 것을 의미한다. 이 상황은 문자열을 검색하는 상황이다. 정수나 실수 데이터를 비교할 경우 단순히 한 번(경우에 따라 두 번.. 이전 1 다음
