자료알고 검색 결과

해당 글 130건
평방 분할 (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
팬 케이크 정렬 : 위에서부터 k개를 뒤집는다.

팬케이크 정렬은 유튜브에서 영상으로 한 번 쯤은 보셨을 겁니다. 이것을 최소한으로 뒤집는 횟수를 구하는 것은 경시 대회 이상에서 나올 만한 문제입니다. 우리는 단지, 어떻게 잘 뒤집어서 정렬을 잘 시키면 됩니다. 팬 케이크 더미에서는 위에서 k개만 뒤집을 수 있습니다. 단, k는 총 갯수보다 작을 거에요. 갯수를 n개라고 한다면 2n-3번 이하 뒤집어야 합니다. 이 때에는 어떻게 해야 할까요? 사실, 잘 모르겠습니다. 일단, 1회전이 끝날 때 마다, 2회의 단위 연산을 수행해야 한다는 것은 알겠습니다. 그러면 한 회전마다 어떤 일이 일어나면 좋을까요? 팬 케이크가 이런 식으로 쌓여 있다고 생각해 봅시다. '위에서 k개를 뒤집는다'는 연산 특성상, k가 n이 아니라면, 맨 아랫쪽에 있는 것은 움직이지 않습..
자료알고/알고리즘 2019. 9. 17. 13:29
재해싱 (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
라빈 카프 알고리즘 : 그래도 비벼볼 만한 문제가 있다.

오늘은 라빈 카프 알고리즘을 배워 보겠습니다. 어떠한 문자열을 수 하나, 혹은 2개, 3개로 압축할 수 있다. 이것은 꽤 엄청납니다. 그렇게 하면, 사실 어떠한 문자열에서 다른 패턴을 찾는 거 또한, 상당히 빠르게 수행할 수 있습니다. 다만, 정확성이 문제라면 문제인데요. 이 부분은 모듈러를 2개, 3개 이상 주는 식으로 해결합니다. 즉, 데이터가 강하지 않을 거라는 믿음을 가지고 수행을 하는 편입니다. 이 알고리즘을 잘 배워놓으면, 문자열 알고리즘을 모를 때, 조금이라도 건드려 볼 수 있습니다. 그러니 알아두시면 나름 좋습니다. 이 포스팅은 부분합 알고리즘을 이해했다는 전제 하에 쓰여졌습니다. 만약에, 그 부분에 대해서 이해를 하지 못하셨다면, 아래 포스팅을 먼저 보시고 오시는 것을 강력하게 권해드립니..
자료알고/알고리즘 2019. 9. 6. 17:16