[수학적 처리] 증명된 수식을 로직으로

알고리즘을 성능 최적화하기 위해서는 수학적으로 증명된 기능을 사용하는 것이다.
아래는 증명된 수식을 어떻게 로직을 구현하는지 정리한 내용이다.
계속 추가될 예정이다.

소수점 올림(ceil)

ceil(X/Y) -> (X + Y - 1) / Y
ex)
ceil(60/30) -> (60 + 30 -1) / 30 = 89 / 30 = 2

소수점 내림(floor)

• 나누기 자체가 내림 수

  foor(X/Y) -> X / Y
  ex)
  floor(69/30) -> 69 / 30 = 2

  소수점 반올림(round)

• 나누려고 하는 값의 절반을 올려줌으로 0.5 이상이면 반올림 효과 발생

  round(X/Y) -> (X + Y/2) / Y
  ex)
  round(7/2) -> (7 + 2/2) / 2 = 8 / 2 = 4
  round(7/3) -> (7 + 3/2) / 3 = 8 / 3 = 2.333(일반 나누기는 버림) = 2(몫)

평균 최소값

• 길이 4 이상은 길이가 2,3의 평균값보다 작을 수 없다.
• 즉, 길이 2, 3만 체크하면 됨

  double minAvg = Double.MAX_VALUE; // 평균최소
  int minPos = 0; // 최소가되는 시작지점
  

// 평균이 가장 낮은거 반환
// 길이 4이상은 평균이 작지 않다는 걸 이용
// 길이 2, 3만 체크
// 전체 길이에서 i + 1 < N 만 체크 함 길이 2가 되는 조건
for(int i = 0; i < N -1; i++){
// 기본 길이 2의 조건
double avg2 = (A[i] + A[i+1]) /2.0;
if(avg2 < minAvg ){
minAvg = avg2;
minPos = i;
}

// i 기준에서 길이 3개 가능여부    
if(i < N -2){
    double avg3 = (A[i] + A[i+1] + A[i+2])/ 3.0;
    if(avg3 < minAvg){
        minAvg = avg3;
        minPos = i;
    }
}

}

## 범위(A~B)내의 K가 나누어 떨어지는 수의 개수
```java

// Brute Force
// O(B-A) 범위가 커질 수록 성능 저하 발생
int count= 0;
for(int i = A; i <= B; i++){
    if(i % K == 0) count++;
}

B / K - (A - 1) / K

??? 뭔가 싶다… K의 범위별 배수 개수를 구하고 최대에서 최소 빼주면 된다… 간단…

• B / K는 0 ~ B까지의 K의 배수
• (A - 1) / K 는 0 ~ A 까지의 K의 배수 개수
• 둘을 빼면 A ~ B 구간의 K 배수 개수 나옴

배열의 가장 큰 수

곱하기

• 정렬을 이용해서 가장 큰 수를 순서대로 곱하면 됨
• 음수 범위이면서 음수를 2개 곱할 수 있는 케이스 추가 최소값 2개 * 가장 큰수

소수(prime number)

1,2,3,5,7,11,13,…,N

약수(Divisor)

12의 약수는 1,2,3,4,6,12

약수는 a = 2, 약수 n = 12 일 때,
n/a = 12/2 = 6도 약수다
a, n/a는 는 반드시 √n 이하이다.

약수 구할 때

while( i * i < n) // 이렇게 줄일 수 있다.