자료알고/자료구조 검색 결과

해당 글 43건
java treemap compareto나 compare만 구현했을 때 제대로 동작할까요?

자바에는 TreeMap이 있습니다. 키 오브젝트가 Obj의 인스턴스라고 해 봅시다. Obj 클래스에서 equals를 override 하지 않고 compareTo를 비교하거나, Obj를 비교하는 방법인 comparator만 생성자로 넘기면 어떻게 될까요? 그래도 잘 동작할까요? 우리가 걱정하는 부분은 equals입니다. equals는 두 객체의 동등성을 비교합니다. 이 메서드가 어디에서 쓰이는지 TreeMap 내부에서 한 번 찾아보도록 합시다. putAll에 등장합니다. Objects.equals이네요. comparator를 넘기는 것으로 보아서는, 비교하는 객체를 넘기는 것으로 보입니다. 따라서, 키 값과는 아무런 연관이 없습니다. 다음 replace 입니다. 이 부분도 잘 보면, value에 대해서만 ..
자료알고/자료구조 2023. 5. 11. 00:14
java linkedhashmap removeeldestentry 메소드에 대해 알아봅시다.

가희배 5회 코딩테스트가 4월 2일에 열렸습니다. 제가 플레 이상으로 예측한 문제도 있었지만, 골드 정도로 예측했는데 실제로 까 보니 플레였던 문제가 있었습니다. 그 문제에 이어서 또 당한 셈인데요. 이 문제가 어려웠던 이유는 2가지가 있습니다. 카카오 기출 문제를 3개나 섞었다. 그리고, 이 문제에 jpop 이랑 kpop이 상당히 많이 들어가면서 지문 자체가 어마어마하게 길었다. 이 2가지가 있겠습니다. 이것은 가희와 코드도 마찬가지입니다. 후자는 사전 지식이 없으면 해석하는 데 시간이 구현시간보다 더 걸렸을거고 전자는 구현량이 생각보다 있었습니다. 문제에서 요구하는 것은 2가지입니다. lru, 가장 가까운 cache 찾기, 엄청나게 긴 지문과 이상하게 jpop과 kpop이 들어간 예제 해석. 이 중 ..
자료알고/자료구조 2023. 4. 4. 02:16
java stack 클래스와 대체해서 쓸 만한 arraydeque를 간단히 알아봅시다.

java에는 stack 클래스가 있습니다. 스택은 마지막에 들어온 원소가 먼저 빠져나가는 것으로 유명한 자료구조입니다. 계산기 같은 것을 구현할 때 많이 쓰이기도 합니다. 백준 문제를 풀다 보면 간혹 가다 쓰일 때가 있습니다. 간단한 예제를 하나 보겠습니다. 위 예제는 0부터 4까지의 수를 넣은 다음에, 맨 위에 있는 원소를 peek으로 가져오기만 합니다. 다음에, pop으로 맨 위에 있는 원소를 가져오면서 제거합니다. peek 메서드의 설명을 보면, 보다 명확합니다. 스택에서 원소를 제거하지 않고 stack의 맨 위에 있는 원소를 가져온다. 반면에 pop은 제거까지 합니다. 비어있는지 검사하기 위해서 empty를 호출했습니다. 다음에, 원소를 넣기 위해 push를 썼습니다. 나중에 넣은 4가 먼저 빠지..
자료알고/자료구조 2023. 2. 28. 23:55
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