정수론4 [알고리즘] 고오급 알고리즘 키워드 *블로그 주인만 알아볼 수 있음 주의* 삼진탐색으로 최솟값 찾기 함수의 최솟값이 x구간 [a,d] 구간 안에 있다고 하자. 구간을 같은 길이 [a,b], [b,c], [c,d]로 나누고 f(b)>f(c)가 성립함을 보인다. (미분) 합 최소화 abs(a1-x)+abs(a2-x)+ ... +abs(an-x) 의 최솟값으로 만드는 x의 최적해는 중앙값이다. 배열 원소가 짝수개라면 두 중앙값 사이 모든 값이 최적해가 된다. 트리의 지름 임의의 노드 a 선택, a에서 가장 먼 노드 b, b에서 가장 먼 노드 c를 구하면 b-c가 트리의 지름 트리 k번째 조상 찾기 ancestor(n,k) : n번 노드의 k번째 부모 가장 쉬운 방법은 k번 거슬러 올라가는 것인데 비효율적이다. k가 2의 거듭제곱인 모든 경우에 .. 2023. 6. 1. [알고리즘] 분할정복으로 거듭제곱 최적화하기 프로그래밍에서 거듭제곱을 구하는 방법은 크게 세 가지이다. pow 내장함수 사용하기 double 실수 자료형을 사용해 거듭제곱을 반환하는 방법이다. 하지만 지수가 매우 클 때 정확성의 문제가 발생한다. 그 문제는 아래 글에서 확인 가능하다. C++ 기준 pow에 관한 글이다. 2023.04.30 - [TIL] - [C++] pow함수 double 형의 정확성 문제 [C++] pow함수 double 형의 정확성 문제 https://www.acmicpc.net/problem/1740 1740번: 거듭제곱 3의 제곱수를 생각하자. 3의 0제곱, 3의 1제곱, 3의 2제곱, ... 은 순서대로 1, 3, 9, 27, ... 이 된다. 이를 바탕으로, 한 개 이상의 서로 다른 3의 제곱수의 oozoowos.tis.. 2023. 5. 30. [정수론] 모듈러 연산과 증명 주의) 나눗셈 연산에서는 성립하지 않는다. 2023. 5. 29. [정수론] 페르마의 소정리 (모듈러 연산) 2023. 5. 26. 이전 1 다음
