프로그래밍 언어로 스위프트(Swift)를 배우는 것은 많은 개발자에게 흥미로운 경험입니다. 이번 강좌에서는 코딩 테스트에서 자주 등장하는 ‘소수’ 문제를 다루고, 스위프트를 사용하여 이를 해결하는 방법을 단계별로 알아보도록 하겠습니다. 우리는 ‘신기한 소수 찾기’라는 문제를 통해 이를 설명할 것입니다.
문제 설명
주어진 정수 N (1 ≤ N ≤ 10000)에 대해, 1 이상 N 이하의 모든 소수를 출력하시오.
소수란?
소수는 1과 자기 자신 외의 약수를 가지지 않는 1보다 큰 자연수입니다. 예를 들어, 2, 3, 5, 7은 모두 소수입니다. 반면, 4, 6, 8, 9는 소수가 아닙니다.
문제 접근 방법
이 문제를 해결하기 위해 다음과 같은 방법을 사용하겠습니다. 소수를 찾는 여러 방법 중 하나는 에라토스테네스의 체(Sieve of Eratosthenes)라는 알고리즘입니다. 이 알고리즘은 효율적으로 소수를 찾을 수 있는 방법으로, 주어진 숫자 범위 내의 모든 소수를 찾는데 효과적입니다.
에라토스테네스의 체 알고리즘
- 1부터 N까지의 모든 정수를 포함하는 리스트를 생성합니다.
- 2부터 시작하여, 현재 수의 배수를 모두 리스트에서 제거합니다.
- 리스트의 다음 남은 수로 계속해서 위의 과정을 반복합니다.
- N까지의 모든 수를 처리한 후, 리스트에 남아 있는 수가 소수입니다.
스위프트 코드 구현
이제 스위프트로 이 알고리즘을 구현해 보겠습니다. 아래의 코드는 주어진 N에 대해 모든 소수를 출력하는 방법을 보여줍니다:
func findPrimes(upTo n: Int) -> [Int] {
guard n >= 2 else { return [] }
var isPrime = [Bool](repeating: true, count: n + 1)
isPrime[0] = false
isPrime[1] = false
for i in 2...Int(sqrt(Double(n))) {
if isPrime[i] {
for j in stride(from: i * i, through: n, by: i) {
isPrime[j] = false
}
}
}
return isPrime.enumerated().compactMap { $0.element ? $0.offset : nil }
}
// 사용 예
let n = 100
let primes = findPrimes(upTo: n)
print("1부터 \(n)까지의 소수는: \(primes)")
코드 설명
위의 코드는 다음과 같이 작동합니다:
- 함수
findPrimes는 인자n을 받아 1부터n까지의 소수를 찾습니다. isPrime배열을 생성하여, 모든 인덱스를 소수로 초기화합니다. 인덱스 0과 1은 소수가 아니므로false로 설정합니다.- 2부터
sqrt(n)까지의 모든 숫자에 대해 반복하며, 현재 숫자가 소수라면 그 배수를 소수 목록에서 제거합니다. - 리스트의 남은 요소를 출력합니다.
테스트 및 결과
이제 코드를 실행하고 결과를 확인해 보겠습니다. 예를 들어, n = 100일 때의 출력 결과는 다음과 같아야 합니다:
1부터 100까지의 소수는: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
시간 복잡도
에라토스테네스의 체 알고리즘은 평균적으로 O(n log log n)의 시간 복잡도를 가집니다. 이는 소수를 찾는 효과적인 방법 중 하나로, n이 커질수록 훨씬 빠르게 소수를 찾을 수 있습니다.
마무리
이번 강좌에서는 스위프트를 활용하여 소수를 찾는 알고리즘을 다루었습니다. 이러한 기초적인 알고리즘 문제를 통해 코딩 실력을 향상시킬 수 있으며, 나아가 복잡한 문제에 대한 해결 능력을 기를 수 있습니다. 문제를 해결하는 과정에서 다양한 알고리즘과 프로그래밍 개념을 적용해보시기 바랍니다.
더 많은 소스 코드와 알고리즘을 배우고 싶다면, 다음 강좌를 기대해 주세요!