해싱 검색 결과

해당 글 2건

Codeforces Round #625 - D. Reachable Strings

https://codeforces.com/contest/1320/problem/D Problem - D - Codeforces codeforces.com 두 문자열이 서로 연결되어있다(reachable)는 것을 다음과 같이 정의한다. 어떤 문자열에서 011 혹은 110 이 등장하면 그것을 각각 110, 011로 바꾸는 동작을 반복하면 다른 문자열과 같아질 수 있다.(원문 디스크립션 예시 참고 바람) 초기 문자열(S)이 주어지고 l, r, len 쿼리 형식으로 입력이 주어진다. S[l,l+1,...l+len-1]과 S[r,r+1,...r+len-1] 이 서로 reachable하면 Yes, 아니면 No를 출력하여라. 곰곰히 고민해보면 1이 두개 연속으로 있는 부분을 지워도 상관이 없다. 1이 달랑 한 개만 ..
Problem Solving 2020. 3. 4. 17:45

문자열 Hashing에 대하여

Hash는 특정 조건을 만족하는 함수이다. 정의역은 굉장히 넓고 그에 비해 치역은 좁다. 그래도 충분히 넓어서 서로 다른 정의역 원소에 대해 함수값이 충돌할 가능성이 적다. 치역은 보통 C++에서의 long long 등의 자료 형태로 표현되어 처리하기 간단하다. 그렇기 때문에 해시값이 같은 경우 두 대상은 서로 같을 확률이 아주 높다. 특히 부분 문자열에 대한 문제에서 많이 사용한다. 부분 문자열끼리 서로 완벽하게 비교하는데 걸리는 시간은 너무 오래 걸린다. 그렇기 때문에 해시값을 통해 비교와 처리를 하는 경우가 많다. 문자열 Hashing을 사용하는 문제 예시 https://www.acmicpc.net/problem/10840 10840번: 구간 성분 첫 두 줄에 신호 서열이 공백 없는 하나의 문자열로..
Problem Solving 2020. 2. 21. 00:00