1. 기본 정수론(Basic Number Theory)
Basic Number Theory
•
정수(Integer)의 성질을 연구하는 분야입니다. (가령, 약수와 배수)
2. 약수(Divisor)
•
특정 정수를 나누어 떨어지게 하는 수
//MARK: - 약수
//MARK: - Framework
import Foundation
//MARK: - Function
func solution() -> Void {
//MARK: - Input
guard let N: Int = Int(readLine() ?? "0") else { return }
var answer: String = "\(1) "
//MARK: - Process
for i in 2..<N {
answer += N % i == 0 ? "\(i) " : ""
}
answer += "\(N)"
//MARK: - Output
print(answer)
}
solution()
Swift
복사
3. 소수(Prime Number)
•
약수가 1과 자기 자신 뿐인 정수
//MARK: - adv. 소수 판별
//MARK: - Framework
import Foundation
//MARK: - Function
func isPrime(_ number: Int) -> Bool {
var result: Bool = true
if number == 1 {
result = false
} else if number == 2 || number == 3 {
result = true
} else {
var start: Int = 2
while start * start <= number {
if number % start == 0 {
result = false
break
}
start += 1
}
}
return result
}
func solution() -> Void {
//MARK: - Input
guard let N: Int = Int(readLine() ?? "0") else { return }
var result: Bool = false
//MARK: - Process
result = isPrime(N)
//MARK: - Output
print(result ? "YES" : "NO")
}
solution()
Swift
복사
4. 에라토스테네스의 체
•
소수를 구하는 알고리즘 중 하나입니다.
•
소수의 배수를 지워 나감으로써 2부터 특정 범위 내의 소수를 얻을 수 있습니다.
•
O(N log N)의 시간복잡도를 가지게 됩니다.
•
2부터 N까지 모든 숫자들 중 모든 소수를 구할 때 사용하면 빠르지만, 특정 수가 소수인지 아닌지 판별할 때는 제곱근 까지 나눠보는 것이 더 빠르다고 할 수 있습니다.
//MARK: - 에라토스테네스의 체
//MARK: - Framework
import Foundation
//MARK: - Variable
var candidates: [Int] = []
//MARK: - Function
func getEratos(_ number: Int) -> Void {
for i in stride(from: 2, through: number, by: 1) {
for j in stride(from: i * 2, through: number, by: i) {
if candidates[j] == 0 {
continue
}
candidates[j] = 0
}
}
}
func solution() -> Void {
//MARK: - Input
guard let N: Int = Int(readLine() ?? "0") else { return }
candidates = Array(repeating: 0, count: N + 10)
for i in stride(from: 2, through: N, by: 1) {
candidates[i] = i
}
//MARK: - Process
getEratos(N)
//MARK: - Output
for i in 1...N {
if candidates[i] == 0 {
continue
}
print("\(candidates[i]) ", terminator: "")
}
}
solution()
Swift
복사
5. 소인수 분해
•
숫자 N을 소수의 곱으로 나타내는 것을 말합니다.
•
2부터 시작해서 차례대로 전부 나누어봄으로써 구할 수 있습니다.(2로 나누어 지는 수는 이미 앞에서 나눌 수 있을 때 까지 다 나누었기 때문에 4로 나누어지지 않는 것이 가능합니다. 3과 6, 5와 10 마찬가지)
//MARK: - Framework
import Foundation
//MARK: - Function
func solution() -> Void {
//MARK: - Input
guard let N: Int = Int(readLine() ?? "0") else { return }
var number: Int = N
var primeNumber: Int = 2
var answer: String = ""
//MARK: - Process
while number > 1 {
while number % primeNumber == 0 {
answer += "\(primeNumber)\n"
number /= primeNumber
}
primeNumber += 1
}
//MARK: - Output
print(answer, terminator: "")
}
solution()
Swift
복사
6. 유클리드 호제법
•
공약수 : A의 약수 이면서 동시에 B의 약수인 수 입니다.
•
공배수 : A의 배수 이면서 동시에 B의 배수인 수 입니다.
•
최대공약수(GCD, Greatest Common Divisor) : A의 약수 이면서 동시에 B의 약수인 수 중 가장 큰 수 입니다.
•
최소공배수(LCM, Least Common Multiple) : A의 배수 이면서 동시에 B의 배수인 수 중 가장 작은 수 입니다.
•
유클리드 호제법 : 최대공약수를 구하기 위한 알고리즘 입니다.
func getGCD(_ a: Int, _ b: Int) -> Int {
return a % b == 0 ? b : getGCD(b, a % b)
}
Swift
복사
7. 파스칼 삼각형
•
왼쪽 오른쪽 각 대각선 위의 수를 합하여 자신을 결정하는 형태이며 조합과 관련이 있습니다.
•
경우의 수 문제에서 숫자가 굉장히 큰 경우 활용할 수 있습니다. 가령, 20 C 10의 끝 3자리 수를 구하는 경우(파스칼 삼각형을 구성할 때, % 1000 연산 하는 경우를 볼 수 있습니다.)
func getPascalTriangle() -> Void {
let N: Int
var pascal: [[Int]] = [N + 10][N + 10]
pascal[0][0] = 1
for i in 1...N {
pascal[i][0] = 1
pascal[i][i] = 1
for j in 1...(i - 1) {
pascal[i][j] = pascal[i - 1][j - 1] + pascal[i - 1][j]
}
}
}
Swift
복사