알고리즘 공부 ) 프로그래머스 - 최대공약수와 최소공배수 C++

유클리드 호제법(Euclidean algorithm)은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 

호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

2개의 자연수a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

1. 1. 입력으로 두 수 m,n(m>n)이 들어온다.
2. 2. n이 0이라면, m을 출력하고 알고리즘을 종료한다.
3. 3. m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.
4. 4. 그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다.

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 29 30 31 32 33

#include<vector> #include<iostream> using namespace std; vector<int> gcdlcm(int a,int b) {     vector<int> answer;   int mul= a*b;   int temp;     while(b)   {     temp= a%b;       a=b;     b= temp;   }   answer.push_back(a);   answer.push_back(mul/a);     return answer; } int main() {     int a=3, b=12;     vector<int> testAnswer = gcdlcm(a,b);     cout<<testAnswer[0]<<" "<<testAnswer[1]; }     // 위와 같이 return vector를 하면 바로 복사가 되는가?  // v1= v2 와 같은건데,, 궁금해서 다른 방법을 찾아보았당 // 예시 vector<int> v1; // 어떤 배열이 있을 때 vector<int> v2( v1.begin(), v2.end() );  // assign 사용  v2.assign(v1.begin()+1, v1.begin()+5);

cs