[13일차] Hash (1)

오늘은 드디어 해쉬에 대한 내용을 배웠다. 사실 이전까지의 내용들은 학부 수업을 들으면서 조금씩이라도 공부한 내용이었다면, 해쉬는 거의 배운 적이 없다. 배우더라도 이런게 있다 식으로만 지나갔던 것 같다. 실제로 해쉬가 여기저기에 많이 쓰이는 것으로 알고 있어서 꽤 궁금했었다. 하지만 더 찾아보지는 않았었다. 딱 이 정도로만 해쉬를 알고 있었는데 오늘 특강에서 배운 내용들은 좀 신기했다.

 

그리고 몇 문제를 풀었는데, 아무리 해도 시간 초과가 해결되지 않았다. 알고보니 그 문제는 KMP 혹은 라빈 카프 알고리즘을 적용해서 푸는 문제였다. KMP 알고리즘을 배우기는 했지만 배운지가 너무 오래돼서 기억이 가물가물하고 배울 당시에 되게 어려웠던 기억이 있어서 선뜻 KMP로 풀고 싶지 않았다. 그래서 라빈 카프 알고리즘을 공부해서 문제에 적용했다. 나도 문자열의 해쉬 값을 구하고 해쉬 값이 같으면 실제로 문자열이 똑같은 지 비교하려고 했었기 때문에 알고리즘의 아이디어 자체는 내가 접근한 방법과 비슷했지만 나는 해쉬 값을 구하는 방법이 너무 시간이 오래 걸렸었다. 라빈 카프 알고리즘은 이전 해쉬 값을 이용해서 다음 해쉬 값을 O(1)에 구할 수 있기 때문에 시간을 많이 줄일 수 있었다.

 

문자열이 아니라 배열에 라빈 카프 알고리즘을 적용하는 문제도 있었는데, 2차원에 적용하려니 아주 어지러웠다. 해쉬 값을 구해서 문제 해결하는 것에 아직 익숙하지 않아서 그런 것 같다. 백준에서도 몇 문제 풀어봐야겠다.