기본 콘텐츠로 건너뛰기

유클리드 호제법 (최대공약수)

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

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

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

이는 명시적으로 기술된 가장 오래된 알고리즘이다.

78696과 19332의 최대공약수를 구하면,


78696 ＝ 19332×4 ＋ 1368



19332 ＝ 1368×14 ＋ 180



1368 ＝ 180×7 ＋ 108



108 ＝ 72×1 ＋ 36



180 ＝ 108×1 + 72



72 ＝ 36×2




최대 공약수는 36













라벨:





























댓글











댓글 쓰기




















이 블로그의 인기 게시물



















11004 : K번째 수 [C++]




























# include < iostream >  # include < cstdio >  # include < algorithm >   int  main ( )  {   int  * Number =  new  int [ 5000000 ] ;    int  N ,  K ;   scanf ( " %d %d " ,  & N ,  & K ) ;    for  ( int  i =  0 ;  i <  N ;  i + + )    scanf ( " %d " ,  Number [ i ] ) ;    std :: sort ( Number ,  Number +  N ) ;    printf ( " %d " , Number [ K -  1 ] ) ;    return  0 ;  }  




















댓글 쓰기









자세한 내용 보기






























1149 : RGB Street Coloring (Dynamic Programming) [C,C++]




























 The key to this problem lies in understanding the principles.    Let me explain the algorithm to solve the problem by using DP.      First, you need the same storage space like input data's size.     When you draw any color of the nth house, the space will contain the minimum value.   If you paint the red in the second house, this value is sum of blue or green of the first house.      You must use DP because you must use the previous value.    Of course, you can also use the recursive algorithm to solve it. But if it gets bigger, it will take a lot of time.      If you paint the red in the nth house in the same way, you should add the lower value of the blue and green of the n-1th house.      Therefore, the minimum value can be found in the value of the storage space (n-1) index.         <pesudo code>      *Source of the problem =  https://www.acmicpc.net/problem/1149    *문제 출처  : BAEKJOON ONLINE JUDGE     




















댓글 쓰기









자세한 내용 보기




























11478 : 서로 다른 부분 문자열의 개수 (미제) [C++]




























# include < iostream >  # include < vector >  # include < string >   using  namespace  std ;   int  main ( )  {   string  sInput ;   getline ( cin ,  sInput ,  '\n' ) ;    int  Time =  1 ;   int  Count =  0 ;    vector < string >  Storage ;   for  ( int  i =  0 ;  i <  sInput . size ( ) ;  i + + )   {    for  ( int  j =  0 ;  ( j +  Time -  1 )  <  sInput . size ( ) ;  j + + )     Storage . push_back ( sInput . substr ( j ,  Time ) ) ;      Time + + ;   }    bool *  Visited =  new  bool [ Storage . size ( )  *  sizeof ( bool ) ] ;     for  ( int  i =  0 ;  i <  Storage . size ( ) ;  i + + )   {    Visited [ i ]  =  true ;    for  ( int  j =  0 ;  j <  Storage . size ( ) ;  j + + )    {     if  ( i ! =  j & &  Storage [ i ]  = =  Storage [ j ] )     {      Visited [ i ]  =  false ;      Visited [ j ]  =  true ;      break ;     }    }   }    for  ( int  i =  0 ;  i <  Storage . size ( ) ;  i + + )    if  ( Visited [ i ] )     Count ...




















댓글 쓰기









자세한 내용 보기