목록hash (2)
Joonas' Note
문자열을 정수로?이 글에서 다루는 내용은, 문자열의 형태로 적혀있는 "112223"과 같은 문자열을 말하는 것이 아닙니다. 영어 소문자로만 이루어진 "aaabbb" 또는 대문자로만 이루어진 "ABCCDD" 같은 문자열을 정수형 변수 하나에 담는 것을 말합니다.왜?보통 해싱은 작은 크기로 우겨넣기 때문에 데이터 손실이 일어나는 형태가 많습니다. 그래서 그대로 저장하면 충돌 해결 이슈가 따라오죠. (resolving collisions in hash tables) 정수로 바꾸어서 다룬다면 문자열 비교를 길이만큼인 \(O(|s|)\) 가 아닌 정수 비교 시간인 \(O(1)\) 으로 줄일 수 있습니다. 조건만 가능하다면 데이터의 손실 없이 그대로 담을 수도 있죠.26진법소문자 26개 혹은 대문자 26개만 사용하..
링크: https://programmers.co.kr/learn/courses/18/lessons/1878문제코딩 테스트의 데모 문제, 연습 문제로 많이 등장하는 문제입니다.직사각형을 나타내는 네 개의 꼭짓점 중 세 개의 좌표가 주어졌을 때, 나머지 한 좌표를 구하는 문제죠.좌표의 범위에 따라 해결 방식이 다를 수 있습니다. 여기서는 좌표의 범위가 10억까지인 프로그래머스 문제의 풀이를 다룹니다. (백준에서는 1000 이하의 정수)네 점의 x좌표들은 모두 2번씩 등장합니다. 마찬가지로 y좌표들도 2번씩 등장해야하죠. 그럼 x, y 좌표들 중 1번만 등장한 녀석들이 문제의 정답입니다.이것을 카운팅하는 것이 곧 문제를 해결하는 것인데, 좌표가 10억까지 주어지는 경우라면 해시(Hash)와 같은 적당한 자료구..