시간복잡도와 디버깅

 

Do it! 알고리즘 코딩테스트 : 파이썬

 

 

시간 복잡도

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

 

파이썬에서는 2000만 번~1억 번의 연산을 1초의 수행 시간으로 예측

표기법에는

1. 빅-오메가 Ω(n) : 최선일 때의 연산 횟수

2. 빅-세타 θ(n) : 보통일 때의 연산 횟수

3. 빅-오 O(n) : 최악일 때의 연산 횟수

가 있고

 

→ 코딩 테스트에서는 당연히 빅-오 표기법을 기준으로 수행 시간을 계산하는 것이 좋음!
(항상 최악의 경우를 생각하고 로직을 짜야함)

 

시간 복잡도를 바탕으로 코드 로직을 개선하려면 코드의 시간 복잡도를 도출할 수 있어야함!

시간 복잡도 도출 기준은

 

1. 상수는 시간 복잡도 계산에서 제외

 

2. 가장 많이 중첩된 반복문의 수행 횟수가 시간 복잡도의 기준이 됨

 

디버깅

문법은 컴파일러가 잡아주기 때문에 신경쓰지 않아도 괜찮다!

하지만 내가 짠 Logic 이 원하는데로 돌지 않는 논리 오류는 해결해야함

 

→ 가장 뛰어난 오류 탐색 방법은 “디버깅” 이다.

 

디버깅 방법은

 

 

1. 코드에서 디버깅하고자 하는 줄에 중단점(break point) 를 설정한다. (여러 개 설정 가능)

 

2. IDE의 디버깅 기능을 실행하면 코드를 1줄씩 실행하거나다음 중단점까지 실행할 수 있으며,
이 과정에서 추적할 변숫값도 지정할 수 있다.
(이 방법으로 변숫값이 자신이 의도한 대로 바뀌는지 파악 가능)

3. 변숫값 이외에도 원하는 수식을 입력해 논리 오류를 파악할 수 있다.

이다.

파이썬을 이용해 알고리즘 문제풀이를 진행하며 실수하기 쉬운 4가지 대표적인 오류는

1. 변수 초기화 과정에서 발생하는 오류

2. 반복문의 인덱스 설정에서 발생하는 오류

3. 잘못된 변수를 사용하는 오류

4. 자동 형변환 오류 (파이썬에서 나누기 연산자 / 와 // 의 차이점 주의!)

가 있다.