Lesson3. TimeComplexity(시간 복잡성)

 시간 복잡성을 사용하면 지금 실행하는 프로그램의 실행시간을 추정가능하게 할 수 있습니다. 컴파일러와 컴퓨터의 종류 또는 프로세서의 속도에 따라 다르므로 정확한 추정은 힘들지만, 대략적인 속도는 추정이 가능하다. 추정시간은 Big-O 표기법을 사용하여 알 수 있다.

O(1) : 입력된 데이터의 크기에 상관없이 일정한 시간이 걸린다.   
O(N) : 입력된 데이터의 크기에 비례해서 시간이 상승한다.   
O(N<sup>2</sup>) : 입력된 데이트 크기에 따라 시간은 제곱에 비례한다.   
O(logN) : O(N<sup>2</sup>)과는 반대로 시간에 비례하여 처리할 수 있는 데이터의 크기가 늘어난다.

1. 문제

개구리가 출발지점(X)에 있고, 도착지점(Y)까지 걸리는 점프횟수를 구하는 문제이다.(한번의 점프거리는 D이다.)

2. 정답

첫번째 - 100점

int solution(int X, int Y, int D) {
    Y -= X;
    return Y%D ? Y/D+1 : Y/D;
}

개구리가 건너야하는 강의 거리를 확인하기 위해 도착지점에서 출발지점을 빼주었다.
Y-= X;

강의 거리를 개구리의 점프거리만큼 나눠주어 총 몇번의 점프를 해야하는지 확인하였다.

예시    
X = 10,  Y = 85, D =30 일 때,   
강의 거리는 85 - 10 = 75이다.   
점프 횟수는 75 / 30 = 2 나머지 15 이다.   
나머지가 0보다 크므로 점프 횟수를 1 더해준다.   
총 점프 횟수는 3이 된다.