
Algorithm 공부 #27 - 확장 유클리드 호제법 ✏️ 유클리드 호제법최대공약수 관련 문제들을 풀어봤다면 한번쯤은 접해 봤을 법한 알고리즘자연수 a와 b가 주어졌을 때 gcd(a,b) 즉 a와 b의 최대공약수를 구할 수 있음 a를 b로 나눈 몫을 q라고 하고, 나머지를 r이라 하면 a= bq + r로 나타냄이때 gcd(a,b) = gcd(b,r)을 만족 gcd(a,b)=g">gcd(a,b)=ggcd(a,b)=g라고 하면, g|a">g|ag|a, g|b">g|bg|b 를 만족하게 되고, r=a−bq">r=a−bqr=a−bq이므로 g|(a−bq)=r">g|(a−bq)=rg|(a−bq)=r 을 만족gcd(b,r)=g">gcd(b,r)=ggcd(b,r)=g라고 해도, g|b">g..

✏️문제 링크 https://www.acmicpc.net/problem/2436 2436번: 공약수 첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0 www.acmicpc.net ✏️문제 설명 ✏️문제 풀이 일단 문제를 보기에 앞서 두 수를 a, b 라 하면 a와 b의 최대공약수는 m=gcd(a,b)이고, 최소공배수는 a*b/m입니다. 즉 문제에서 최대공약수와 최소공배수가 주어지는데 정답으로 출력하고자 하는 두 개의 자연수의 곱은 최대공약수 * 최소공배수가 되어야 합니다. 이는 최소공배수와 최대공약수를 구하는 식을 보시면 당연한 결과입니다 int형으로 하면 ..

Algorithm 공부 #12 - 정수론(유클리드 호제법과 확장 유클리드 호제법) 유클리드 호제법(최대 공약수 구하기) ● 큰 수를 작은 수로 나누는 MOD연산 ● 앞 단계에서 나왔던 작은 수와 나머지를 다시 MOD연산 ● 이렇게 반복하면서 나머지가 0이 되면 그 순간의 작은 수를 최대 공약수로 선택 ex) 270과 192 270 mod 192 = 78 192 mod 78 = 36 78 mod 36 = 6 36 mod 6 = 0 => 0이 되는 순간 6을 return, 즉 270과 192의 최대공약수는 6 백준 1934번 최소공배수 https://www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수..

백준 3036번 링https://www.acmicpc.net/problem/3036 3036번: 링출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다.www.acmicpc.net 정답 코드#include using namespace std; int arr[100]; int find(int a, int b); int main() { int n; cin >> n; for (int x = 0; x > arr[x]; for (int x = 0; x < n - 1; x++) { int res = find(arr[0], arr[x + 1]); cout
- Total
- Today
- Yesterday
- 카운팅 정렬
- HTML5
- 이분 매칭
- C++ Stack
- 백준
- 자료구조
- 에라토스테네스의 체
- 알고리즘 공부
- html
- c++ string
- DFS
- 스택
- 유클리드 호제법
- 자바스크립트
- 우선순위 큐
- 유니온 파인드
- js
- 자바
- DP
- 투 포인터
- BFS
- 스프링 부트 crud 게시판 구현
- CSS
- C++
- 반복문
- Do it!
- 알고리즘
- java
- 백준 풀이
- 세그먼트 트리
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | ||||||
2 | 3 | 4 | 5 | 6 | 7 | 8 |
9 | 10 | 11 | 12 | 13 | 14 | 15 |
16 | 17 | 18 | 19 | 20 | 21 | 22 |
23 | 24 | 25 | 26 | 27 | 28 |