해싱1 문자열 해싱(String Hashing) 해싱 알고리즘은 다양한 문제들을 해결하는데 도움을 준다. 문자열을 효과적으로 비교해야 하는 문제들이 있다. 각 문자들을 비교해서 브루트 포스(brute force) 방법으로 문자열(s1, s2)을 비교하는 경우 시간복잡도는 O(min(|s1|, |s2|))가 된다. 더 효과적으로 비교하는 방법의 아이디어는 문자열을 정수형으로 바꾸는 것부터 시작한다. 문자열 대신 숫자를 비교하게 된다면 시간복잡도는 O(1)이 된다. 문자열의 해시(hash)라 불리는 정수를 얻기 위해 해시 함수(hash function)를 사용한다. 만약 두 문자열 "ss"와 "tt"가 같다면 그들의 해시 값도 같아야 한다. hash(문자열)을 문자열의 해시값이라고 한다면 hash("ss")와 hash("tt")가 같아야 한다. hash(.. 2020. 6. 20. 이전 1 다음