AutoLoan

문제

매월 이자가 잔액에 추가됩니다

이자가 추가된 후 지불액이 차감됩니다

연 이율의 1/12 가 월 이율이 됩니다

대출의 price, monthlyPayment, loanTerm 이 주어질 때

대출의 연 이율을 리턴합니다.

예시 입력

1)
6800, 100, 68

2)
2000, 510, 4

3)
15000, 364, 48

예시 출력

1)
4.76837e-05

2)
9.56262

3)
7.68788

생각의 변화

계산해보면 이렇게 된다

2번 예시
연 이율 9.56%
월 이율 9.56 / 12 = 0.79%

납부    이자+   지불-    잔액
                       2000
 1     15.94   510     1505.94
 2     12.00   510     1007.94
 3     8.03    510     505.97
 4     4.03    510     0

지불 금액에서 이자의 비율은 점점 줄어들 것이다 (잔액이 줄어들고 있으니까)

연리 100% 에서 시작

잔고가 + 면
월리 -= 월리 half

잔고가 - 면
월리 += 월리 half

이분 탐색을 할때 매끄럽게 balance 가 0이 되진 않을것 같은데

abs(balance) 로 1e-n 체크

이분탐색 시에는 low mid high 를 꼭 사용해야 한다
단순히 절반한 값을 + 하거나 - 하는 경우는
이전 탐색 결과를 무시할수 있다

high-low 로 1e-9 체크

예시

0.6 정답

1 : 크다       1 - 1/2 : 0.5
0.5 : 작다     0.5 + 0.5/2 : 0.75
0.75 : 크다    0.75 - 0.75/2 : 0.375
0.375.. 

0.5 보다 더 작은 곳으로 이동하였다

pseudo code

interestRate(price, monthlyPayment, loanTerm)
    low = 0, mid = 0, high = 1
    
    annual_rate
    
    while high-low > 1e-9
        mid = (low + high) / 2

        annual_rate = mid
        monthly_rate = annual_rate / 12
        
        balance = price
        
        for (i=0  i<loanTerm  i++)
            balance += balance * monthly_rate
            balance -= monthlyPayment
            
        if (balance > 0)
            high = mid
        else
            low = mid
            
    return annual_rate * 100 

절대오차와 상대오차에 대해

high-low > 1e-9 는 절대오차이고
(high-low)/high > 1e-9 는 상대오차이다

현 문제에서는 절대오차만 봐도 괜찮다. 값이 0에 가까운, 작은 값이기 때문이다

하지만, double 의 유효숫자는 제한적이여서, 너무 큰수를 사용할 경우

low 1경, high 1경+2 일때

mid = (1경 + 1경+2) / 2 = 1경+1 이여야 하지만, 
해상도 문제로 1경 또는 1경+2 가 되어버린다

따라서 둘의 차이는 좁혀지지 않고, 무한루프에 빠질 위험이 있다

그래서 등장한 것이 상대오차이다

relative error = |a-b| / max(|a|, |b|)