유클리드 호제법(Euclidean Algorithm)

개념

• 두 수의 최대공약수 (GDC, Greates Common Divisor)를 구하는 알고리즘
• 호제법 - 두 수를 나누고 나머지를 이용하는 방식

원리

• 어떤 자연수 A, B (A > B) 에 대해  A를 B로 나눈 나머지를 r이라고 할 때
  GDC(a,b) = GDC(b,r)이 성립한다.
• 이를 반복하여 나머지가 0이 되면 , 그때의 나누는 수가 최대공약수이ㅏㄷ.

코드 예시

int GCD(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

void Start() {
    Debug.Log(GCD(48, 18));  // 출력: 6
}

 

예시와 같이 48 18이 있다면

48 % 18 은 12가 되고 

18 % 12 는 6이되고

12 % 6 은 0이 되므로, 최대 공약수는 6이 된다. 

 

유니티에서의 사용

• 비율 정규화 (좌표, 크기 조정) : 게임 오브젝트의 크기나 비율을 일정한 비율로 조정 EX) 해상도 조정
• 타일맵 시스템에서 격자 크기 조정 : 서로 다른 타일 크기의 최소 공통단위를 찾음
• FPS 조절 및 프레임 동기화 : 서로 다른 프레임 속도를 가진 시스템 간의 최적 주기 찾음

시간복잡도

• O(log N)의 시간 복잡도