코딩테스트 준비하기

01 시간복잡도

⌛시간 복잡도

💜 시간 복잡도 유형

빅-오메가 : 최선일 때의 연산 횟수를 나타낸 표기법
빅-세타 : 평균일 때의 연산 횟수를 나타낸 표기법
빅-오 : 최악일 때 연산 횟수를 나타낸 표기법
👉 보통 코딩테스트에서는 빅-오 표기법을 사용한다. 다양한 테스트 케이스들이 존재하기 때문!

💜 빅-오 표기법 시간 복잡도 순서

1. O(1)
2. O(logn)
3. O(n)
4. O(nlogn)
5. O(n^2)
6. O(2^n)
7. O(n!)

💜 시간복잡도를 알고리즘 선택의 기준으로 사용하기

👉 주어진 데이터의 크기 및 시간 제한을 고려하여 적절한 시간 복잡도를 가진 알고리즘을 선택해야 한다. 시간 복잡도로 인해 너무 큰 연산 횟수가 나온다면, 더 작은 시간 복잡도를 가진 알고리즘으로 수정해야 한다.

💜 시간 복잡도 도출 기준

1. 상수는 시간 복잡도 계산에서 무시한다.
2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 된다.

02 디버깅

💜 디버깅이란?

👉 문법 오류나 논리 오류를 찾아 바로잡는 과정

❗디버깅 하는 법
👉 디버깅 하고자 하는 줄에 중단점을 설정해 변수 값 등을 추적한다

💜 실수하기 쉬운 4가지 오류

1. 변수 초기화 오류 - 변수를 초기화 하지 않고 사용하는 경우
2. 반복문의 인덱스 범위 지정 오류 - 반복문의 횟수를 잘못 지정하거나 시작 인덱스를 잘못 설정하는 경우
3. 잘못된 변수 사용 오류 - 변수 이름이 비슷하여 잘못된 변수를 사용하거나 반복문에서 반복 변수 대신 지정 변수를 사용하는 경우
4. 자료형 범위 오류 - 자료형의 범위를 넘어가는 연산을 하는 경우