Kata의 IOS

안녕하세요. KataRN입니다. 코테 문제를 풀다보면 소수를 구하는 문제가 많습니다. 보통 소수관련 문제가 나오면 효율성도 좋아야 되더라구요... 그리고 소수와 효율성하면 꼭 언급하는 이론이 있습니다. 그건 바로 '에라토스테네스의 체' 입니다. 소수를 하나하나 구하는것보다 아래의 그림처럼 소수의 배수를 제거하는것이 빠릅니다. 이를 포함하여 소수판별코드, 소수의개수, 소수구하기 등을 코드로 구현해봤습니다. 소수 판별 코드(swift) func isPrime(_ num: Int) -> Bool { if num == 0 { return false } if num < 4 { return num == 1 ? false : true } for i in 2...Int(sqrt(Double(num))) { if num..

안녕하세요. KataRN입니다. 오늘은 최대공약수와 최소 공배수에 대해 알아보겠습니다. 최대공약수와 최소공배수에 대한 문제를 풀기 위해 코드를 작성했으나 전부 시간초과가 났습니다. 이건 답은 같아도 비효율적이기 때문입니다. 그래서 제가 내린 결론은 무조건 '유클리드 호제법을 이용하여 만들어야한다' 입니다. 유클리드 호제법이란? 유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 최대공약수, 최소공배수 코드(swift) //최대공약수 func gcd(_ a: Int, _ b: Int) -> Int { if b == 0 { return a } else { return gcd(b,..