💡문제 분석 요약
- 자연수 A의 약수의 합은 f(A)이다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)이다. 자연수 N이 주어졌을 때, g(N)을 구해야한다.
- 1부터 N까지 각 숫자에 대하여 그 숫자의 모든 약수들의 합을 구해야 한다.
- n 의 상한(0 < n < 1,000,000)이 크기 때문에 시간 및 공간 복잡도 모두 최적화하는 것이 필요하다.
💡알고리즘 설계
약수합을 최적으로 구하는 알고리즘이 필요하다.
- 에라토스테네스의 체와 비슷한 방법을 사용하여, 각 숫자의 약수들의 합을 효율적으로 계산한다.
- 1부터 N까지 각 숫자에 대하여 그 숫자의 모든 약수들의 합을 구하고, 이를 배열에 저장한다.
- 배열에 저장된 약수들의 합을 모두 더하여 g(N)을 구한다.
*에라토스테네스의 체 는 소수를 구하는 가장 오래되고 대표적인 알고리즘 이다.
💡코드
fun main() {
val br = System.`in`.bufferedReader()
val N = br.readLine().toInt()
val g = LongArray(N + 1) { 1L } // 모든 숫자는 자기 자신을 약수로 갖기 때문에 1로 초기화
// 에라토스테네스의 체 비슷한 방법으로 각 숫자의 약수들의 합 계산
for (i in 2..N) {
var j = i
while (j <= N) {
g[j] += i.toLong()
j += i
}
}
// 누적합 계산
for (i in 2..N) {
g[i] += g[i - 1]
}
println(g[N])
}
💡시간복잡도
알고리즘의 시간 복잡도는 O(N log N)이다. 각 숫자의 약수를 찾는 과정에서 모든 약수들을 찾기 때문에, N까지의 모든 숫자에 대해 약수들의 합을 계산하는 과정이 N log N 번의 연산을 수행하기 때문이다..
💡 틀린 이유
이번 문제는 수학을 풀이하는 문제였는데, 약수의 합을 구하는 알고리즘을 내가 작성하지 못했다. 다양한 수학적인 부분을 알고리즘으로 구현하는 연습이 필요할 것 같다.
💡 다른 풀이
풀이는 크게 현재 작성한 풀이와, 또 다른 풀이가 존재했다. 직접 많은 숫자를 확인하며 찾은 규칙을 활용한 것인데, 해당 방법이 복잡도 측면에서 훨씬 큰 이점이 있는 방법이었다.(O(N))
10을 기준으로 한다면,
1 은 총 10번 등장하고 ((10 / 1) * 1),
2 는 총 5번 등장하고 ((10 / 2) * 2),
3 은 총 3번 등장하고 ((10 / 3) * 3),
4, 5 는 총 2번 등장하고 ((n (10) / i ( 4 ~ 5 )) * i ( 4 ~ 5 )),
6, 7, 8, 9, 10 은 총 1번 등장한다 ((n (10) / i ( 6 ~ 10 )) * i ( 6 ~ 10 ))
이를 수식으로 정리하면, n / i ) * i 가 되며, 이를 활용한 방법이다.
import java.io.BufferedReader
import java.io.InputStreamReader
fun main() = with(BufferedReader(InputStreamReader(System.`in`))) {
val n = readLine().toInt()
var answer = 0L
for (i in 1..n) {
answer += (n / i) * i
}
println(answer)
}
💡 느낀점 or 기억할정보
현재 다양한 문제유형을 풀이를해보고 있는데, 다방면으로 많이 부족함을 느끼고 있다. 그리디 문제를 풀이할 땐, 코딩 피지컬의 부족함을 느꼈는데, 이번 수학과 관련해서도 코딩 피지컬의 부족으로 인한 문제 + 수학 공식의 부족을 인지할 수 있었다.
수학 공식의 경우, 다방면으로 활용이 될 수 있으므로, 카테고리화 하여 정리해놓고, 복습하며 다른 알고리즘 문제를 풀이할 때 응용할 수 있도록 해야겠다.
- 알고리즘 별 카테고리화 정리 진행
'개인공부 > 알고리즘' 카테고리의 다른 글
[ 탐색 ] 백준 13549 숨박꼭질 3 (0) | 2024.03.25 |
---|---|
[ 수학 ] 백준 2609 최대공약수와 최소공배수, Kotlin, 유클리드 알고리즘 (0) | 2024.03.16 |
[ DP ] 백준 15988번 1, 2, 3 더하기 3, Kotlin (0) | 2024.03.14 |
[ 그리디 ] 백준 1783 병든 나이트 (0) | 2024.03.07 |
프로그래머스 - 그룹별 조건에 맞는 식당 목록 출력하기 (SQL) (0) | 2023.08.20 |