[#5][알고리즘] 최대공약수와 최소공배수

프로그래머스(Programmers) > 최대공약수와 최소공배수

문제링크 (https://programmers.co.kr/learn/challenge_codes/149)

C++ 풀이

#include<vector> #include<iostream> using namespace std; vector<int> gcdlcm(int a,int b) {   vector<int> answer;   int gcda, gcdb, gcdc;   gcda = a;   gcdb = b;   while( b != 0){     gcdc = a%b;     a = b;     b = gcdc;   }   answer.push_back(a);   answer.push_back(gcda*gcdb/a);   return answer; } int main() {     int a=3, b=12;     vector<int> testAnswer = gcdlcm(a,b);     cout<<testAnswer[0]<<" "<<testAnswer[1]; } Colored by Color Scripter

cs

gcdlcm(3,12);

입력받은 a와 b값을 각각 gcda, gcdb에 저장
gcda = 3;
gcdb = 12;

b가 0이 아닌 동안 연산하며 한 칸씩 앞으로 당김
a     b     gcdc
3    12    3
--↙----↙----------------------
a     b    gcdc
12   3     0
--↙----↙----------------------
a     b   gcdc
3     0
--↙----↙----------------------
=> 연산 끝

결과
최대공약수 = a = 3
최소공배수 = a * b / 최대공약수 = a * b / 3 = 3 * 12 / 3 = 12