Algorithm) 알고리즘 성능

요구사항에 따라 적절한 알고리즘 설계하기 

문제에서 가장 먼저 확인해야 하는 내용은 시간제한(수행시간 요구사항)

 

시간제한이 1초인 문제를 만났을 때, 일반적인 기준

• N의 범위가 500인 경우: 시간 복잡도가 O(N^3)인 알고리즘을 설계
• N의 범위가 2,000인 경우: 시간 복잡도가 O(N^2)인 알고리즘을 설계
• N의 범위가 100,000인 경우: 시간 복잡도가 O(NlogN)인 알고리즘을 설계
• N의 범위가 10,000,000인 경우: 시간 복잡도가 O(N)인 알고리즘을 설계

 

알고리즘 문제 해결 과정 (일반적으로)

1. 지문 읽기 및 컴퓨팅적 사고

2. 요구사항(복잡도) 분석

3. 문제 해결을 위한 아이디어 찾기

4. 소스코드 설계 및 코딩 

일반적으로 대부분의 문제 출제자들은 핵심 아이디어를 캐치한다면, 간결하게 소스코드를 작성할 수 있는 형태로 문제 출제함

 

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

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

# 프로그램 소스코드 ...

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