시간복잡도 검색 결과

해당 글 6건
python dictionary는 최악의 경우에 정말로 시간 복잡도가 선형일까요?

python에서 dictionary가 어떻게 구현되었을까요? 아니 그 전에 최악의 경우에 뭔가를 찾는 연산은 O(n)일까요? insert 하는 연산도? 사실, 저는 자바에서 본 것 처럼 그냥 chaining 으로 관리하지 않을까 싶었는데 그건 아니였습니다. 니다. 제 무지함이 또. 그 전에, 정말 최악의 경우에 insert나 find 연산 등이 비효율적으로 동작할까? 에 대한 의문부터 해결해 봅시다. 최악의 경우를 인위적으로 만드는 방법은 그리 어렵지 않습니다. 어디까지나 인위적으로 조작할 뿐, 실제로 제가 출제한 문제에서 최악 케이스를 만드는 건 쉽지 않습니다. 왜냐하면, python에서 int object가 모든 hashcode 값이 0일 리는 없기 때문입니다. 이에 대한 건 나중에 언급하도록 하겠습..
레퍼런스/분석 2021. 11. 6. 20:57
heap 자료구조에 build를 어떻게 linear time에 끝낼까요?

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

어느덧 500번째 글입니다. 그냥 정보글은 시시하니, 대회 검수 썰을 풀어보도록 하겠습니다. SUAPC를 검수하면서 신경을 썼던 것 중 하나는, 대회에 출제된 20940번 문제였습니다. 대회에 출제된 문제 중에 난이도가 높은 그룹에 속할 것이라고 예상했고, 실제로 그렇게 되었습니다. 이 문제를 검수할 때 세웠던 원칙 중 하나는 브루트 포스로 검증을 해 볼만한 사이즈가 되면, 검증을 해 보자는 것이였습니다. 100만이면 모르겠지만, 50만이면 해 볼 만 했습니다. 잘 돌리면 1시간 정도에 해결을 할 수 있었기 때문입니다. 이 문제의 초기 조건은 N은 [1, 50만], K는 10^9+7이였습니다. 브루트 포스로 돌릴 만 합니다. 그런데, 이걸 그냥 브루트 포스로 돌리기에는? N이 대충 50만. 50만의 제곱..
자료알고/알고리즘 2021. 5. 21. 04:02
알고리즘 시간 복잡도 대강 분석하는 방법을 예제를 통해 알아봅시다.

시간 복잡도를 어떻게 대강 분석할까요? 실행 시간을 보고, 추정을 하시면 됩니다. 정말 괴랄한 복잡도가 아니라면, O(n), O(n^2), ... 등은 어느 정도 맞아 떨어집니다. 저는 java에서 메서드를 실행하는 데 걸린 시간을 측정할 때, System.nanoTime()을 이용하는 편입니다. 이것은 정밀한 시간 측정을 해 주지는 못합니다만, 어느 부분에서 시간 초과가 날 수 있는지 후보해를 추릴 수 있습니다. 질문이 하나 들어왔습니다. M자리 수와 N자리 수를 BigInteger로 곱하였습니다. M, N은 30만 자리 정도 되었다고 합니다. 10진수로 M자리 수라면, 32bit 2진수가 10진수 9자리와 대응이 됩니다. 그래서, bit 연산을 잘 이용하면 M과 N이 최대 30만자리까지 나오니까, (..
자료알고/알고리즘 2021. 4. 3. 02:24
java ArrayList remove 메소드에 대해 알아봅시다.

이번 시간에는 ArrayList의 remove에 대해 알아보겠습니다. remove를 보시면, int형을 받는 것이 있고, Object를 받는 것이 있습니다. int를 wrapping한 것은 Integer입니다. auto boxing까지 생각한다면 이 둘이 헷갈릴 소지가 매우 다분합니다. 특히 Integer는 스택 오버플로우에도 꽤 많이 올라왔던 질문 중 하나였습니다. 이 기회에 정리를 해 두시는 것도 괜찮겠습니다. 먼저 Object를 받는 remove를 알아보겠습니다. 먼저, Obj를 하나 생성하였습니다. 여기에는 equals가 재정의 되어 있지 않습니다. 저는 여기에서, "gahui"가 들어간 오브젝트를 새로 생성하였습니다. 그리고, 새롭게 생성한 "gahui" 라는 오브젝트를 li에서 제거할 건데요...
레퍼런스/분석 2020. 8. 25. 00:32