전체 글107 [수학] 백준 1629: 곱셈 1629번: 곱셈 (acmicpc.net) 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 그냥 (A^B)%C를 연산하면 풀 수 없다. 일단 범위를 벗어난다. 그래서 다음과 같은 modulo 연산의 성질을 이용해야 한다. (X*Y)%Z = ((X%Z)*(Y%Z))%Z 위 성질을 통해 long long int의 범위 내에서 계속 결과값이 형성되도록 관리해 주어야 한다. 이를 반복문을 통해 B번 순회하면서 하고 있으면 O(N)의 시간복잡도에 걸리기 때문에 다음과 같은 지수함수의 성질을 응용한다. X^Y = X^(Y/2)*X^(Y/2) 이를 통해 시간 복잡도를 O(logN) 수준.. 2024. 4. 4. [자료구조] Map 정의 Map은 pair를 저장하는 자료구조이다. Map은 여기에 더해 다음 두 가지 특성을 가진다. 1. key는 반드시 자연수가 아니어도 괜찮다.(non-numeric key) 2. key가 반드시 연속될 필요는 없다.(non-consecutive key) 3. value는 중복될 수 있지만, key는 반드시 unique해야 한다. 응용 어떤 unique한 key로 무엇인가를 분류해야 하는 경우에 사용할 수 있다. - 주민등록번호(key),이름(value): 이름은 동명이인이 있을 수 있지만 주민등록번호는 각 개인이 모두 고유한 값을 가지기 때문에 map을 이용하는 것이 적절하다. - 국가 이름(key):각 국가가 사용하는 화폐(value) : 각 국가 이름은 고유하지만, 화폐는 여러 국가가 같은 화폐.. 2024. 3. 15. [자료구조] Heap(2) 새로운 last node 위치 찾기 앞선 포스팅에서 heap의 insertion, removal 연산이 last node를 필요로 한다는 것을 언급하였다. insertion 연산은 맨 끝에( 새로운 last node 위치에) 새 node를 삽입한 후 up-heap bubbling을 통해 heap을 업데이트하였고, removal 연산은 제거하고자 하는 node를 last node와 교환한 후 down-heap bubbling을 통해 heap을 업데이트하였다. 따라서 heap에서는 last node 위치를 적절히 업데이트 해 주는 것이 필수적이다. insertion 연산을 할 때는 다음 절차를 거쳐 새 last node가 삽입될 위치를 구한다. 1. 기존 last node로부터, 어떠한 node의 left .. 2024. 3. 5. [자료구조] Heap (1) 정의 Heap은 Binary Tree의 일종으로, 다음과 같은 특징을 가진다. 1) Heap-Order: 부모 node의 key와 그 자식 node의 key간 특정한 순서가 존재한다. 부모의 key가 항상 자식의 key보다 큰 경우를 max-heap, 작은 경우를 min-heap 이라 한다. 이러한 특성 때문에 heap에서는 항상 가장 큰 key 값을 가진(max-heap의 경우), 또는 가장 작은 key 값을 가진(min-heap의 경우) node가 root node가 된다. 2) Complete Binary Tree heap은 complete binary tree 구조로, 각 level이 가질 수 있는 최대한의 node를 가지고 있다(1->2->4...). 따라서 n개의 element를 가진 heap.. 2024. 3. 4. 이전 1 ··· 3 4 5 6 7 8 9 ··· 27 다음
