[백준] 수학 | 최대공약수(GCD) 문제 풀이 전략과 관련 문제

해당 알고리즘 풀이 게시글은 python을 기준으로 작성되었습니다.

 

1. 최대 공약수(GCD) 개념 정리

이미지 출처 - TCP 코딩 스쿨

 

 

최대 공약수(GCD, Greatest Common Divisor)란

두 개 이상의 정수에서 공통으로 나눌 수 있는 가장 큰 수를 의미한다.

 

파이썬에서는 표준 라이브러리인 math 모듈에서

gcd 함수를 기본 제공하므로 직접 구현하지 않고도 간단하게 사용할 수 있다.

import math 

math.gcd(12, 18) # 6
math.gcd(24, 16) # 8

 

알고리즘 문제에서 GCD는 단순한 수학 계산 문제 보다

수의 규칙성, 차이, 공통된 간격 등을 찾아내는 핵심 도구로 활용된다.

 

 

2. 유클리드 호제법

math.gcd 내부 구현은 유클리드 호제법을 기반으로 하며,

최대 공약수를 구하는 가장 효율적인 핵심 방법으로 기본적으로 이해하고 있어야 한다.

 

핵심 아이디어

두 수 a, b (a > b) 에 대해 

gcd(a, b) = gcd(b, a % b)

 

나머지가 0 이 될 때의 b가 최대 공약수이다.

그 예시로는 다음과 같다.

48 % 18 = 12
18 % 12 = 6
12 % 6 = 0 → GCD = 6

 

 

파이썬  최대 공약수 함수 구현

파이썬으로 유클리드 호제법을 직접 구현하면 다음과 같은 형태가 된다.

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

 

위 함수는
gcd(a, b) = gcd(b, a % b) 규칙을 그대로 반복문으로 구현한 형태이며,
나머지가 0이 되는 순간의 a가 최대 공약수가 된다.

 

시간 복잡도는 O(logN) 으로 매우 효율적이며,

대부분의 최대 공약수 문제는 해당 로직을 기반으로 확장된다.

 

 

재귀 함수 코드 구현

해당 함수는 재귀 형태로도 간단하게 구현할 수 있다.

def gcd_recursive(a, b):
    if b == 0:
        return a
    return gcd_recursive(b, a % b)

 

 

다만, 입력 값이 매우 크거나 재귀 호출이 깊어질 경우

RecursionError가 발생할 수 있다.

 

오랜만으로 맛을 본 재귀 함수의 그림자. . .

 

(추가) 관련 영상 추천

텍스트로 전달되는 이해 전달에는 한계가 있기 때문에,

유클리드 호제법을 원리를 증명하는 아래의 영상을 보는 것을 추천한다.

 

 

3. 최소공배수(LCM)와의 관계

파이썬에서는 최소공배수 LCM도 GCD를 이용해 간단히 구할 수 있다.

import math

lcm = a * b // math.gcd(a, b)

 

따라서 GCD를 정확히 이해하고 있다면,
LCM이 포함된 문제 역시 자연스럽게 해결할 수 있다.

 

 

 

4. 추천 알고리즘 문제 (백준)

• 최대공약수와 최소공배수 : GCD / LCM 기본 패턴 익히기
• 최대 공약수 : 여러 수의 GCD 누적 계산
• 숨바꼭질 6 : GCD 관련 응용 알고리즘 문제
• 검문 : GCD 관련 응용 알고리즘 문제

 

 

5. 마지막으로

다시 수학 부분 알고리즘을 공부하면서

왜 최대 공약수를 구하는 걸 알아야 해? 라고 생각했지만,

공통된 간격 등 활용할 수 있는 부분이 많음을 배우며 문제를 보는 시야가 조금 넓어짐을 느꼈다.

 

파이썬에 math 모듈을 거의 활용하지 않았던 것 같다.

해당 추천 문제들을 직접 풀면서, gcd 함수를 만들어서 해결했는데

파이썬이 주는 유익한 모듈들을 써볼 수 있어야 겠다.

 

알고리즘 문제 해결 코드 참고 : github 링크

algo_study/baekjoon/구현/수학 at master · jung-jinyoung/algo_study