Mathematics

[MUKER-WON]

9/25 링크

[stealmh]

수학

소수

1과 자신으로만 나눠지는 수 즉 약수가 2개인 수를 말한다. 2부터 n-1까지의 수로 나누어지지 않는 수

1은 소수가 아니다.

합성수 1과 자기 자신을 제외한 다른 약수를 가지고 있는 수

연산이 최대 n-2번 발생하기때문에 시간복잡도는 O(n) 이 시간복잡도를 O(sqrt(n))으로 줄일 수 있는 방법이 있다

합성수 N에서 1을 제외한 가장 작은 약수는 sqrt(N) 이하이다. N이 9라면, sqrt(9)는 3이다. 가장 작은약수는 3이하고 1,3,9중 1을 제외한 가장 작은 약수는 3이 됨

따라서 2부터 n-1까지의 수로 나누어지지 않는 수를 지금까지 소수라고 했다면 O(n) 2부터 sqrt(n)까지의 수로 나누어지지 않으면 소수이다. O(sqrt(n))

연습문제

1978: 소수찾기

코드

```swift var primeCount: Int = 0 let n = Int(readLine()!)! let listup = readLine()!.split(separator: " ").map { Int($0)! } for i in listup { if isPrime(i) { primeCount += 1 } } func isPrime(_ num: Int) -> Bool { if num == 1 { return false } for i in 2...num where i * i <= num { if num % i == 0 { return false } } return true } print(primeCount) ```

[MUKER-WON]

수학 (Mathematics)

• 수학 개념이 들어간 알고리즘. 코딩테스트에서는 비교적 쉬운 수학 개념이 쓰인다.

소수

• 소수
  • 1과 자기 자신으로만 나누어지는 수
  • 약수가 2개인 수
  • 2부터 N-1까지의 수로 나누어지지 않는 수
  • 합성수 N에서 1을 제외한 가장 작은 약수는 √N 이하이다. 따라서 2부터 N-1 까지가 아니라 √N 까지만 나눠도 소수임을 판단할 수 있다.
• 합성수
  • 1과 자기 자신을 제외한 다른 약수를 가지고 있는 수
• 1은 소수도 합성수도 아니다.

sqrt() 함수를 사용하면 안될까?

• sqrt()는 실수 연산을 하기 때문에 정수형 계산을 정확히 다루는 문제에서 조심해야 할 부분이 있다. 이유는 Double 타입을 반환하므로 소수점이 포함되어 실수 오차로 인해 정밀한 정수 계산이 필요할 때 문제가 발생할 수 있기 때문이다.
• 하지만 약수를 구할 때, 루트 값까지만 반복을 하면 계산을 줄일 수 있기 때문에, 우리가 원하는 정수 범위 내에서만 사용되므로 정밀도 문제는 크게 발생하지 않는다.
• 따라서 약수를 구하는 데 sqrt()를 사용하는 것은 유용하다.

에라토스테네스의 체

• 2부터 N까지의 소수를 구하는 방법. 특정 수의 배수들을 제거하는 방식으로 2부터 순차적으로 제거되지 않은 작은 수를 찾아 그 수의 배수들을 제거하여. 더 이상 제거할 수 없을 때까지 반복하면 남아있는 수들은 모두 소수.

func sieveOfEratosthenes(_ n: Int) -> [Int] {
    // 0부터 n까지의 값을 가진 배열을 true로 초기화 (소수인지 여부를 나타냄)
    var isPrime = [Bool](repeating: true, count: n + 1)
    isPrime[0] = false // 0은 소수가 아님
    isPrime[1] = false // 1도 소수가 아님

    // 2부터 sqrt(n)까지의 수들에 대해
    for i in 2...Int(Double(n).squareRoot()) {
        if isPrime[i] {
            // i의 배수들을 소수가 아니라고 표시
            for multiple in stride(from: i * i, through: n, by: i) {
                isPrime[multiple] = false
            }
        }
    }

    // 소수인 수들만 배열로 반환
    return (2...n).filter { isPrime[$0] }
}

let primes = sieveOfEratosthenes(50)
print(primes)

소인수분해

• 정수를 소수의 곱으로 나타내는 것을 의미한다. ex) 1100 = 2 2 5 5 11

import Foundation

func optimizedPrimeFactorization(_ n: Int) {
    var n = n

    // 먼저 2로 나누기
    while n % 2 == 0 {
        print(2)
        n /= 2
    }

    // 3부터는 홀수만 체크 (i += 2)
    var i = 3
    while i * i <= n {
        while n % i == 0 {
            print(i)
            n /= i
        }
        i += 2
    }

    // n이 1보다 크면 마지막 소수 출력
    if n > 1 {
        print(n)
    }
}

let n = Int(readLine()!)!
optimizedPrimeFactorization(n)

최대공약수(Greatest Common Divisor, GCD)

• 두 자연수의 공통된 약수 중 가장 큰 약수

유클리드 호제법

