섹션 1. 코딩테스트 [준비] 하기 - 시간 복잡도, 디버깅

섹션 1. 코딩테스트 [준비] 하기

⬛ 01. 시간 복잡도의 중요성

• 어떤 알고리즘으로 풀어야 하는가 ?
• 알고리즘 선택의 기준이 되는 ‘시간복잡도’

⬛ 01-1. 시간 복잡도 표기법

🟦 시간 복잡도

• 시간복잡도 : 주어진 문제 해결을 위한 ‘연산 횟수’
• 기본적으로 1억 번(10의 8승) 의 연산 = 1초의 시간으로 간주한다.

🟦 시간 복잡도의 유형

• 1) 빅-오메가 : ‘최선’일 때의 연산 횟수 표기법
• 2) 빅-세타 : ‘보통’일 때의 연산 횟수 표기법
• 3) 빅-오(O(n)) : ‘최악’일 떄의 연산 횟수 표기법 - 코테에서 사용

⬛ 01-2. 시간 복잡도 활용하기

• 연산 횟수 = (알고리즘 시간복잡도) X (데이터 크기)
• 시간 제한을 확인하여 가능한 연산 횟수의 제한을 두고 생각할 것.

🟦 (1) 시간 제한 확인 (ex. 2초)

• 2초 제한이라면 2억번 이내의 연산 안에 도출해야 한다.

🟦 (2) 데이터의 크기 확인 (ex. 0≤ N ≤1,000,000)

• N이 백만(10의 6) 이므로 N2이 되는 이중 for문 사용 시 시간 제한 조건 만족 X

🟧 시간 복잡도 도출 기준

• 1) 상수는 제외
• • ex) for()문 3번 사용하면 3XN 번이지만 표기로는 O(N)이다.
• 2) 가장 많이 중첩된 반복문의 수행 횟수가 기준이 된다.

⬛ 02. 디버깅의 중요성

• 코드 논리 오류는 어떻게 잡을까 ?
• 코드 논리 오류 탐색기 : 디버깅

⬛ 02-1. 디버깅이 왜 중요한가

🟦 디버깅

• 문법 오류 or 논리 오류 찾아 바로잡는 과정

🟦 디버깅 하는 법

• break point(중단점)을 설정한 뒤, IDE에서 디버깅 기능 실행 하면 된다.
• 1) 디버깅하고자 하는 라인에 중단점 설정(여러 개 가능)
• 2) IDE의 디버깅 기능 실행하여 1줄씩 실행 or 다음 중단점까지 실행*
• ⇒ 추적할 변숫값 지정이 가능, 변숫값이 자신의 의도대로 잘 바뀌는지 활용 필요
• 3) 변숫값 이외에도 원하는 수식 입력하여 논리 오류 파악도 가능

---

⬛ 02-2. 디버깅 활용 대표 사례

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

🟧 1) 변수 초기화 오류

🟧 2) 반복문에서 인덱스 범위 지정 오류

🟧 3) 잘못된 변수 사용 오류

🟧 4) 자료형 범위 오류