[알고리즘/Python] 알고리즘 설계 Tip!!

코딩 테스트 문제에서 시간제한은 보통 1~5초가량이라고 생각해야함.

Python의 경우 연산 횟수가 5억을 넘어간다면 통상 5~15초 가량의 시간이 소요된다.

 

 

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

만약 시간제한이 1초인 문제를 만났다면,  일반적인 기준은 다음과 같다.

• N의 범위가 500인 경우 : 시간 복잡도가 O(N^3)인 알고리즘을 설계하기

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

• N의 범위가 100,000인 경우 : 시간 복잡도가 O(N*logN)인 알고리즘을 설계하기

• 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)  #수행 시간 출력

알고리즘 문제를 풀때 위 코드를 활용해서 프로그램의 실행시간을 살펴보자!