[SWEA] 8. 해쉬

오늘 강의는 해쉬에 대한 내용이었다.

해쉬는 프로그래밍을 공부하기 시작하면서 처음부터 되게 많이 들어본 자료구조인데 실제로는 한 번도 써보지 않았다. 그냥 막연히 해쉬 버킷을 나누고 버킷에 원소를 넣어두는 형식으로 알고만 있었는데 실제로 해쉬 버킷을 나누고 관리하는 것이 중요한 부분이었다.

들어오는 원소를 특정 변환 함수로 변환을 해서 키값을 얻어내는데 이 키값으로 해쉬 버킷을 나누는 것이었다. 해쉬 버킷이 총원소의 수보다 적기 때문에 키값이 겹칠 수밖에 없는데 이때 해쉬 버킷의 원소는 최대한 균등하게 배분되어야 해쉬 버킷으로 나누는 의미가 있기 때문에 균등하게 나누는 것 역시 중요하였다.

 

연습 문제는 많이 풀지 못했는데 처음 사용하는 자료구조라 쉽게 풀 엄두를 내지 못하였다. 주말에 풀고 다시 올려야겠다.

No37. 문자열 교집합 (SWEA 2948)

강의에서 나온 해시로 키값을 구하는 함수를 활용하여 해시를 구해보려 했으나 너무 어려워서 한동안 안 풀다가 unordered map이 해시를 구현하기 좋은 방법이라고 하여 다시 문제를 보았다. unordered map은 collision이 일어나면 좋지 않은데 이 문제는 중복되는 문자열이 들어오지 않는다는 조건이 있어서 바로 key 값을 string으로 두고 문제를 풀었더니 풀렸다. collision을 어떻게 해결하는지는 따로 공부해보아야겠다.

 

No38. 단어가 등장하는 횟수 (SWEA 4038)

이 문제는 대표적인 KMP 알고리즘을 활용할 수 있는 문제이지만 해쉬를 사용하는 라빈카프 알고리즘을 사용할 수도 있다고 들었다. 근데 친구들이 이 문제에 대해 이야기하는 것을 들었을 때 이해가 가지 않아 해쉬 공부를 조금 더 하고 공부해보도록 하겠다.