• 큰 수에서 작은 수를 반복적으로 나누는 방식으로 GCD를 구하는 방법
• 두 수 A와 B가 있을 때, 그 중 큰 수가 A라고 가정한다면 두 수의 최대공약수는 A % B와 B의 최대공약수와 동일하다.
• 즉 GCD(a, b) = GCD(b, a % b) 가 된다.
• 이 과정을 나머지가 0이 될 때 까지 반복하면 마지막에 나오는 값이 최대공약수가 된다.
• 반복 하는 과정을 재귀로 하면 간단한 코드로 구현할 수 있다.

func gcd(_ a: Int, _ b: Int) -> Int {
    return a == 0 ? b : gcd(b % a, a)
}

최소공배수(Lowest Common Multiple, LCM)

• 두 자연수의 공통 배수 중 가장 작은 수
• A * B = GCD(A, B) * LCM(A, B) 가 성립이 되기에 해당 코드로 구현할 수 있다.

func lcm(_ a: Int, _ b: Int) -> Int {
    return (a * b) / gcd(a, b)
}

// 오버플로우가 걱정된다면 해당 코드로 구현 가능
func lcm(_ a: Int, _ b: Int) -> Int {
        return a / gcd(a, b) * b
}

연립합동방정식

• 여러 개의 합동식(modulo 연산 식)으로 이루어진 방정식들을 동시에 만족하는 값을 구하는 문제
• 연립합동방정식이 간단할 때는 수동 탐색으로 푸는게 효과적이지만, 큰 값이거나 문제가 복잡해진다면 해당 문제를 풀기 위해선 가장 유명한 중 하나인 중국인의 나머지 정리이다.

중국인의 나머지 정리

• 서로 다른 모듈로에 대해 주어진 연립 합동 방정식이 해가 존재하고 유일한지를 알려주며, 이를 바탕으로 해를 구할 수 있다.
• 조건은 다음과 같다
  1. 모든 모듈로 값들이 서로소(공약수가 1인 관계)여야 한다.
  2. 위 조건이 만족되면, 연립 합동 방정식의 해는 유일하게 존재하며, 모듈로들의 곱에 대해 반복된다.

// 모듈로 역수를 구하는 함수
func modInverse(_ a: Int, _ m: Int) -> Int {
    var m0 = m
    var y = 0, x = 1

    if m == 1 {
        return 0
    }

    var a = a
    while a > 1 {
        let q = a / m
        var t = m

        m = a % m
        a = t
        t = y

        y = x - q * y
        x = t
    }

    if x < 0 {
        x += m0
    }

    return x
}

// 중국인의 나머지 정리 함수
func chineseRemainder(_ nums: [Int], _ rems: [Int]) -> Int {
    let prod = nums.reduce(1, *)
    var result = 0

    for i in 0..<nums.count {
        let pp = prod / nums[i]
        result += rems[i] * modInverse(pp, nums[i]) * pp
    }

    return result % prod
}

// 테스트 예시
let nums = [3, 5, 7]   // 모듈로들
let rems = [2, 3, 2]   // 나머지들

let result = chineseRemainder(nums, rems)
print("\(result)")

이항계수

• 주어진 두 자연수 n 과 k 에 대해, n개의 원소 중에서 k개의 원소를 선택하는 방법의 수를 나타내는 수 이다.
• 팩토리얼이나 재귀함수를 이용해 계산할 수 있다.

// 재귀적으로 이항계수 계산
func BCR(n: Int, k: Int) -> Int {
    if k == 0 || k == n { return 1 }
    return BCR(n: n - 1, k: k - 1) + BCR(n: n - 1, k: k)
}

// 예시
let resultRecursive = BCR(n: n, k: k)
print("C(\(n), \(k)) = \(resultRecursive)")  // 출력: C(5, 2) = 10

문제 풀이

백준 11051번: 이항 계수2

• 파스칼의 법칙에 따라 이항계수를 계산하는 점화식을 세우면 dp[i][j] = dp[i-1][j-1] + dp[i-1][j] 이기에 dp배열을 만들고 메모제이션 해주면 된다.

let I = readLine()!.split { $0 == " " }.map { Int($0)! }
let (N,K) = (I[0],I[1])
var dp = Array(repeating: Array(repeating: 0, count: N+1), count: N+1)

for i in 0...N {
    for j in 0...min(i,K) { // 불필요한 반복을 줄이기 위해 i,k중 작은값 까지 반복
        if j == 0 || j == i { dp[i][j] = 1 }
        else { dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % 10007 }
    }
}
print(dp[N][K])

[qwerty3345]

수학 알고리즘

1. 소수 (Prime Numbers)

1.1 소수의 정의

• 1과 자기 자신으로만 나누어지는 수
• 약수가 2개인 수
• 1은 소수가 아님

1.2 소수 판정 알고리즘

• 기본 방법: O(N)
• 최적화 방법: O(√N)
  • 합성수 N의 1을 제외한 가장 작은 약수는 √N 이하
  • 2부터 √N까지만 나누어 보면 됨

1.3 에라토스테네스의 체

