자료구조 검색 결과

해당 글 40건
heap 자료구조에 build를 어떻게 linear time에 끝낼까요?

오랫만에 자료구조 시간으로 돌아왔습니다. heap 자료구조는 다들 익숙하실 겁니다. 그리고 힙을 build 하는 연산을 힙 사이즈가 n이라면 O(n)에 할 수 있다는 이야기는 예전부터 들어왔어요. 그런데 어떤 원리로 그것을 할 수 있을까요? 자바에도 PriorityQueue가 있으니, 이 클래스의 내부 소스를 까보면서 이야기 해 보도록 하겠습니다. 문제 상황은 임의의 순서로 배열되어 있는 array를 heap 조건에 맞추어서 build 하는 것입니다. 그에 맞게 코드를 짜 보았습니다. PriorityQueue에 list를 넘겨주었는데요. Collection을 받았기 때문에, 아래 메서드가 호출될 겁니다. 아래에 나와있는 코드를 보겠습니다. 여기서 보면 List는 SortedSet도 아니고, Priorit..
자료구조 2021. 10. 13. 14:50
펜윅 트리 (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
반응형