[코딩 테스트 준비하기] 시간 복잡도

✔ 알고리즘 선택의 기준이 되는 시간 복잡도

코딩 테스트의 핵심 중 하나는 문제마다 주어진 시간 복잡도를 고려해 적절한 알고리즘을 선택하는 것

✔ 시간 복잡도 표기법 알아보기

시간 복잡도는 주어진 문제를 해결하기 위한 연산 횟수

• 일반적으로 수행 시간은 1억 번의 연산을 1초의 시간으로 간주하여 예측
• 시간 복잡도는 빅-오메가, 빅-세타, 빅-오로 정의
  
  1. 빅-오메가 : 최선일 때의 연산 횟수를 나타낸 표기법
  2. 빅-세타 : 보통(평균)일 때의 연산 횟수를 나타낸 표기법
  3. 빅-오 : 최악일 때의 연산 횟수를 나타낸 표기법
• 데이터의 크기가 커질수록, 시간 복잡도의 차이가 많이 발생

코딩 테스트에서는 다양한 테스트 케이스를 수행

• 모든 케이스를 통과해야 하므로 최악의 경우를 염두에 두고 빅-오 표기법을 기준으로 수행 시간을 계산

가장 빠른 1, 가장 느린 n!

✔ 시간 복잡도 활용하기

시간 복잡도의 개념을 코딩 테스트에 어떻게 활용해야할까?

• 알고리즘 유형에 따라 시간 복잡도 계산 → 알고리즘 선택의 기준으로 사용하기
• 자신의 코드의 시간 복잡도 계산 → 시간 복잡도를 바탕으로 코드 로직 개선하기

알고리즘 선택의 기준으로 사용하기

• 입력되는 데이터의 갯수와 시간 제한을 보는 것이 중요
• 연산 횟수 = 알고리즘 시간 복잡도 X 데이터의 크기
• 예) 시간 제한 2초, N이 1 ~ 1000000개일 때의 수 정렬하기
  시간 제한이 2초이므로 2억 번 이하의 연산 횟수로 문제를 해결해야 함
  버블 정렬 = N² = 1000000000000번의 연산, 병합 정렬 = NlogN = 20000000번의 연산을 하므로
  버블 정렬은 이 문제를 풀기에 부적합 알고리즘, 병합 정렬은 적합 알고리즘

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

• 시간 복잡도 도출 기준
  1. 상수는 시간 복잡도 계산에서 제외
  2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준
• 실제 코딩 테스트에서 시간 초과가 발생했을 때
  위 원리를 바탕으로 문제가 되는 코드 부분을 도출하고 더욱 효율적인 구조로 수정하는 작업으로 문제를 해결

 

Do it! 알고리즘 코딩테스트 with JAVA

https://inf.run/w9Tn