Minwook’s portfolio

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/courses/30/lessons/120956 저작권 관련 더보기 비상업적, 비영리적 용도로 사용합니다. 광고가 노출되지 않는 블로그나 YouTube 채널, GitHub 등에 문제 풀이 게시 코딩테스트 연습에 공개된 문제는 (주)그렙이 저작권을 가지고 있습니다. (지문 하단에 별도 저작권 표시 문제 제외) 코딩테스트 연습 문제의 지문, 테스트케이스, 풀이 등과 같은 정보는 비상업적, 비영리적 용도로 게시할 수 있습니다. ※ 2020 KAKAO BLIND RECRUITMENT, Summer/Winter Coding 등의 문제는 기업 코딩 테스트에 나온 문제이나, 코딩테스트 연습에 공개된 문제이기 때..

Hashtable이란? key와 value를 받아 hashing하여 나온 index에 값을 저장하는 선형자료구조, 삽입시 시간복잡도는 O(1), key를 알고 있다면 탐색과 삭제도 O(1)로 빠른속도로 수행가능. 해쉬충돌이란? 서로 다른 input Data 가 같은 hash 함수를 통해 hashing후 결과값이 같을때 해쉬충돌이 일어날 경우, 같은 버킷에 저장되게 되므로 원하지 않는 결과를 불러올 수 있다. 해쉬충돌을 해결하는 4가지 방법 1.선형탐사법 충돌이 발생하면 기존 버킷에서 옆으로 한칸 이동하여 Data를 저장한다. 단순하지만 충돌이 여러번 일어날 결우 특정영역에 데이터가 모일 수 있는 단점이 있다. 또한 충돌이 발생하지 않을 때까지 이동해야 하므로 최악의 경우에는 탐색에 선형시간 O(n)이 소..