유클리드호제법 기출문제 풀이

 

2011 대비 정보처리 실기 기출문제 풀이 유클리드호제법

다음 문제는 2010년 정보처리기사에서 나온 기출문제라고 합니다. 이 문제에서 유클리드호제법만 알고 있다면 기능사, 산업기사, 기사 중에 어디에서든 나올 수 있는 수준의 문제입니다. 2010년에 기사에서 나왔으니 2011년에는 산업기사에서 나올 가능성이 있다고 봐야 겠습니다.

두 수 A, B에 대한 최대공약수와 최소공배수를 유클리드호제법으로 처리하시오.

풀이를 해보면
두수 A, B의 최대공약수를 유클리드호제법으로 구하는 공식은 A = B x Q + R 입니다.
여기에서 Q는 A/B = Q 입니다. 다시 말해 A를 B로 나눈 몫이 바로 Q입니다. R은 나머지 입니다.

이 공식을 이용하여 나머지가 0이 될 때까지 공식을 반복해서 마지막 나머지가 0이 었을 때의 B 값이 최대공약수가 됩니다.

이것을 좀 더 풀어서 쓰면 이렇습니다.
우선 A/B를 해서 몫인 Q를 구하고 A%B를 해서 나머지 R을 구합니다.
이때 만약 R이 0이면 B는 최대공약수가 됩니다. R이 0이 아니면
B의 값을 A에 넣고 B에는 나머지인 R을 넣습니다. 그리고 다시 나누기를 하여 나머지가 0인지를 확인하는 과정을 반복하는 것입니다. 이렇게 최대공약수를 구하고 나면 최소공배수는 (A x B)/최대공약수 라는 공식으로 구할 수 있습니다.

그래서 최소공배수는 최대공약수만 있으면 한번에 구해 집니다.
이것을 C로 프로그래밍을 하면 아래와 같습니다.

void main()
{
  int A, B, Q, R=1, G, L, HIGH, LOW; //나머지에 1을 넣어 아래에서 반복문을 들어가도록 합니다.
  /* Q: 몫, R: 나머지, G: 최대공약수, L:최소공배수, HIGH:A와B 중 큰값, LOW:A와B 중 작은값 */
   scanf("%d%d", &A, &B);  // A,B를 입력 받습니다.
   if(A>B){          // A와B를 비교하여 큰 값은 HIGH에 작은 값은 LOW에 넣습니다.
    HIGH = A;       // 이렇게 값을 다른 곳으로 옮기는 이유는 아래에서 나누기를 한 후 
    LOW = B;        //다음 나누기를 위하여 값을 옮길 때 A,B를 그래로 쓰면
   }           //처음 입력받은 값이 사라져 버리기 때문에 보호하기 위해서 입니다.
   else{
    HIGH = B;
    LOW = A;
   }
   while(R != 0) //나머지가 0이 될 때까지 반복을 합니다. 이 조건을 만족하기 위해서는
  {              //처음에 나머지 R에 0이 아닌 값이 들어가 있어야 합니다.
    Q=HIGH/LOW;  //몫은 사실 이 프로그램에서는 필요없기 때문에 생략해도 됩니다.
    R=HIGH%LOW;  // %연산자로 나머지를 구했지만 MOD() 함수로 구하기도 합니다.
    HIGH=LOW;    //일단 작은 값을 큰 값에 옮겨 다음 나누기를 준비합니다.
    LOW=R;       //일단 나머지를 작은 값에 옮겨 다음 나머지를 준비합니다.
  //이 while문을 반복하다가 나머지가 0이 되면 마지막 LOW는 이미 HIGH에 옮겨 놓고 LOW에는 나머지 0이 들어가 있는 상태이기 때문에 최대공약수는 HIGH에 들어가 있습니다.
  }
  G = HIGH;  //최대공약수를 G에 넣었습니다. 아래 최소공배수를 구할때
             // 굳이 G에 넣지 않고 HIGH를 그냥 사용해되 됩니다.
  L = (A*B)/G; //최소공배수를 구하여 L에 넣었습니다.
  printf("%d %d",G,L); //값을 출력합니다.
}
그래서 위 순서도의 답을 확인하면

1번 괄호에 들어 갈 것은 바로 위에서 LOW에 A가 들어 가서 HIGH에는 B를 넣어야 하기 때문에 HIGH = B 입니다.

 2번 괄호에 들어 갈 것은 MOD를 이용해 나머지를 구하는 것이기 때문에 R 입니다.
 3번 괄호에 들어 갈 것은 다음 나머지를 준비하는 것이기 때문에 LOW 입니다.
 4변 괄호에 들어 갈 것은 나머지도 LOW에 옮겨야 하기 때문에 LOW=R입니다.

5번 괄호에 들어 갈 것은 최소공배수를 구해야 하기 때문에 A x B 입니다.

정보처리 실기의 순서도 문제들은 알고리즘을 종류별로 잘 알고 있으면 쉽게 풀 수 있습니다. 그래서 순서도를 보며 공부하는 것도 중요하지만 알고리즘의 종류와 처리 방법등을 알아 두는 것도 중요합니다.