[Swift] 최대공약수

유클리드 호제법을 사용해서 최대공약수를 구하는 함수를 구현할 수 있습니다.

a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. - 위키백과 유클리드 호제법

구현방법

func gcd(a: Int, b: Int) -> Int { 
	var a = a
	var b = b
    
    while b != 0 { 
    	let r = a%b
        a = b
        b = r
    } 
    
    return a 
} 
        
gcd(a: 24, b: 12) // returns 12

기본적으로 제공되는 Swift 함수의 파라미터는 상수이기 때문에 재귀함수를 사용하지 않고 구현한다면 코드가 상대적으로 길어질 수 있습니다.

func gcd(a: Int, b: Int) -> Int { 
	return b == 0 ? a : gcd(a: b, b: a%b)
}

gcd(a: 24, b: 12) // returns 12

삼항연산자와 재귀함수를 사용한 동일한 코드입니다. (재귀함수 사용이 낯설었는데 역시 처음이 어렵지)