Life and IT

먼저 해시 함수가 가져야 할 특징 3가지가 있다. 충돌이 적어야 한다. 해시 테이블에 고르게 분포시킬 수 있는 주소의 연산 값이 나와야 한다. 이는 곧 1번을 충족할 수 있다. 계산이 빨라야 한다. 위 3가지를 고루 갖추지 못한다면 100개의 버킷 중에 하나의 버킷만 나와서 오버플로우가 발생하는 참사가 일어날 수 있다. 위의 특징을 고루 갖춘 함수 중 하나로 제산 함수라는 것이 있다. 제산 함수 레코드(키) 값을 소수로 나누어 나머지 값을 주소로 지정하는 해시 함수. ex) h(k) = k % 7 만약 위 특징을 갖춘 해시 함수를 만들었는데도 오버플로우가 발생한다면? 내가 아는 선에서 두 가지의 방법이 있다. 선형 탐사법 (Linear Probing) 분리 연결법 (Separate Chaining) 1...

해시 다양한 길이를 가진 데이터를 고정된 길이를 가진 데이터로 매핑한 값 *매핑 : 하나의 값을 다른 값으로 대응시키는 것 탐색 하나 이상의 필드로 구성된 레코드의 집합에서 원하는 레코드를 찾는 것 *탐색을 위하여 사용되는 자료 구조 : 배열, 연결 리스트, 트리, 그래프 또한 레코드들의 집합을 테이블(Table)이라고 부른다. 테이블에서 레코드들을 어떻게 구분할까? 레코드마다 서로 구별되는 키를 가지고 있는데 이것을 탐색키라고 부른다. 의미 있는 단위를 이끌어 내기 위해서 하나의 필드를 가진 레코드만으로는 부족하다. 따라서 맵이라는 개념을 끌어온다. 맵 탐색키 그리고 탐색키와 관련된 값의 쌍을 말한다. 즉, 두 가지 필드를 가진 키를 가진 레코드 또는 엔트리로 이루어진다. 이 두 가지 값은 key, v..

https://programmers.co.kr/learn/courses/30/lessons/42576 코딩테스트 연습 - 완주하지 못한 선수 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수 programmers.co.kr 문제 설명 수많은 마라톤 선수들이 마라톤에 참여하였습니다. 단 한 명의 선수를 제외하고는 모든 선수가 마라톤을 완주하였습니다. 마라톤에 참여한 선수들의 이름이 담긴 배열 participant와 완주한 선수들의 이름이 담긴 배열 completion이 주어질 때, 완주하지 못한 선수의 이름을 return 하도록 solution 함수를 작성해주세요..