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

해당 글 43건
평방 분할 (Sqrt Decompositon) : 루트로 쪼개보자.

세그먼트 트리를 모를 때, k번째로 빠른 수를 어떻게 찾아야 할 지 모를 때, 어떤 방법을 쓰면 좋을까요? n이 적당히 크다면, 우리는 이런 아이디어를 생각해 볼 수 있습니다. 구간이 n개가 아닌 sqrt(n)개. 그리고, 구간 별 원소 갯수도 sqrt(n)개. 사실, 이것을 응용한 알고리즘이 Mo's algorithm인데, 여기까지 다루지는 않겠습니다. 예를 들어, 배열의 임의의 원소가 구간 [1,9]에 속하는 자연수라고 해 봅시다. 이 때 배열 [1, 3, 3, 4, 4, 5, 5, 6, 7, 7, 7, 8, 8, 9]에서, 13번째로 작은 수를 찾기 위해서 어떻게 하면 좋을까요? 일단, co[x]는 x가 나타나는 빈도수를 나타낸 겁니다. 그러면 단순하게 생각하면, 누적 값을 더해가면서, 1이 출현하..
자료알고/자료구조 2019. 9. 22. 00:18
재해싱 (rehashing) : 시간 복잡도를 분석해 보면서 왜 필요한지 알아봅시다.

Hash에서, 면접에서 물어볼 만한 키워드들을 천천히 알아보도록 하겠습니다. 이 중 오늘은 재해싱에 대한 이야기를 간단하게 하고 넘어가겠습니다. Hash Table은, 저번시간에 배운 바로는, 버킷에다가, 데이터를 주렁 주렁 매달아 놓는 식으로 많이 처리를 한다고 했었습니다. 보통, Chaining을 사용하는 경우, List를 사용한다고 했었습니다. 저는 간단하게 구현하기 위해서, 2차원 배열로 구현을 했었고요. 그런데, 생각을 해 봅시다. 수가 2개만 들어왔어요. 그런데, 1000만개의 바구니를 미리 만들어 놓을 필요가 있을까요? 2개를 위해서, 1000만개의 바구니를 생성한다. 이것만큼 낭비가 없습니다. 그러면, 어떻게 할 거냐. 초기 사이즈를 매우 작게 잡습니다. 예를 들자면, 2개의 초기 buck..
자료알고/자료구조 2019. 9. 13. 00:59
자료구조 해시 테이블 : 직접 구현해 봅시다.

저번에 비둘기 집의 원리에 대해서 잠깐 언급을 했었습니다. 거기서, hash에 대해서 잠깐 언급을 했었는데요. 오늘은 이 hash를 STL 없이 직접 구현을 해 봅시다. 다음 시간에 String의 hashCode를 직접 구현해 보고, 백준의 듣보잡 문제를 풀어 봅시다. 사실 Hash는 크게 보면 딱 1가지만 주목하면 됩니다. 가 있을 때, 우리는 Key에 대응이 되는 bucket 값을 b(key)라 할 거에요. 예를 들자면, Key 값이 10101010입니다. b(10101010)의 값이 10이라면, 우리는 10번 버킷에 Value를 넣는 것입니다. Key가 정수인 경우, 함수 b는 Key 값에다가 버킷 갯수를 나눈 모듈러를 취하는데요. 예를 들어서, Key의 값이 2058370이고, 버킷 수가 100만..
자료알고/자료구조 2019. 9. 11. 01:30
자료구조 덱 (deque) : 앞과 뒤에서 추가되고 삭제된다.

자료구조의 덱, 그러니까 deque는 queue하고 비슷합니다. front와 back, 이렇게 2개의 포인터 있습니다. 그런데, 큐가 front에서 삭제가 일어나고, back에서 삽입 연산이 일어나는데 비해서, 덱은 front에서도 삽입과 삭제가, back에서도 삽입과 삭제가 일어납니다. 이 연산만 구현하려면, 사실 List로 구현하는 게 제일 간단해 보입니다. 먼저 다음과 같이 초기화를 시켜 봅시다. 그러면 이 때가 비어있는 상태일 겁니다. head->next가 tail이고, tail->prev가 head일 때, empty 상태라고 판단할 수 있습니다. 저는 이 두 개의 더미를 인위적으로 잇기만 하였습니다. 여기에서 push_front 연산을 수행해 봅시다. 이것은 맨 앞에 원소를 추가하는 것입니다. ..
자료알고/자료구조 2019. 8. 22. 01:05
비둘기집의 원리 : 왜 해시충돌을 피할 수 없는가?

해시를 하기 전에, 비둘기집의 원리를 간단하게 짚고 넘어가겠습니다. 집이 k개가 있고 비둘기가 k+1마리가 있습니다. 그리고 비둘기들은 상자들 중 하나에 들어갔을 때, 이들이 2마리 이상 들어가는 집이 최소한 하나 존재합니다. 집 k개를 그려보았습니다. 그리고 밑에는 비둘기 k+1마리가 있어요. 그러면, 결론을 부정해 봅시다. '2마리 이상 들어가는 집이 최소한 하나 존재한다'는 명제의 부정은, 2마리 이상 들어가는 집이 존재하지 않는다입니다. 그러면 k+1마리가 있고, 집이 k개 있을 때, 많아봤자 1마리가 들어간다가 참이라고 해 봅시다. 즉 ~p가 참이다라고 한 겁니다. 그러면 각 상자에는 최대 1마리씩만 들어갈 수 있으니까, k개의 상자에는 최대 k마리가 들어갈 수 있습니다. 그러면 나머지 1마리는..
자료알고/자료구조 2019. 8. 17. 23:09