[Do it! 알고리즘 코딩 테스트 자바편] 알고리즘 공부 (01)

1. 시간복잡도

코딩테스트에는 시간 복잡도라는 내용이 있다.

시간 복잡도란 연산 횟수를 표기하는 방법을 의미한다.

 

시간복잡도의 유형에는

1. 빅 오메가 : 최선일 때의 연산 횟수를 나타낸 표기법

2. 빅 세타 : 보통일 때의 연산 횟수를 나타낸 표기법

3. 빅 오 : 최악일 때의 연산 횟수를 나타낸 표기법

들이 있다. 

 

코딩테스트에서는 빅 오 표기법을 활용하여 연산 횟수(수행시간) 을 계산한다.

 

 

2. 시간 복잡도 계산하기

기본적으로 코딩테스트 문제에는 수행 시간이 주어진다.

1초에 1억번의 연산이 기준이기 때문에 2초가 주어진 경우,

시간 내에 2억번의 연산이 가능하도록 코드를 작성해야 한다.

 

문제에서 n의 범위가 1 <= n <= 10000 이 주어졌다.

그러면 1차 반복문으로 n을 탐색했을 때, 우리는 빅 오 표기법을 사용하기 때문에 경우의 수는 n번 즉, O(n) 이다. (여기서는 10^4)

2차 반복문으로 탐색했을 때에는 n*n 으로 O(n^2) 으로 표현하며 10^8의 번의 연산을 수행한다. 

 

그렇다면 문제에서 주어진 수행 시간이 0.5초 인경우 2차 반복문은 사용하면 시간초과 오류가 나오게 된다.

(최선의 상황에서는 시간초과가 나지 않겠지만)

 

이렇듯 주어진 변수의 범위와 시간복잡도를 활용하면 문제에서 어떤 알고리즘을 사용해야할지에 대한 힌트를 조금은 얻을 수 있다.

 

 

 

3. 시간복잡도 도출 기준

시간 복잡도의 도출 기준은

1. 상수는 계산에서 제외한다.

-> 1차 반복문이 2개여서 2n 일 경우 그냥 O(n) 으로 표시한다.

 

2. 가장 차수가 높은(가장 중첩이 많이 된) 반복문이 시간 복잡도의 기준이 된다. 

-> 2차 반복문이 2개, 1차 반복문이 1개로 2*n^2 +n 일 경우 가장 차수가 높은 반복문은 2차 반복문이며, 상수는 취급하지 않으므로 O(n^2) 으로 표기할 수 있다. 

 

 

4. 디버깅

디버깅이란 프로그램에서 발생하는 문법적이 오류나 논리적인 오류를 찾아서 바로잡는 과정을 의미한다.

이를 사용하는 방법은 IDE 에서 중단점을 설정하고, 이 중단점을 기준으로 변수를 추적하여 어느 부분에서 오류가 발생했는 지를 알 수 있다.

 

디버깅 예시 사진

 

위의 사진에서 보라색으로 표시되는 줄이 중단점으로 설정한 지점이다.

이렇게 중단점을 지정하고 (중단점으로 잡고싶은 Line 숫자쪽을 클릭하면 중단점으로 지정할 수 있다.) 

디버깅을 누르면 아래처럼 현재 저장된 변수들의 값을 확인할 수 있다. 

 

이 기능을 통해서 코딩테스트중에 방대한 양의 변수 중에서 어떤 변수에 값이 제대로 들어가지 않았는 지 확인할 수 있다.