[알고리즘 스터디] 1주차_재귀함수_Ex015

입력 받은 두 수의 최대 공약수를 구하고, 전개도 작성하기

유클리드 호제법

---

(조건1) a > b
(조건2) a와 b는 양의 정수
(조건3) a와 b는 서로소

gcd = 최대 공약수 (ex) gcd(x, y)는 x와 y의 최대공약수

① a = AG, b = BG
-> 조건1에 따라 a는 b로 나눌 수 있다.

② a = qb + r (q는 몫, r은 나머지)
-> ①의 내용을 대입한다.

③ AG = qBG + r
-> G로 묶는다

④ G(A-qB) = r, b = BG
-> 두 식 사이에는 G라는 공통의 약수가 생긴다.

#include <iostream>
#include "Practice.h"

void gcd(int a, int b)
{
    if (a < b)
    {
        gcd(b, a); //  a < b 이면 순서를 바꿔서 함수를 실행한다.
        return;
    }

    // 여기까지 오면 무조건 a > b

    if (a % b != 0) // a % b 가 0이 아니면 
    {
		gcd((a % b), b); // 다시 실행
    }
    else
    {
        std::cout << b; // 최대 공약수 출력 
    }
}

int main(void)
{
    gcd(1071, 1029);
    
    return 0;
}

// 전개도

gcd(24, 36)
{
    if (true)
    {
        gcd(36, 24)
        {
            if(false)
            if(true) // 36 % 24 = 12
            {
                gcd(12, 24)
                {
                    if (true)
                    {
                        gcd(24, 12)
                        {
                            if (false)
                            if (false)
                            cout(12);
                        }
                    }
                }
                return;
            }
        }
        return;
    }
}

<실행 결과>

결론

---

a와 b중 작은수(b)로 큰 수(a)로 나눴을 때 나머지가 0이 아니면
나머지와 b 중 작은수로 다른 수를 나누는 과정을 반복한다.
나머지가 0이 되면 그 때 나눈 수(둘 중 작은 수)가 최대 공약수가 된다.