(전공복습) 데이터과학 4. 시각화
차례
백준(BOJ) 11692 시그마 함수 파이썬(Python)
답이 심플한 정수론 문제.
시그마 n이 짝수이기 위한 조건은, 다시 말해 약수 중 홀수의 개수가 홀수인 것이다.
여러 수들의 합이 짝수이려면 그 중 홀수가 짝수 번 등장해야 하기 때문이다(홀+홀=짝, 홀+짝=홀, 짝+짝=짝 이므로).
이는, n의 홀수 소인수(2를 제외한 소인수)들의 지수+1의 곱이 짝수여야 한다는 것을 의미한다.
예를 들어, n = 63 = 3**2 * 7**1이라고 해보자. 그렇다면 나올 수 있는 홀수 약수는 1, 3, 7, 9, 21, 63일 것이다.
경우의 수를 이야기하자면, 3이 0개, 1개, 2개인 경우와 7이 0개, 1개인 경우를 곱한 것이다.
즉 (2 + 1) * (1 + 1)=6이다.
그렇다면 시그마 n이 짝수가 아니라 홀수인 조건은 무엇일까?
바로 2를 제외한 소인수들의 지수가 모두 짝수인 경우일 것이다(적어도 하나의 홀수를 가지는 것의 반대이므로).
소인수들의 지수가 모두 짝수인 수를 우리는 완전제곱수라고 한다.
m에 루트를 씌우면, sqrt(m)을 구할 수 있다.
예를 들어, m=9라면 sqrt(m) = 3이 된다.
즉, m 이하의 완전제곱수는 1, 4, 9로 3개라는 것을 알 수 있다.
m=10**12라면? sqrt(m) = 10**6이므로 1000000개의 완전제곱수가 존재함을 알 수 있다.
이제, 완전제곱수인 경우(코드에서는 x_1이라 칭함)는 모두 구했다.
그런데, 우리가 당초 구하고자 하는 수는 m개의 수 중 2를 제외한 소인수들의 지수가 짝수인 수들이었다.
즉, 인수 중 2는 지수가 짝수이든 홀수이든 상관이 없다는 뜻이고, 짝수인 경우는 완전제곱수에 포함되어 있으므로 홀수인 경우를 구해야 한다.
이 경우 그러한 수 k_2는 임의의 완전제곱수 k_1에 대해 k_2 = k_1 * 2로 나타낼 수 있다.
왜냐하면 2의 지수가 홀수인 경우는 결국 2의 지수가 짝수인 경우에 2를 곱한 것이기 때문이다.
따라서, 이 경우의 수는 x_2 = sqrt(m//2)이다. 2로 나눈 후에 완전제곱수인 수이기 때문이다.
이제 우리는 시그마 n이 홀수인 경우를 모두 구했다.
m까지의 모든 수에서 시그마 n이 홀수인 경우를 빼면 짝수인 경우만 남으므로 그게 답이다.
#!python
from math import sqrt
m = int(input())
# x_1 : m 이하의 완전제곱수의 개수
x_1 = int(sqrt(m))
# x_2 : m 이하의 완전제곱수 * 2 꼴인 수의 개수
x_2 = int(sqrt(m//2))
# 전체 m개의 수에서 이 두 가지 경우(시그마 n이 홀수인 경우)를 빼면 된다
print(m - x_1 - x_2)
2024
맨 위로 이동 ↑2023
백준(BOJ) 2045 마방진 / 3192 매직 스퀘어 파이썬(Python)
문제 링크 문제 링크
세그먼트 트리
개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...
벨만-포드 알고리즘
개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...
다익스트라 알고리즘
개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...