[코딩 팁] 최대공약수 : 유클리드 호제법 원리

✍️ 최대공약수와 유클리드 호제법 코딩 테스트에서 심심치 않게 등장하는 최대공약수 구하기 2부터 시작하는 반복문으로 구할 수 있지만 유클리드 호제법을 사용하면 보다 효율적으로 구할 수 있다. 유클리드 호제법의 과정은 다음과 같다. 1. 큰 수를 작은 수로 나눈다. 2. 나누는 수를 나머지로 계속 나눈다. 3. 나머지가 0이 나오면 나누는 수가 최대공약수이다. $1512$와 $1008$의 최대공약수를 유클리드 호제법으로 풀어보면 $1512 = 1008 * 1 + 504$ $1008 = 504 * 2 + 0 $ 두 수의 최대공약수는 504이다. 💡 유클리드 호제법 이해하기 나는 원리를 알지 못한다면 금방 까먹는 사람으로서... 대충이라도 원리를 정리해 보려 한다. (1) 어떤 수 $A$를 $B$로 나눈다면 ..

• format_list_bulleted Algorithm/감명 깊게 본 코딩 팁
• · 2021. 12. 3.
• textsms

[프로그래머스 Level 1] 최대공약수와 최소공배수

문제 최대공약수와 최소공배수 두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다. 제한 사항 두 수는 1이상 1000000이하의 자연수입니다. 코드 #include using namespace std; int gcd(int a, int b) { int c; while(b != 0) { c = a % b; a = b; b = c; } return a; } vector solution(int n, int m) { int a = gcd(n, m); int b..

• format_list_bulleted Algorithm/프로그래머스 : Level 1
• · 2021. 11. 8.
• textsms