[백준/파이썬] 17427 : 약수의 합 2
https://www.acmicpc.net/problem/17427 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 문제 요약 : 자연수 A의 약수의 합은 f(A)이다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)이다. 자연수 N이 주어졌을 때, g(N)을 구하라. 시도 ) # 약수의 합2 import sys input = sys.stdin.readline ans = 0 for number in range(1,int(input(..
2023. 3. 27.
[자료구조/Python] 세그먼트 트리(Segment Tree)
세그먼트 트리(Segment Tree) 구간 합, 최소값, 최대값 등의 쿼리를 빠르게 처리하기 위해 사용되는 자료구조 이진 트리(binary tree)를 기반으로 하며, 각 노드는 해당 구간의 합, 최소값, 최대값 등의 값을 저장한다. 1. 구성 기본 배열을 이용하여 세그먼트 트리를 초기화, 배열의 각 요소가 세그먼트 트리의 각 리프 노드에 대응된다. 이진 트리의 성질을 이용하여, 각 노드가 나타내는 구간을 두 개의 서브트리로 나눈다. 각 노드에 대해, 해당 구간의 합, 최소값, 최대값 등의 값을 계산하여 저장한다. 각 쿼리에 대해, 세그먼트 트리를 탐색하여 필요한 값을 계산한다. 리프 노드 : 배열의 그 수 자체 다른 노드 : 왼쪽 자식과 오른쪽 자식의 합을 저장 2. 시간 복잡도 트리의 높이가 log..
2023. 3. 24.
