이코테 1강 리뷰 (알고리즘 성능 평가)

* 알고리즘 성능 평가

복잡도 : 알고리즘의 성능을 나타내는 척도

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

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

 

- 복잡도가 낮을 수록 좋은 알고리즘임

- 복잡도는 빅오 표기법 사용

 

* 빅오 표기법

- 가장 빠르게 증하가는 항 만을 고려

- 함수의 상한만을 나타냄

- 연산 횟수가 3N^3 + 5N^2 + 1,000,000 일 경우 가장 큰 항인 O(N^3)으로 표현함. 계수는 생략

- 데이터의 크기가 N이라고 했을 때,  다음과 같이 복잡도를 나타낼 수 있음

성능	복잡도	명칭	예제
좋음	O(1)	상수 시간
	O(LogN)	로그 시간
	O(N)	선형 시간	1중 for 문
	O(NlogN)	로그 선형 시간
	O(N^2)	이차 시간	2중 for문이 예가 될 수 있음
	O(N^3)	삼차 시간
나쁨	O(2^n)	지수 시간

수행시간은 데이터의 개수 N에 비례할 것임.

 

- 연산 횟수가 5억을 넘어가면 : C언어 1~3초, 파이썬 5~15초, PyPy는 C언어 보다 빠르게 동작 하기도 함

그러므로 시간 제한에 유의해서 알고리즘을 설계 해야 한다. 설계시 1초에 2천만번 정도 연산할 수 있다 예측하고 설계해야함

- 코딩테스트 문제에서 시간 제한은 5초 정도로 생각해서 푸는 것이 좋음.

- 시간 제한이 1초인 문제를 만났을 때, 다음과 같은 시간 복잡도 이하로 알고리즘을 설계하면 문제를 풀 수 있다.

N의 범위	시간 복잡도
500	O(N^3)
2,000	O(N^2)
100,000	O(NlogN)
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) # 수행시간 출력

 

본 글은 나동빈 - 이코테 2021 강의 몰아보기를 토대로 작성한 정리입니다.

좋은 강의를 올려주신 나동빈님께 감사드립니다.