자료구조 검색 결과

해당 글 39건
펜윅 트리 (fenwick tree) : 구간합을 빠르게 구한다.

펜윅 트리는 구간합을 구할 때 상수를 줄이기 위해 이용할 수 있는 구조입니다. 유성 문제는 세그먼트 트리 대신에 펜윅을 써야 풀리는 문제로 유명한데요. 시간 복잡도의 특성상 상수를 줄여야 하는데, 레이지를 이용한 세그 트리는 느리기 때문입니다. 이게 어떤 식으로 동작하는지 보고, 간단하게 코드를 작성해 보도록 하겠습니다. 펜윅 트리는 다음과 같이 그릴 수 있습니다. 이들은 각각 [1], [3], [5], [7]을 담고 있는 노드입니다. 규칙을 찾아보면, 1, 3, 5, 7은 1의 배수이지만 2의 배수는 아닙니다. 다음에 1, 3, 5, 7과 비교했을 때 구간의 크기가 2배인 2와 6이 있습니다. 이들의 구간 크기는 2이고요. 각각 구간 [1, 2], [5, 6]을 담고 있습니다. 이 둘의 공통점은 2의 ..
자료구조 2021. 3. 14. 00:37
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