Coding Test Java

알고리즘 코딩 테스트 1일차

seonggu 2023. 3. 21. 23:35

01-1 시간 복잡도 표기법 알아보기

일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다.

시간 복잡도 유형

  • 빅-오메가($\Omega$(n)) : 최선일 때 (best case)의 연산 횟수를 나타낸 표기법
  • 빅-세타($\Theta$(n)) : 보통일 때(average case)의 연산 횟수를 나타낸 표기법
  • 빅-오(O(n)) : 최악일 때(worst case)의 연산 횟수를 나타낸 표기법
  •  

코딩 테스트에서는 어떤 시간 복잡도 유형을 사용할까?

코딩 테스트에서는 빅-오 표기법(O(n))을 기준으로 수행하는 시간을 계산하는 것이 좋다.

빅-오 표기법(O(n))으로 표현한 시간 복잡도 그래프이다. 각각의 시간 복잡도는 데이터 크기(N)의 증가에 따라 성능(수행 시간)이 다르다는 것을 확인할 수 있다.

 

 

기울기가 가파를수록 성능이 좋지 않다. →

O(1), O(logN), O(N), O(NlogN), O(N^2), O(N^3),..., O(2^N), O(N!)

모두 어떤 동작을 수행할 때 최악의 경우 걸리는 시간을 의미한다.

왼쪽으로 갈수록 좋은 알고리즘이고, 오른쪽으로 갈수록 안 좋은 알고리즘이다. 보통 NlogN까지를 괜찮다고 생각하고, N^2부터는 안 좋다고 생각한다.

최악의 경우를 뜻하기 때문에 최선의 경우는 O(1)도 나올 수 있다.

즉 O(N^2)은 O(1)부터 O(NlogN)까지를 모두 포함하고 있다.

 

 

01-2 시간 복잡도 활용하기

수 정렬하기

📌 버블 정렬과 병합 정렬의 시간 복잡도를 각각 O(n^2), O(nlogn)이라고 알고 있다고 가정

문제 : N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오.

제한시간 2초 : 2억(200,000,000)번 이하의 연산 횟수로 문제를 해결해야함.

 

 

연산 횟수 계산 방법

  • 연산 횟수 = 알고리즘 시간 복잡도 * 데이터의 크기

 

 

알고리즘 적합성 평가

버블 정렬과 병합 정렬의 시간 복잡도를 각각 O(n$^2$), O(nlogn)

  • 버블 정렬 = (1,000,000)$^2$ = 1,000,000,000,000 > 200,000,000 → 부적합 알고리즘
  • 병합 정렬 = 1,000,000log(1,000,000) = 약 20,000,000 < 200,000,000 → 적합 알고리즘

 

 

시간 복잡도를 바탕으로 코드 로직 개선하기

시간 복잡도는 작성한 코드의 비효율적인 로직을 개선하는 바탕으로도 사용할 수 있다.

이 부분을 활용하려면 가장 먼저 코드의 시간 복잡도를 도출할 수 있어야 한다.

시간 복잡도를 도출하려면,

1) 상수는 시간 복잡도 계산에서 제외한다.

2) 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

 

02-1 디버깅

→ 정의 : 프로그램에서 발생하는 문법 오류나 논리 오류를 찾아 바로잡는 과정을 디버깅(debugging)이라고 함.

문법 오류는 컴파일러가 자동으로 찾아 주므로 테스트할 때 문제가 되지 않는다.

논리 오류는 코드가 사용자의 의도와 다르게 동작하는 것이며 다양한 형태로 발생한다.

 

 

 

✅ 디버깅하는 법

디버깅하고자 하는 줄에 중단점(break point)를 설정하고, IDE의 디버깅 기능을 실행하면 됨.

ex) 이클립스 Expressions 기능

  1. 코드에 디버깅하고자 하는 줄에 중단점을 설정한다. (중단점은 여러 개 설정할 수 있다.)
  2. IDE의 디버깅 기능을 실행하면 코드를 1줄씩 실행하거나 다음 중단점까지 실행할 수 있으며, 이 과정에서 추적할 변숫값도 지정할 수 있다. 변숫값이 의도하는 대로 바뀌는지 파악
  3. 변숫값 이외에도 원하는 수식을 입력해 논리 오류를 파악할 수도 있다.

 

코딩 테스트를 진행하며 실수하기 쉬운 4가지 오류 찾아보기

1) 변수 초기화 오류 찾아보기 p.27

책에서 이클립스 IDE를 통해서 예시를 보여주고 있다. 여기서 변수를 초기화 하지 않아서

answer 이란 변수에 초기화가 되어있지 않다.

 

2) 반복문에서 인덱스 범위 지정 오류 찾아보기 p.28

인덱스 범위 지정 오류는 여러 종류로 발생할 수 있음.

0부터 시작한다는 것을 간과, 반복문 N까지 설정해야 하는데 비교 연산자를 잘못 입력하여 N-1까지 반복

int A[] = new int[100001];
for (int i=1; i<10000; i++){ //0을 하나 누락함.
	...
}

 

3) 잘못된 변수 사용 오류 찾아보기 p.29

print를 하여서 console에 결과를 보여주려고 하는데

변수 t 값을 보여줘야 하는 상황에서 testcase라는 변수의 값을 보여줌.

 

4) 자료형 범위 오류 찾아보기 p.30

자료형은 처음부터 long형으로 선언하자.

코딩 테스트에서 계산되는 값은 long형 안에서 웬만하면 표현 가능.

 

 

 

 

참고자료 - Do it! 알고리즘 코딩 테스트 자바편