(전공복습) 데이터과학 4. 시각화
차례
에라토스테네스의 체를 응용한 문제.
사실 더 효율적으로 풀 수 있는 것 같은데 오랜만의 문제풀이라 그런지 좀 비효율적으로 풀었다.
최소값이 최대 1_000_000_000_000
이라는 게 힌트. 저 수에 루트를 씌우면 1_000_000
이다.
즉, 최대 저 범위의 수에 대해서 제곱수를 구하고 그 제곱수의 배수를 에라토스테네스의 체로 쳐내면 된다.
체로 쳐내야 하는 범위는 최소값부터 최대값이므로 1_000_001
개를 넘지 않는다.
from math import sqrt, ceil
mini, maxi = map(int, input().split())
m = int(sqrt(maxi))
n = maxi - mini + 1
arr_base = [True for _ in range(m + 1)]
arr_area = [True for _ in range(n)]
# arr_base는 제곱수를 구할 범위
# arr_area는 최소값부터 최대값의 숫자들
for i in range(2, m + 1):
if not arr_base[i]: # 체에 쳐진 숫자면 넘어간다
continue
k = i ** 2
# arr_base, 즉 제곱수를 구할 범위에서 중복 계산을 피하기 위해 걸러낸다
for j in range(m // k):
arr_base[k * j] = False
# arr_area, 즉 실제 답안의 범위에서 제곱수의 배수를 걸러낸다
for j in range(ceil(mini / k), maxi // k + 1):
arr_area[k * j - mini] = False
# True의 개수가 제곱ㄴㄴ수의 개수
print(sum(arr_area))
문제 링크 문제 링크
개요 선형적인 자료구조에서는 값에 접근하는 데에 \(O(1)\)이면 충분하지만, 대신 부분합을 구하는 데에는 \(O(N)\)이 필요하다. 그렇다면 이 자료구조를 이진 트리로 구성하면 어떨까? 값에 접근하는 데에 걸리는 시간이 \(O(\lg N)\)으로 늘어나지만 대신 부분합을 구하...
개요 다익스트라 알고리즘과 함께 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 다익스트라 알고리즘보다 느리지만, 음수 가중치 간선이 있어도 작동하며, 음수 가중치 사...
개요 다익스트라 알고리즘은 Single Sourse Shortest Path(SSSP) 문제를 푸는 알고리즘 중 하나이다. 즉, 한 노드에서 다른 모든 노드로 가는 최단 경로를 구하는 알고리즘이다. 단, 다익스트라 알고리즘은 음수 가중치 엣지를 허용하지 않는다. 이 경우에는 벨만-...