K번째수 검색 결과

해당 글 2건
k번째 숫자 구하기 : 트라이(Trie) 구조를 이용해 봅시다.

수 x가 추가되고 제거됩니다. k번째로 작은 수를 구해야 하는 쿼리가 있습니다. 아니면, 수 x가 있는지 찾아야 합니다. 어떻게 해야 할까요? 물론, offline이 가능하면 정렬하고 좌표 압축한 다음에 세그먼트 트리를 돌릴 수 있어요. 하지만, online으로 해결해야 하는 경우, 정렬 후 좌표압축 스킬이 통하지 않습니다. 이 때, 우리는 수 x를 32bit 범위 내라면 32, 64bit 범위 내라면 길이 64의 2진수 문자열로 변환할 수 있습니다. 이 때, 우리는 Trie라는 자료구조를 생각할 수 있습니다. 이 Trie는 올해 카카오 4번에 나왔던 structure 이기도 합니다. Skip List는 상대적으로 구현하기 까다로우니, 논외로 합시다. 예를 들어서, 13을 넣는다고 생각해 봅시다. 그러면..
자료알고/자료구조 2019. 12. 5. 20:12
k번째 수 찾기 : count sort를 응용해 봅시다.

백준 11004번, k번째 수를 구하는 문제가 있습니다. 오름 차순으로 정렬하였을 때, k번째 수가 무엇인지를 묻는 문제입니다. 그런데 배열의 크기가 500만입니다. 그렇기 때문에 fast io를 쓴 다음에 sort를 쓰거나, 아니면 다른 방법을 써야 하는데요. 저번에 배운 count sort를 조금 응용해 보도록 하겠습니다. [관련 글] count sort에 대해 알아봅시다. 이게 k번째 수와 어떠한 관련이 있을까요? [0, 20억] 사이에 있는 수는 다음과 같이 표현할 수 있습니다. 65536a + b (단 a, b는 0보다 크거나 같고 65536보다 작은 자연수) 즉, 65536 진법으로 표현할 수 있습니다. 그러면 몫을 구할 때 (x>>16)을, 나머지를 구할 때에는 (x&65535)로 구할 수 ..
자료알고/알고리즘 2019. 8. 17. 18:27