• 1부터 N까지의 소수를 모두 찾는 효율적인 방법
• 시간복잡도: O(N log log N)
• 구현 시 vector을 사용하면 메모리와 속도 면에서 유리

2. 최대공약수 (GCD)와 최소공배수 (LCM)

2.1 약수

• 약수 구하기: O(√N)에 가능

2.2 최대공약수 (GCD)

• 유클리드 호제법 사용
• GCD(A, B) = GCD(B, A % B)
• 시간복잡도: O(log(max(a,b)))

2.3 최소공배수 (LCM)

• LCM(A, B) = A * B / GCD(A, B)
• 오버플로우 주의: (A / GCD(A, B)) * B 형태로 계산

3. 연립합동방정식

3.1 개념

• 여러 개의 나머지 조건을 동시에 만족하는 수 찾기

3.2 해결 방법

• 브루트포스: O(NM) - 비효율적
• 최적화: O(N) 또는 O(M) - 하나의 조건을 기준으로 후보 축소

3.3 중국인의 나머지 정리 (CRT)

• 대회 수준의 고급 기법, 로그 시간에 해결 가능

4. 이항계수

4.1 정의

• nCk: n개 중 k개를 선택하는 조합의 수

4.2 계산 방법

• 기본 공식: nCk = n! / (k! * (n-k)!)
• 재귀적 성질: nCk = (n-1)C(k-1) + (n-1)Ck

4.3 큰 수의 이항계수 계산

• DP를 이용한 방법: d[i][j] = iCj = d[i-1][j-1] + d[i-1][j]
• 모듈러 연산 주의

주의사항

• 실수 연산 대신 정수 연산 사용 (예: sqrt 함수 대신 i*i <= n 사용)
• 오버플로우 주의
• 테스트 케이스의 범위 확인 중요

팁

• 수학 문제는 코딩테스트에서 비중이 낮을 수 있으나, 대비 필요
• 지엽적인 테크닉보다는 기본적인 개념과 구현에 집중
• 연습 문제를 통해 다양한 유형 학습 권장

BOJ 6064 카잉 달력

import Foundation

let inputNum = Int(readLine()!)!

func solution(M: Int, N: Int, x: Int, y: Int) -> Int {
    let lcm = lcm(M, N)
    var year = x

    while year <= lcm {
        if (year - 1) % N + 1 == y {
            return year
        }
        year += M
    }
    return -1
}

func gcd(_ a: Int, _ b: Int) -> Int {
    return b == 0 ? a : gcd(b, a % b)
}

func lcm(_ a: Int, _ b: Int) -> Int {
    return a / gcd(a, b) * b
}

let result: [Int] = (0..<inputNum).map { _ in
    let input = readLine()!.components(separatedBy: " ").compactMap { Int($0) }
    return solution(M: input[0], N: input[1], x: input[2], y: input[3])
}
result.forEach {
    print($0)
}

[shippingpark]

소수판정법에서의 Tip

루트 N 범위를 잡을 때 루트 연산자를 쓰면 실수 연산자라 오차가 발생할 수 있음 for 문의 조건에서 i*i<=N 이라고 두면 됌

소인수분해 문제 풀이

import Foundation

var n = Int(readLine()!)!
var i = 3

func division() {
  guard n > 1 else { return }
  while n%2 == 0 {
    print("2")
    n /= 2
  }

  while i*i<=n {
    if n%i==0 {
      print(i)
      n /= i
    } else {
      i += 2
    }
  }

  if n > 1 {
    print(n)
  }
}

division()

수학 문제는 많이 나오지 않지만, 기본 개념을 숙지할 것

소수:

소수는 1과 자기 자신으로만 나누어지는 수이다. 합성수에서 1을 제외한 가장 작은 약수는 √N 이하이므로, 소수를 구할 때 N-1까지 나누지 않고 √N까지만 나누어도 소수인지 판단할 수 있다.

에라토스테네스의 체:

2부터 N까지의 소수를 구하는 알고리즘으로, 배수를 제거하는 방식이다. 소수를 빠르게 구할 수 있는 방법으로 사용된다.

소인수분해:

정수를 소수의 곱으로 나타내는 것을 의미한다. 예를 들어, 1100 = 2 2 5 5 11로 표현된다.

최대공약수(GCD):

두 자연수의 공통된 약수 중 가장 큰 약수로, 유클리드 호제법을 사용하여 구할 수 있다.

최소공배수(LCM):

두 자연수의 공통 배수 중 가장 작은 수로, GCD를 이용하여 LCM을 구할 수 있다.

연립합동방정식:

여러 개의 합동식을 동시에 만족하는 값을 구하는 문제이다. 중국인의 나머지 정리를 통해 해를 구할 수 있으며, 모듈로 값들이 서로소일 때 유용하다.

이항계수:

n개의 원소 중 k개의 원소를 선택하는 방법의 수를 나타낸다. 이항계수는 재귀 함수나 파스칼의 법칙을 이용해 계산할 수 있다.