Approach 라빈-카프 방법으로 접근하였다. 1. 일단 그림의 각 행에 대해서 Rabin fingerprint 해시함수를 활용하여 해싱을 한다. 2. 1에서 구한 해싱값을 이용하여 다시 해싱을 한다. 단, fingerprint_x를 다르게끔 해싱을 한다. 3. 걸작에 대해서도 동일하게 1, 2과정을 반복해준다. 단, 걸작의 크기가 그림의 크기보다 클 수 있으므로 동일한 크기를 기준으로 해싱을 해준다. 4. 믿음과 신뢰를 가지고, 해싱한 값이 같으면 동일한 패턴이 나왔다고 생각해준다 kmp나 야호코라식 등등으로 접근할 수 있다는데, 차후에 다시 풀어보는 것으로.. 라빈-카프 알고리즘에 대해서는 다음 블로그를 참고하도록 하자. https://m.blog.naver.com/kks227/22092727216..
[백준 10538번] [Rabin-karp] 빅 픽쳐
Approach 라빈-카프 방법으로 접근하였다. 1. 일단 그림의 각 행에 대해서 Rabin fingerprint 해시함수를 활용하여 해싱을 한다. 2. 1에서 구한 해싱값을 이용하여 다시 해싱을 한다. 단, fingerprint_x를 다르게끔 해싱을 한다. 3. 걸작에 대해서도 동일하게 1, 2과정을 반복해준다. 단, 걸작의 크기가 그림의 크기보다 클 수 있으므로 동일한 크기를 기준으로 해싱을 해준다. 4. 믿음과 신뢰를 가지고, 해싱한 값이 같으면 동일한 패턴이 나왔다고 생각해준다 kmp나 야호코라식 등등으로 접근할 수 있다는데, 차후에 다시 풀어보는 것으로.. 라빈-카프 알고리즘에 대해서는 다음 블로그를 참고하도록 하자. https://m.blog.naver.com/kks227/22092727216..
2022.02.09