스위프트 코딩테스트 강좌, 소수 구하기

작성자: 조광형 | 날짜: [작성일자]

서론

프로그래밍 언어 스위프트(Swift)는 macOS 및 iOS 애플리케이션 개발에 널리 사용됩니다.
취업을 위한 알고리즘 시험에서 소수(prime number)를 찾는 문제는 자주 출제되며, 그 해결 방법에 대한 충분한 이해와 실습이 필요합니다.
이 글에서는 소수를 판별하는 알고리즘 문제를 예시로 들고, 그 해결 과정을 단계별로 설명하겠습니다.

문제 설명

문제: 주어진 정수 N 이하의 모든 소수를 구하라.

소수가 무엇인지에 대한 간단한 정의: 소수는 1과 자기 자신 외에는 약수가 없는 자연수입니다. 즉, 1과 N으로만 나누어 떨어지는 수입니다.
예를 들어, 2, 3, 5, 7, 11, 13, 17, 19 등이 소수입니다.
이 문제의 목표는 입력으로 주어진 N 이하의 모든 소수를 찾아 배열 또는 리스트 형태로 반환하는 것입니다.

구현 방안

소수를 찾는 문제는 여러 가지 접근 방법이 있지만, 여기서는 에라토스테네스의 체(Sieve of Eratosthenes) 알고리즘을 사용하여 소수를 찾는 방법을 다루겠습니다.
이 방법은 O(N log log N)의 시간 복잡도로 소수를 효율적으로 찾을 수 있습니다.

1단계: 배열 초기화

먼저, N+1 크기의 부울 배열을 생성하여 각 인덱스가 소수인지 여부를 나타내도록 초기화합니다.
모든 인덱스는 true로 초기화하며, 인덱스 0과 1은 false로 설정합니다.

2단계: 소수 판별

2부터 시작하여 각 숫자를 검사합니다.
현재 숫자가 소수로 판별되면, 그 숫자의 배수를 모두 false로 설정합니다.
이 과정을 N의 제곱근까지 반복합니다.

3단계: 소수 출력

최종적으로 true로 남아 있는 인덱스는 모두 소수입니다.
이 인덱스를 이용해 결과 리스트를 출력합니다.

스위프트 코드 구현

        
        func sieveOfEratosthenes(n: Int) -> [Int] {
            // N+1 크기의 배열 초기화
            var isPrime = [Bool](repeating: true, count: n + 1)
            isPrime[0] = false // 0은 소수가 아님
            isPrime[1] = false // 1은 소수가 아님

            // 소수를 판별
            for i in 2...Int(sqrt(Double(n))) {
                if isPrime[i] {
                    for multiple in stride(from: i * i, through: n, by: i) {
                        isPrime[multiple] = false
                    }
                }
            }

            // 소수 리스트 생성
            var primes: [Int] = []
            for i in 2...n {
                if isPrime[i] {
                    primes.append(i)
                }
            }
            
            return primes
        }

        // 예시 실행
        let n = 30
        let primesUnderN = sieveOfEratosthenes(n: n)
        print("소수:", primesUnderN)

코드 설명

위의 스위프트 코드는 주어진 N 이하의 소수를 찾는 방법을 구현합니다.
func sieveOfEratosthenes라는 함수는 정수 N을 입력받아 따르는 과정을 실행합니다.

배열 초기화: N+1 크기의 부울 배열을 생성하여 모든 값을 true로 설정합니다.
소수 판별: 2부터 시작하여 모든 소수를 판별하고, 해당 소수의 배수를 false로 설정합니다.
소수 출력: 최종 배열을 확인하여 true로 남아 있는 모든 인덱스를 리스트 형태로 반환합니다.

예제 실행

N = 30일 때, 위의 코드를 실행하면 다음과 같은 결과가 출력됩니다:

        
        소수: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

결론

소수를 계산하는 것은 프로그래밍을 배우는 데 있어 중요한 주제가 될 수 있으며, 면접에서도 흔히 출제됩니다.
에라토스테네스의 체 알고리즘을 사용하면 효율적으로 소수를 찾을 수 있습니다.
이 글에서 설명한 방법과 코드를 참고하여 다양한 입력값에 대해 직접 테스트해보시기 바랍니다.
소수를 찾는 것은 알고리즘을 연습하는 좋은 방법이며, 더 복잡한 문제를 해결하기 위한 기초가 될 수 있습니다.

서론