파이썬 코테 준비 1 - 알고리즘 성능 평가

동빈나님의 이것이 코딩테스트다 책을 보면서 파이썬 코테 준비를 했었다.

코테 팁들을 원노트에 정리해뒀었는데 블로그에 옮겨야겠다는 생각이 들어 정리하게 되었다. 

 

온라인 개발 환경 리플릿 

Log In

동빈나님의 팀 노트 

GitHub - ndb796/Python-Competitive-Programming-Team-Notes: Python Library for Programming Competition

 

1. 복잡도

 

시간 복잡도

특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석

 

공간 복잡도

특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석

 

2. 빅오 표기법 

가장 빠르게 증가하는 항만을 고려한다.

연산횟수가 3N^3 + 5N^2 + 1,000,000인 알고리즘이 있다면

빅오표기법에서는 차수가 가장 큰 항만 남기므로 O(N^3)으로 표현된다.

 

O(1) > O(logN) > O(N) > O(NlogN) > O(N^2) > O(N^3) > O(2^n)

코테에서 시간제한은 통상 1~5초 가량이라고 생각하자. 문제에 시간제한이 명시되어 있지 않더라도 5초 안에 푸는게 합리적이다. PyPy를 지원하는 경우에는 때로는 C언어보다도 빠르지만 이를 항상 보장하지 않는다. 일반적으로 파이썬으로 먼저 제출 한 후에, 알고리즘에는 문제가 없는것 같다면 PyPy로 제출 해 보자.

 

 

 

3. 시간 제한

1. N의 범위가 500인 경우 : 시간 복잡도 O(N3)인 알고리즘을 설계하면 문제를 풀 수 있다.
2. N의 범위가 2000인 경우 : 시간 복잡도가 O(N2)인 알고리즘을 설계하면 문제를 풀 수 있다.
3. N의 범위가 100,000인 경우 : 시간 복잡도가 O(NlogN)인 알고리즘을 설계하면 문제를 풀 수 있다.
4. N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계하면 문제를 풀 수 있다.

 

 

 

4. 알고리즘 문제 해결 과정

1. 지문 읽기 및 컴퓨터적 사고
2. 요구사항(복잡도) 분석
3. 문제해결을 위한 아이디어 찾기
4. 소스코드 설계 및 코딩

일반적으로 대부분의 문제 출제자들은 핵심아이디어로 캐치한다.

 

 

 

 

5. 수행시간 측정 소스코드 예제

import time
start_time = time.time() #측정 시작

# 프로그램 소스코드 

end_time = time.time() #측정 종료
print("time:", end_time - start_time) # 수행 시간 출력