수학

문제: 귀찮아 (SIB) (백준 14929번)문제 분석주어진 n개의 정수에 대해, 모든 서로 다른 두 수의 곱의 합을 구하는 문제이다.즉,$\text{result} = \sum_{1 \leq i 직접 모든 쌍을 계산하면 O(n²) 시간 복잡도가 발생하지만, n의 범위가 클 경우 시간 초과가 날 수 있다.해결 방법수학적 아이디어:두 수의 곱의 합은 다음 식으로 변형할 수 있다.$\left(\sum_{i=1}^{n} a_i\right)^2 = \sum_{i=1}^{n} a_i^2 + 2\sum_{1 \leq i 따라서,$\sum_{1 \leq i 이 식을 이용하면 O(n) 시간 내에 결과를 구할 수 있다.전체 코드#include using namespace std;int main() { ios::syn..

문제 링크 (백준 1004번)문제 분석어린 왕자가 출발점에서 도착점까지 이동하면서 거쳐야 하는 최소한의 행성계 진입/이탈 횟수를 구하는 문제다.행성계는 원으로 표현되며, 출발점과 도착점, 그리고 행성계의 중심과 반지름이 주어진다.문제의 조건에 따라 행성계 경계는 서로 교차하거나 맞닿지 않고, 출발점과 도착점이 경계에 걸쳐지는 경우도 없다.문제 로직행성계 내부 판정두 점 사이의 거리를 계산해서 해당 점이 행성계 내부에 있는지 확인진입/이탈 횟수 계산출발점과 도착점이 특정 행성계 내부/외부에 속하는 관계가 다를 때만 진입/이탈 횟수를 증가시킨다.이 과정을 통해 최소 진입/이탈 횟수를 구한다.전체 흐름각 테스트 케이스마다 모든 행성계를 검사하면서 위 조건을 만족하는 경우를 카운트한다.거리 계산float Dis..

문제: 행렬 제곱(백준 10830번)문제 분석$N\times N$ 크기의 행렬을 $B$번 제곱한 결과를 출력하는 문제이다.보통 이런 지문 자체가 간단한 문제들은 입력 범위가 특정 알고리즘을 사용해야 시간 초과가 나지 않도록 설계되어 있다. 이번 문제 역시 단순히 행렬 제곱을 반복적으로 계산하면 $O(N^3\times B)$의 시간 복잡도를 가지므로 1000억 번의 연산이 필요하다. 따라서 시간 복잡도를 $O(\log B\times N^3)$ 수준으로 줄일 수 있는 알고리즘이 필요하다.거듭 제곱을 이용한 행렬 제곱 알고리즘거듭 제곱을 활용하면, 행렬을 효율적으로 제곱할 수 있다.행렬 $M$을 $B$번 제곱하는 과정을 다음과 같이 분할 정복 방식으로 처리한다.$B=0$일 경우, 단위 행렬을 반환한다..