자료구조 검색 결과

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

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

java의 arrayDeque가 어떻게 구현되었는지 간단히 알아보겠습니다. 세세하게 뜯지는 않을 거고, 중요한 변수들과 메서드만 보도록 하겠습니다. 먼저, 이 메서드를 보도록 하겠습니다. 코드를 봐도 뭔 말인지 모르겠습니다. 이럴 때는 쪼개시면 됩니다. 먼저, if문을 만족하지 않는다면, MIN_INITIAL_CAPACITY개의 원소를 저장할 수 있는 배열이 생성됩니다. 이 값은 디폴트로 8입니다. 만약에, numElements가 8보다 크거나 같으면 어떻게 될까요? 그러면 이런 알 수 없는 코드들이 수행되는데요. 어렵지 않아요. 132번째 부터 136번째 줄까지는 bit or 연산을 하고 있어요. 우항을 보면, >>> 연산자가 있는데요. 이는 쉽게 말해서 우측으로 이동한다 정도로 생각하심 됩니다. in..
레퍼런스/분석 2021. 3. 26. 01:25
펜윅 트리 (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
많이 언급되는 오프라인 쿼리 간단하게 훑어봅시다.

오프라인 쿼리. ps 하면서 한 번 쯤은 들어보셨을 법한 말입니다. 무엇을 오프라인으로 처리한다는 것일까요? 사실 잘 모르겠습니다. 대신에, 하나의 문제에 대해서 생각해 보면서 어떤 것이 오프라인 query 인지 대충 감만 잡도록 하겠습니다. 그냥 관점만 보셔도 됩니다. ps를 하는데 막 오프라인이 뭐냐고 묻진 않을 거니까요. 그거보다는 어떻게 효율적으로 해결할지 생각하시는 것이 더 중요하지 않을까 싶습니다. 배열이 이런 식으로 있습니다. 여기서 r1, r2, r3, r4, r5는 해당 위치로부터 얼마나 떨어진 거리까지 영향을 미치는지에 대한 것입니다. 마나커 알고리즘을 한 번 보셨다면, 이해가 가실 겁니다. 문제는, 이것이 기본적인 마나커에서 +3 ~ +4가 된 이유는, 이것을 처리하는 아이디어가 어렵..
자료알고/알고리즘 2021. 1. 4. 23:58
백준 11003 최소값 찾기 : 큐와 덱를 응용해 봅시다.

요새 코테 철이 되었습니다. 저도 간간히 구현력을 잃어버리지 않기 위해서 조금씩 복기만 하고 있습니다. 백준 11003번 문제는 최솟값을 구하는 문제입니다. 특정 구간 [e-k, e]에서의 최솟값을요. 단, 0보다 작은 위치의 구간은 무시하고 구해야 합니다. 별로 어렵지 않아 보이는데, 문제는 n이 500만입니다. 입력 받느라 시간이 많이 가는 건 흐음. O(n)으로 줄일 수 있습니다. 다들 아시는 기법을 소개하도록 하겠습니다. 관찰을 해야 할 것은 2가지 상황입니다. 어떠한 데이터가 추가되는 상황하고, 제거되는 상황. i번째에 있는 데이터가 제거되면, 더 이상 추가되지 않는다는 것을 관찰하는 것 또한 포인트입니다. 현재, 이런 식으로 데이터가 들어갔다고 해 보겠습니다. 그리고 저는 7번째 위치에 있는 ..
자료알고/알고리즘 2020. 9. 11. 02:37