✅ 코딩테스트란?

• 문제마다 주어진 시간복잡도를 고려해 적절한 알고리즘을 선택하는 것
• 빅-오(O(n)) 표기법을 기준으로 수행시간을 계산 (최악의 경우를 고려하는 방법)

📍시간복잡도 표기법

✅ 시간복잡도란?

• 주어진 문제를 해결하기 위한 연산횟수를 말한다.
• 일반적으로 수행 시간은 1초에 1억번의 연산으로 간주하여 예측한다.
• 데이터의 크기(N)의 증가에 따라 성능(수행 시간)이 다르다.

✅ 시간복잡도 유형

• 빅-오메가 : 최선일 때(best case)의 연산횟수를 나타낸 표기법 (1번)
• 빅-세타 : 보통일 때(average case)의 연산횟수를 나타낸 표기법 (N/2번)
• 빅-오(O(n)) : 최악일 때(worse case)의 연산횟수를 나타낸 표기법 (N번)

✅ 빅-오 표기법(O(n))

• 코딩테스트에서 주로 사용한다.
• 데이터의 크기(N)의 증가에 따라 성능(수행 시간)이 다르다.
  

📍시간복잡도 활용하기

• 연산횟수는 1초에 1억번 연산하는 것을 기준으로 잡는다.
• 시간복잡도는 항상 최악일 때, 즉 데이터의 크기가 가장 클 때를 기준으로 잡는다.

ex. 문제에 주어진 시간 제한이 2초인 경우, 연산횟수 2억 번 안에 원하는 답을 구해야한다.
즉, 데이터의 크기(N)를 단서로 사용해야하는 알고리즘을 추측해볼 수 있다.

✅ 시간복잡도 도출 기준

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

📍디버깅의 중요성

✅ 디버깅(debugging)

• 문법오류나 논리오류를 찾아 바로잡는 과정을 뜻함

• 문법오류 : 컴파일러가 자동으로 찾아주므로 테스트할 때 문제가 되지 않음
• 논리오류 : 코드가 사용자의 의도와 다르게 동작하는 것이며 다양한 형태로 발생

✅ 디버깅 방법

1. 중단점 설정 (여러 개 설정 가능)
2. IDE의 디버깅 기능 실행(1줄씩 혹은 다음 중단점까지 실행) & 변숫값 지정
3. 변숫값 이외에도 원하는 수식을 입력해 논리 오류를 파악

📍디버깅 활용하기

✅ 변수 초기화 오류 찾아보기

• int answer = 0; 과 같은 변수 초기화 로직 확인하기
• 실제 코딩테스트 시 2번째 테스트 케이스부터 통과되지 않는다면, 모든 변수가 정상적으로 초기화되고 있는 디버깅을 이용해 확인해보기

✅ 반복문에서 인덱스 범위 지정 오류 찾아보기

• for(int i = 1; i<10000; i++) {} 에서 0의 갯수 확인하기
  배열 인덱스의 시작과 끝 확인하기(0부터 혹은 1부터 시작 / N까지 혹은 N-1까지 반복)

✅ 잘못된 변수 사용 오류 찾아보기

• 변수명을 혼동해 잘못된 값이 들어가진 않았는지 확인하기

✅ 자료형 범위 오류 찾아보기

• 변수에 지정한 자료형 범위를 넘어가는 경우, 저장할 수 없는 범위의 값을 선언한 것은 아닌지 확인하기
• 자료형은 처음부터 long형으로 선언하기