알고리즘 기초 및 파이썬 기초 문법(1) - 알고리즘 기초

알고리즘 성능 평가

1. 복잡도(Complexity)

- 알고리즘 성능을 나타내는 척도 (복잡도가 낮을수록 좋은 알고리즘)

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

- 공간 복잡도 : 특정한 크기의 입력에 대하여 알고리즘 메모리 사용량 분석

 

2. 빅오 표기법(Big-O)

- 가장 빠르게 증가하는 항만 표기 (차수가 가장 큰 항만 남김)

 

출처 : 이코테

3. 알고리즘 설계 팁(Python)

1. Python을 기준으로 5 ~ 15초 가량 시간 소요

2. 상황에 따라 PyPy도 이용해 보는 것도 좋음

3. 코딩 테스트 문제의 시간제한은 통상 1~5초

4. 문제에서 시간제한(수행시간 요구사항)을 가장 먼저 확인

- N의 범위 500인 경우 - O(N^3) 알고리즘

- N의 범위 2,000인 경우 - O(N^2) 알고리즘

- N의 범위 10만 경우 - O(NlogN) 알고리즘

- N의 범위 1000만 경우 - O(N) 알고리즘

 

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

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

   - 단계별로 문제를 쪼갠 뒤 문제를 최대한 간결하게 정의

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

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

4. 소스코드 설계 및 코딩

 

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

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

#프로그램 소스코드
end_time = time.time() #측정 종료
print("time:", end_time - start_time) # 수행 시간 출력