Test of Week 4
이번 테스트는 hash table에 관한 문제들이었다.
이번 시험은 방심해서 처음으로 3번만에 완료할 수 있었다.
1번문제는 아주 기초적인 내용을 묻고 있다. 7-digit의 전화번호부에 대한 hash map을 만들기 위한 배열의 최소 크기를 묻는다.
2번은 Text 내 Pattern이 최대 L번 나타나는 것을 보장한다면 Rabin-Karp 알고리즘의 평균 운영시간은 어떻게 되는지 고르는 것이다.
3번은 배웠던 hash function과 다르게 역순으로 연산하는 기능일 때 H[i]와 H[i+1] 사이의 관계를 찾아내는 문제다.
7-digit의 전화번호부에 대한 hash map을 만들기 위한 배열의 최소 크기는 10^7이 된다.
2번같은 경우에 꽤 애를 먹었고 결국 틀렸지만 강의 끝자락에서 보았던 bad example에 관한 내용이었음을 유추할 수 있었다.
강의에서 보았던 hash function에 대해 H[i]와 H[i+1]의 관계식을 거꾸로 적용하면 쉽게 찾을 수 있다.
이번 테스트는 hash table에 관한 문제들이었다.
이번 시험은 방심해서 처음으로 3번만에 완료할 수 있었다.
1번문제는 아주 기초적인 내용을 묻고 있다. 7-digit의 전화번호부에 대한 hash map을 만들기 위한 배열의 최소 크기를 묻는다.
2번은 Text 내 Pattern이 최대 L번 나타나는 것을 보장한다면 Rabin-Karp 알고리즘의 평균 운영시간은 어떻게 되는지 고르는 것이다.
3번은 배웠던 hash function과 다르게 역순으로 연산하는 기능일 때 H[i]와 H[i+1] 사이의 관계를 찾아내는 문제다.
7-digit의 전화번호부에 대한 hash map을 만들기 위한 배열의 최소 크기는 10^7이 된다.
2번같은 경우에 꽤 애를 먹었고 결국 틀렸지만 강의 끝자락에서 보았던 bad example에 관한 내용이었음을 유추할 수 있었다.
강의에서 보았던 hash function에 대해 H[i]와 H[i+1]의 관계식을 거꾸로 적용하면 쉽게 찾을 수 있다.
댓글
댓글 쓰기