자료구조 검색 결과

해당 글 38건
java map find key in value : 2개의 맵을 씁시다.

java에서 hash나 tree 계열 (흔히 rb로 구현된) map은 key 값이 주어졌을 때, value를 빠르게 찾는 자료구조입니다. 예를 들어, hash 계열의 map은 key 값을 가지고 계산된 hash 값을 가지고, 특정한 버킷에서 값을 찾아버립니다. Treemap이나 set은 정렬이 되어 있습니다. key값의 대소에 따라 정렬이 되어 있다면, 적절한 연산을 통해 O(log(size))의 복잡도로 찾기 연산을 수행할 수 있습니다. 문제는, 이런 경우입니다. 값을 기준으로 키도 빠르게 찾아내려면 어떻게 해야 할까요? TreeMap이나 HashMap이 Key값을 토대로 Value를 빠르게 찾아낸다고 했습니다. 반대로 생각하면 어떨까요? Value 값을 토대로 대응되는 키 값을 빠르게 찾아내려면, 키..
자료구조 2021. 1. 28. 01:27
스택계산기 구현 : 연산자 우선순위와 결합 순서만 생각해 봅시다.

안녕하세요. 오늘은 간단하게 스택 계산기 프로그램을 만드려고 합니다. 일단 괄호가 없는 유효한 식은 숫자 (연산자 숫자)* 이런 패턴으로 들어올 겁니다. 예를 들어 3도 유효한 계산 식입니다. 그리고, 3*7-2도 유효한 식입니다. 연산자는 *과 +, -만 들어온다고 가정해 보겠습니다. 먼저 우선순위부터 set 하도록 하겠습니다. *는 +, -보다 우선순위가 높으니, *의 priority를 0으로, +과 -를 1로 설정하였습니다. 11번째 줄이 그러한 일을 수행합니다. 그리고, ArrayList인 num과 op는, 수식으로부터 들어온 수와 연산자를 순서대로 넣어놓았습니다. 예를 들어서 2-3+7이 들어왔다면, num에는 2, 3, 7 순서대로 들어가고, op에는 -와 +이 순서대로 들어가 있습니다. 이제..
자료구조 2020. 7. 2. 02:21
java에서 STL의 multimap 구조를 구현해 봅시다.

C++의 STL에서 multimap은 상당히 유용하게 쓰입니다. Java에서는 그렇게 쓸 수 없을까요? 저는 Key값이 중복되는 경우에도, Map 계열에 저장하고 싶습니다. 어떻게 하면 좋을까요? 그 전에 Java의 Map 계열이 어떻게 동작하는지 간단하게 정리하고 가겠습니다. map.find(K)를 호출했을 때 개략적인 흐름을 보겠습니다. 먼저, map 계열이 키가 K인 값을 찾는 구조입니다. 그러면, 자료구조에서 Key가 K인 것을 찾는데, 이 작업을 하기 위해 내부적으로 호출되는 메서드가 equals입니다. put(K,V')가 호출되었을 때, Key가 K인 것이 존재했다면, 데이터 를 가 같이 저장될 수 없습니다. 예를 들어, K가 가수이고, V가 발매한 앨범이라고 해 보겠습니다. Key dupli..
자료구조 2020. 6. 24. 02:12
marking 배열과 sparse array

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

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