자료알고/자료구조 검색 결과

해당 글 43건
균형 이진 트리 : 제약 조건이 맞지 않으면 추가적인 연산을 한다.

ps를 하시면, 많이 보는 자료구조 중 하나는, Java에서 TreeSet, TreeMap, C++의 STL에서는 Map, Set 등이 있습니다. 균형 트리로 구현이 되어 있다는 이야기는 많이 합니다. 이게 무엇일까? 에 대해서만 간단하게 생각해 보도록 하겠습니다. 필기 시험에 나올 때 상당히 매력적인 보기를 주는 경우도 있으니, 간단하게 개념을 짚고 넘어가시는 것도 좋겠습니다. 이진 트리를 생각해 봅시다. 이것은 기준 노드를 기준으로 그것보다 작으면 왼쪽에, 크면 우측에 옵니다. 그러면 1을 찾기 위해서는 몇 번의 탐색이 필요할까요? 3보다 작으므로 왼쪽으로 갑니다. 2보다도 작으므로 왼쪽으로 갑니다. 그랬더니 1이 있습니다. 3번 탐색하면 됩니다. 그러면 이 트리에서 -5를 찾기 위해서는 어떻게 해야..
자료알고/자료구조 2020. 1. 11. 03:28
비트 배열 : 공간을 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
우선순위 큐 : 부모가 자식들보다 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