Do it! 알고리즘 코딩 테스트 자바 편
첫째 마당 코딩테스트 준비하기
01 어떤 알고리즘으로 풀어야 할까? - 알고리즘 선택의 기준이 되는 시간 복잡도
시간 복잡도
주어진 문제를 해결하기 위한 연산 횟수.
일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측한다.
시간 복잡도 유형
- 빅-오메가(Ω(n)): 최선일 때(best case)의 연산 횟수를 나타낸 표기법.
- 빅-세타(θ(n)): 보통일 때(average case)의 연산 횟수를 나타낸 표기법.
- 빅-오(O(n)): 최악일 때(worst case)의 연산 횟수를 나타낸 표기법.
각각의 시간 복잡도는 데이터의 크기(N)의 증가에 따라 성능(수행 시간)이 다르다.
아래는 빅-오(O(n)) 치트시트에서의 복잡도 증가 그림 예시다.
코딩 테스트에서는 빅-오 표기법(O(n))을 기준으로 수행 시간을 계산하는 것이 좋다.
실제 테스트에서는 응시자가 작성한 프로그램으로 다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단하기 때문이다.
연산 횟수 계산 방법
연산 횟수 = 알고리즘 시간 * 데이터의 크기
시간 복잡도 도출 기준
- 상수는 시간 복잡도 계산에서 제외한다.
- 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.
상수
상수란 변하지 않고, 항상 일정한 값을 갖는 수를 말한다. 예를 들어 어떤 함수 f(x)=x+1이 있을 때 x의 값은 특정한 숫자로 정해진 것이 아니라, 정의역의 어떤 숫자도 대입할 수 있는 변수이므로 x는 상수가 아니다.