이 시리즈의 내용 출처 : Do it 알고리즘 코딩테스트 with JAVA 강의
시간복잡도 정의하기
- 시간 복잡도 : 주어진 문제를 해결하기 위한 연산 횟수
- 수행 시간은 1억 번의 연산을 1초의 시간으로 간주
시간 복잡도 유형
- 빅-오메가 Ω(n) : 최선일 때의 연산 횟수를 나타내는 표기법
- 빅-세타 θ(n) : 보통일 때의 연산 횟수를 나타내는 표기법
- 빅-오 O(n) : 최악일 때의 연산 횟수를 나타내는 표기법
→ 가장 최악의 케이스를 더 염두해두고 문제를 풀어야 함
다양한 테스트 케이스를 수행해 모든 케이스를 통과해야만 합격으로 판단하기 때문
공부를 많이 하다 보면 알고리즘이 돌아가는 원리에 따라 시간복잡도를 파악할 수 있게 됨.
자기가 짠 코드가 시간복잡도가 어떠한지를 파악할 수 있으면 좋음.
https://www.acmicpc.net/problem/2751 문제 예시로 시간복잡도 파악
시간복잡도 따질 때는 데이터의 개수를 파악할 것.
수의 개수 N(1 ≤ N ≤ 1,000,000) → 데이터가 1000000인걸 인지하고 그에 맞는 알고리즘을 써야 함.
제한시간 2초 → 2억 번 이하의 연산 횟수 필요
연산 횟수 = 알고리즘 시간 복잡도 * 데이터의 크기
ex) 버블 정렬 : N^2 = (1000000)^2 = 1000000000000 > 200000000 → 2억보다 더 커서 부적합 알고리즘
ex) 병합 정렬 : NlogN = 1000000 log (1000000) = 1000000 * (약 20) = 약 20000000 < 200000000 → 적합 알고리즘
시간 복잡도를 바탕으로 코드 로직 계산하기
시간 복잡도 도출 기준
- 상수는 시간 복잡도 계산에서 제외
- 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 됨
연산 횟수가 N이거나 3N이거나 코딩테스트에서는 큰 차이가 없다고 판단함. → O(N)
N^2은 큰 차이를 가짐.
만약 N^2인 이중for문이 있고 일반 for문이 10개 더 있다 하더라도, 가장 많이 중첩된 반복문을 기준으로 도출하므로 전체 코드의 시간 복잡도는 O(N^2)
코딩테스트에서 시간 초과 떴을 때 살펴 봐야 할 것
- 문제에 알맞은 알고리즘을 써야 함
- 문제에 맞는 알고리즘을 이용한 경우
- 내가 짠 나머지 로직이 효율적인지를 살펴 봐야 함
- 비효율적인 로직을 찾아서 효율적으로 바꾸기
자신이 작성한 코드의 시간 복잡도를 도출할 수 있다면 실제 코딩테스트에서 시간 초과가 발생했을 때
- 이 원리를 바탕으로 문제가 되는 코드 부분을 도출할 수 있고
- 이 부분을 연산에 더욱 효율적인 구조로 수정하는 작업으로 문제를 해결할 수 있음
