스위프트 코딩테스트 강좌, 최대 공약수 구하기

안녕하세요! 오늘은 취업 준비하는 개발자 여러분을 위해 스위프트를 활용한 코딩테스트 강좌를 진행하겠습니다. 이번 주제는 바로 최대 공약수(Greatest Common Divisor, GCD)를 구하는 문제입니다. 최대 공약수는 두 숫자가 가지고 있는 공통적인 약수 중 가장 큰 수로, 수학적 개념 외에도 다양한 알고리즘 문제에서 활용됩니다.

문제 설명

주어진 두 정수 a와 b의 최대 공약수를 구하는 함수를 스위프트로 작성하세요. 또한, 두 숫자가 모두 0일 경우에는 ‘정의되지 않음’이라는 메시지를 출력해야 합니다.

func gcd(_ a: Int, _ b: Int) -> String

문제 해결 접근 방식

최대 공약수를 구하는 방식은 여러 가지가 있지만, 가장 일반적으로 사용하는 방법은 유클리드 호제법(Euclidean Algorithm)입니다. 이 알고리즘은 다음의 두 가지 간단한 사실에 기반합니다:

  • 두 수 a와 b의 최대 공약수는 gcd(a, 0) = |a|입니다.
  • 두 수 a와 b의 최대 공약수는 gcd(a, b) = gcd(b, a % b)입니다.

유클리드 호제법의 구현

위의 두 원리를 바탕으로 유클리드 호제법을 적용하여 최대 공약수를 구하는 방법을 단계별로 설명하겠습니다.

1단계: 함수 정의

먼저, 두 정수를 입력받아 최대 공약수를 반환하는 함수를 정의합니다. 함수의 시그니처는 다음과 같습니다:

func gcd(_ a: Int, _ b: Int) -> String

2단계: 입력 검증

함수 내부에서 입력받은 두 값이 모두 0인지 체크합니다. 이 경우, 우리는 ‘정의되지 않음’ 메시지를 반환합니다:

if a == 0 && b == 0 {
        return "정의되지 않음"
    }

3단계: 알고리즘 구현

유클리드 호제법을 사용하여 최대 공약수를 반복적으로 계산합니다. 이 과정에서는 두 숫자를 서로 바꾸면서 나머지를 사용하여 값을 업데이트 합니다:

var a = abs(a)
    var b = abs(b)

    while b != 0 {
        let temp = b
        b = a % b
        a = temp
    }
    return String(a)

4단계: 전체 코드 완성

위의 단계들을 모두 통합하면 최종적인 최대 공약수 함수를 완성할 수 있습니다:

func gcd(_ a: Int, _ b: Int) -> String {
        if a == 0 && b == 0 {
            return "정의되지 않음"
        }
        var a = abs(a)
        var b = abs(b)

        while b != 0 {
            let temp = b
            b = a % b
            a = temp
        }
        return String(a)
    }

테스트 케이스

이제 우리가 작성한 최대 공약수 함수를 다양한 테스트 케이스로 검증해 보겠습니다. 아래는 몇 가지 예시 테스트 케이스입니다:

print(gcd(48, 18)) // 출력: 6
print(gcd(0, 0)) // 출력: 정의되지 않음
print(gcd(56, 98)) // 출력: 14

결론

이번 강좌에서는 스위프트로 최대 공약수를 구하는 알고리즘 문제를 다뤘습니다. 유클리드 호제법의 원리에 따라 간결하고 효율적인 코드를 작성할 수 있었습니다. 알고리즘 문제는 수학적 원리를 이해하고 이를 프로그래밍으로 구현하는 연습을 통해 더욱 발전할 수 있습니다. 앞으로도 지속적으로 다양한 주제로 코딩테스트 강좌를 진행할 예정이니 많은 관심 부탁드립니다!

© 2023 알고리즘 문제 풀이 강좌