[449] 완전수 쉽게 배우기
1. 완전수란 무엇일까?완전수는 자신을 제외한 모든 약수의 합이 자기 자신과 같은 수를 말해.먼저, 진약수라는 개념을 알아보자.진약수는 자기 자신을 제외한 약수를 뜻해.예를 들어, 숫자 6의 약수는 1, 2, 3, 6인데, 이 중 6을 뺀 1, 2, 3이 바로 6의 진약수야.진약수의 합에 따라 숫자는 세 가지로 나눌 수 있어. 완전수: 진약수의 합이 자기 자신과 같은 수예: 6의 진약수는 1, 2, 3이고, 이걸 더하면 6이 돼. 그래서 6은 완전수야! 부족수: 진약수의 합이 자기 자신보다 작은 수예: 8의 진약수는 1, 2, 4이고, 이걸 더하면 7이야. 7은 8보다 작으니까, 8은 부족수야. 과잉수: 진약수의 합이 자기 자신보다 큰 수예: 12의 진약수는 1, 2, 3, 4, 6이고, 이걸 더하면 1..
[446] 느리게 갱신되는 세그먼트 트리(lazy propagation)
1. 세그먼트 트리 동작 과정세그먼트 트리는 루트 노드에서 리프 노드까지 범위를 나누어 가며 통일된 연산값을 유지해야 합니다.따라서 자식 노드에서 부모 노드로 올라가더라도 더 넓어진 범위에 대해 연산 결과를 유지할 수 있어야합니다.이게 가능한 연산은 최대, 최소, 덧셈, 곱셈 등 일부의 결과로 전체 범위에 적용이 가능한 연산을 세그먼트 트리에 적용할 수 있습니다. 8 크기의 배열에서 3, 2, 5, 3, 5, 2, 3, 4의 값을 가지고 있고, 구간합을 관리하는 세그먼트 트리는 다음과 같습니다. 이 세그먼트 트리에서 2 ~ 8 범위의 구간합을 구하고 싶다면 다음과 같이 구합니다. 찾고자 하는 범위 안에 포함될 때까지 자식으로 내려가며 합을 구하면, 2+8+14로 24라는 것을 알 수 있습니다.다음으로 세..
