자료구조 검색 결과

해당 글 34건
비트 배열 : 공간을 1/8, 1/32, 1/64로 압축한다.

제목이 꽤 도발적인 거 같네요. ps를 하시다 보면 종종 듣는 이야기 중 하나는, 상수 최적화, 혹은 O(n/32)나 O(n/64)입니다. 그것이 공간이 될 수도 있고, 시간이 될 수도 있는데요. 32와 64. 무언가와 연관이 있는 듯 싶습니다. 환경에 따라 다르겠지만, 보통 우리가 흔히 알고 있는 int형, long long형의 bit 수이기도 합니다. 공간을 n/32나, n/64로 compress 하는 문제를 생각해 봅시다. 사실, trie나 set, map을 쓰셔도 됩니다. 그런데 STL을 직접 구현해야 하는 경우, 2번째 것과 3번째 것은 구현하는 데, 상당히 어렵습니다. 1번은 시도해 볼 만 합니다. 그런데 메모리 제한이 128M로 꽤 넉넉하다면 어떨까요? 이 때는 이야기가 달라질 수도 있습니다..
자료알고/자료구조 2019. 12. 24. 05:39
스파스 테이블 (sparse table) : 2의 거듭제곱 단위로 점프한다.

이런 문제를 생각해 보겠습니다. 뭔가 많이 본 거 같은데, 효율적으로 풀기는 쉽지 않아 보입니다. 왜냐하면 naive하게 구하면, 최악의 경우에, dQ만큼이나 수행해야 하기 때문입니다. 이걸 어떻게 하면 좋을지 먼저 생각해 봅시다. 일단, 자연수 k의 2진수 표현은 유일합니다. 이것부터 보여 봅시다. 귀류법을 써 보겠습니다. 간단하게 상위 비트부터 쭉 저장이 되어 있다고 가정해 봅시다. 만약에 k의 2진수 표현이 2가지 이상이라고 한다면, 분명하게도, 비트가 다른 부분이 존재할 겁니다. 그러면 이 둘의 차이의 절댓값은 2^x보다는 크거나 같을 겁니다. 이제 보라색 부분을 봅시다. 가정이 성립하려면, 보라색 부분을 어떻게 잘 채워서, 2^x만큼 상쇄해야 할 건데요. 상쇄를 하려면, 보라색 부분의 차이의 절..
자료알고/자료구조 2019. 12. 20. 10:11
java hashset은 key의 해쉬 코드가 모두 같을 때 최악 복잡도가 어떻게 될까요?

저번에, 왜 equals를 구현하면 왜 hashCode를 같이 구현해야 하는지에 대해서 설명을 했습니다. hash 계열의 자료구조 때문에 그렇다고 했었습니다. 그렇지 않으면 어떻게 동작하는지는 여기를 참고하시면 좋겠습니다. 이 내용에 대해서 숙지하셨다고 가정하고 진행하도록 하겠습니다. 면접 질문에서 간혹 가다가 등장하는지는 잘 모르겠습니다만, 어떠한 객체의 hashCode 값이 같은 것들을 모두 hashSet에 넣을 때, 어떤 일이 벌어지는지는 꽤 중요한 문제 중 하나일 겁니다. 사실, 우리는 그렇게 바보같이 구현할 일이 없습니다. 그렇지만, 저는 이에 대해서 포스팅 하도록 하겠습니다. 먼저 Java 8에서부터, hashMap은 버킷에 8개 이상 달려있을 때, Balanced Tree로 변환이 된다는 것..
레퍼런스/분석 2019. 12. 18. 22:35
우선순위 큐 : 부모가 자식들보다 rank가 높다.

우선순위 큐는, 삽입과 삭제가 일어날 때, 가장 우선순위가 높은 것을 빠르게 찾을 수 있는 구조입니다. 일단, 이것의 특징 먼저 간단하게 잡고 넘어가 봅시다. 먼저, 부모들은 자식들보다 rank가 높습니다. 예를 들어서, A의 자식이 B, C라고 해 봅시다. 그러면, A >= B이고 A >= C입니다. 그러면 A의 모든 child들 (자식의 자식이라던지)은 무조건 A보다 rank가 같거나 낮을까요? 위 그림을 봅시다. B(1)의 직계 child는 B(2), B(2)의 child는 B(3), ... 이런 식으로 가고 있어요. 그러면 A >= B(1) >= ... >= B(n)이 성립합니다. 연쇄입니다. 따라서, A >= B(n)입니다. 부모에서 자식으로만 연결된 간선이 있고, x가 A로부터 도달 가능할 때..
자료알고/자료구조 2019. 12. 16. 21:56
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