자료알고 검색 결과

해당 글 130건
marking 배열과 sparse array

1달 2주 정도만에 자료구조 포스팅으로 돌아왔습니다. 와아아~. 생각난 김에, 안드로이드의 sparse Array에 대한 이야기를 해 보도록 하겠습니다. 당장 android의 스파스 어레이를 구글에 검색해 보시면 HashMap 하고 비교하는 글도 많아요. 거기서 빠질 수 없는 주제는 성능 비교일 텐데요. 퍼포먼스 이야기는 여기서 굳이 하지 않겠습니다. 이 포스팅을 보신 다음에, 추가적인 질문을 통해서 생각을 해 보도록 합시다. sparse는, 분포된 정도가 적은, 희박한이라는 뜻을 가집니다. 이것이 array의 수식어가 되면 어떨까요? 희소 배열. 즉, 전체에서, 정말 중요한 몇 % 정도만 저장하고 있는 구조 정도로 생각하시면 됩니다. 그런데, 사실 수식어가 걸리는 대상이 더 중요합니다. 여기서, 걸리는..
자료알고/자료구조 2020. 6. 19. 00:34
lis 알고리즘 : lower_bound 이용해서 그리디하게 해결해 봅시다.

lis 알고리즘은, 최장 증가 수열을 구하는 알고리즘입니다. 길이가 n인 수열이 있을 때, 이것을 O(nlogn)에 구할 수 있는 방법은 일종의 그리디를 이용한 것입니다. 물론, 조금 더 어려운 응용 문제를 풀기 위해서는 세그먼트 트리라는 자료구조를 알아야 하지만, 여기에서는 논외로 하도록 하겠습니다. 먼저 전체 소스 코드를 보겠습니다. res는 최장 증가 수열의 길이를 구하기 위한 벡터입니다. v는 문제에 주어진 수열입니다. 문제에 주어진 수열 전체를 돌면서, 먼저 lo 값을 구하고 있습니다. 이 lo 값은 res에서 v[i]보다 크거나 같은 최초의 위치를 찾습니다. 그 위치가 res의 크기와 같다면, res의 뒤에 추가합니다. 그렇지 않다면, res[lo]값에 v[i]를 갱신합니다. 일단 전체 시간 ..
자료알고/알고리즘 2020. 6. 17. 02:19
카카오 호텔 방 배정 : map 을 이용해서 깔끔하게 처리합시다.

카카오 호텔 방 배정 문제를 보겠습니다. 우리는 이 쿼리에 대한 답을 효율적으로 처리해야 합니다. 단, 방의 갯수는 10^12개 이하입니다. 10^12개에 대한 정보를 모두 담을 수는 없습니다. 어떻게 해야 할까요? 대신에 우리는 이런 아이디어를 하나 생각해 볼 수 있습니다. 그러면, 구간 정보를 어떻게 담아야 할까요? 방이 총 5개가 있다고 생각해 보겠습니다. 먼저, 초기 상태는 모든 방이 비어 있을 겁니다. 그러면, [1,5]가 비어 있었다는 정보를 넣습니다. 이제, 3보다 크거나 같은 비어 있는 방 중에서, 가장 작은 번호를 가지는 방을 빼 보겠습니다. 이를 K=3인 쿼리라 하겠습니다. 그러면 이 때 어떻게 나누어 질까요? 구간이 [1,2] [4,5]로 나누어 집니다. 이것을 어떻게 관리해 볼까요?..
자료알고/알고리즘 2020. 5. 9. 15:37
trie에서 공간을 줄이기 위해 포인터를 어떻게 쪼갤까요?

안녕하세요. 백준에서 chogahui05로 활동하고 있는 조경완입니다. 트라이에서 x진법으로 쪼갠다. 무슨 소리일까요? 사실 Trie가 어떤 것을 처리하기 위한 자료구조인지는, 카카오 문제에 출제되어서 익숙하신 분들이 많으실 거라고 생각합니다. 여기서 한 단계 더 깊이 들어가 보도록 하겠습니다. 공간을 줄이기 위해서는 어떻게 잘 쪼개야 할까요? 먼저 소문자로만 이루어진 문자열들을 Trie에 넣었을 때 상황을 생각해 보겠습니다. 문자열들의 길이 합은 10만을 넘지 않는다고 해 보겠습니다. 그리고 소문자만 나온다고 해 보겠습니다. 그러면, 다음과 같이 정적 Trie를 구축할 수 있을 겁니다. 여기서 26은 다음을 의미합니다. 'a'가 나왔을 때, 'b'가 나왔을 때, ... , 'z'가 나왔을 때 어디로 갈..
자료알고/자료구조 2020. 5. 5. 21:31
event driven : ps 문제에서 간단하게 활용해 봅시다.

이벤트를 넣어두고 그것을 활용한다. 작년에 스터디를 하면서 처음 들어본 말이였습니다. 사실, Java에서 mouse event listener와 같은 것이나 call back 패턴에서만 쓰이는 줄 알았기 때문입니다. 그런데, 특정 문제에서 이것을 잘 활용하면 생각보다 간단하게 풀 수 있습니다. Egg라는 문제를 보도록 하겠습니다. 이 문제를 간단하게 설명하면 아래와 같습니다. 생각보다 쉽지 않습니다. 그런데, 점들이 삭제되거나, 생성되는 이벤트가 주어지지 않으므로, 다음의 발상을 생각해 볼 수 있습니다. 사실, 이것만 계산을 하면, 문제에서 요구하는 쿼리도 해결할 수 있습니다. 이것을 어떻게 해결하면 좋을까요? 보라색 영역에 점이 있다고 해 보겠습니다. 우리는 x좌표가 A 이하이고, y 좌표가 B 이하인..
자료알고/알고리즘 2020. 5. 1. 17:58