목록유클리드호제법 (2)

안녕 세상아,

[c/c++/알고리즘]유클리드 호제법, 최대공약수와 최소공배수의 관계

유클리드 호제법이란? 2개의 자연수의 최대공약수를 구하는 알고리즘이다. 2개의 자연수 a,b에 대해 a를 b로 나눈 나머지를 r이라고 하면 (a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. ​ b를 r로 나눈 나머지 x를 구하고, 다시 r을 x로 나눈 나머지를 구하는 과정을 반복한다. 결국 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. ​ 예시 1925와 819의 최대공약수 1925%819=287 -> 819%287=245 -> 287%245=42 -> 245%42=35 -> 42%35=7 -> 35%7=0 ====> 7이 최대 공약수! int gcd(int a, int b) { int c; while (b) { c = a % b; a = b; b = c; } retur..
c++ 개념 2024. 4. 4. 19:23
[c++/프로그래머스] N개의 최소공배수

https://school.programmers.co.kr/learn/courses/30/lessons/12953 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 유클리드호제법을 사용해서 최대공약수를 구했다. 최소공배수와 최대공배수의 곱은 두 수의 곱과 같기 때문에 최대공약수를 구하면 최소공배수는 간단하게 구할 수 있다. #include #include using namespace std; //두개씩 비교해서 결론 도달 -> 시간초과 안되겠지? //최소공배수는 유클리드호제법 사용? //최대공약수 유클리드호제법 사용 int gcd(int a, int b){ ..
프로그래머스 2023. 8. 31. 15:48
이전 Prev 1 Next 다음