백준 문풀31 백준 11401 #c 언어 #이항계수 #모듈러 역원 # 페르마의 소정리 #이진 곱셈 먼저 이항계수 구하는 방법.. 볼 때마다 기억이 나지 않아서 찾아보는 내가 싫다.. 당연히 모듈러 연산이니까 덧셈, 곱셈처럼 계신해주면 된다고 생각했는데 나눗셈 연산은 그렇게 계산하는게 아니란다.. 나누기 연산은 나누는 숫자의 역원을 구하여 곱해주는 것이 맞음 이때 [페르마의 소정리]와 [확장 유클리드 호제법]이 있음. 페르마의 소정리는 나누는 숫자가 소수여야 한다는 제한이 있고확장 유클리드 호제법은 연산에 사용되는 두 숫자가 서로소여야 한다는 조건이 있음 여기서는 m 이 1000000007로 소수이기 때문에 페르마의 소정리를 이용한다. (n * n-1 * ...* k+1) / (n-k * n-k-1 * ...* 2) 의 연산을 해주.. 2024. 9. 6. 백준 1655 가운데 숫자 찾기 c++ 처음에는 이진 탐색을 이용하여 재귀 호출로 문제를 풀어보려 했자.. 그치만 자꾸 메모리 초과가 나와서 다른 방법을 찾아보니 우선순위 큐를 이용하여 중간 값을 찾을 수 있었다! 오름차순으로 정렬한 max heap 과 내림차순으로 정렬한 min heap 을 이용하였다.priority_queue, greater> minheap;priority_queue> maxheap; //비교 함수를 주지 않으면 자동으로 오름차순으로 설정 두 힙에 번갈아가며 수를 넣어주는데, min의 top이 max 의 top 보다 더 작은 경우 top을 swap 해준다.결과적으로 max의 top에는 중간값이 오게 된다!처음에 숫자를 할당해줄 heap 을 min heap 으로 정해 heap 의 size 가 같다면 .. 2024. 9. 3. 백준 1822 차집합#include #include#include#includeusing namespace std;using ll = long long;int main() { ll n, m; cin >> n >> m; vectora(n); vectorb(m); for (ll i = 0;i >a[i]; } for (ll i = 0;i > b[i]; } sort(a.begin(), a.end()); sort(b.begin(), b.end()); vectordifference; set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(difference)); cout difference 벡터로 크기는 측정해야겠고 set_difference 함수로 저장도 해.. 2024. 8. 22. 백준 10816 숫자 카드 2 #include#include #includeusing namespace std;vectormy_card;vectorfind_card;int n, m,answer=0;int main() { cin.tie(NULL); ios::sync_with_stdio(false); cin >> n ; for (int i = 0;i > c; my_card.push_back(c); } cin >> m; for (int i = 0;i > c; find_card.push_back(c); } sort(my_card.begin(), my_card.end()); vectoranswer(m); for (int i = 0; i 탐색 과정에서 이진 탐색을 진행하였는데 알고리즘 헤더에 존재하는upper_bound (arr.begi.. 2024. 8. 9. 이전 1 2 3 4 5 6 ··· 8 다음
