동빈나님의 이코테 2021을 보고 정리한 게시글입니다.

알고리즘의 성능 평가

복잡도

알고리즘의 성능을 나타내는 척도로, 일반적으로 복잡도가 낮을수록 좋은 알고리즘이다.

시간복잡도

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

공간복잡도

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

---

빅오 표기법(Big-O Notaion)

가장 빠르게 증가하는 항만을 고려하는 표기법

$5N^3+2N^2+1000$ 인 알고리즘을 빅오 표기법으로 나타내면 $O(N^3)$

	순위	명칭
좋음(Better)	$O(1)$	상수 시간(Constant time)
	$O(logN)$	로그 시간(Log time)
	$O(N)$	선형 시간
...	$O(NlogN)$	로그 선형 시간
	$O(N^2)$	이차 시간
	$O(N^3)$	삼차 시간
	$O(2^n)$	지수 시간
나쁨(Worse)	$O(n!)$	팩토리얼

---

알고리즘 설계 Tip

일반적으로 CPU 기반 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우:

• C언어를 기준으로 1~3초 시간 소요
• Python을 기준으로 5~15초 시간 소요

코딩테스트 문제에서 시간제한은 통상 1~5초 가량
문제에 명시되어 있지 않은 경우 대략 5초라고 생각

[알고리즘 설계 단계]

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

2. 문제에서 가장먼저 시간제한(수행시간 요구사항) 확인 및 분석

   시간제한이 1초인 문제

   • N의 범위가 500인 경우: 최대 $O(N^3)$ 알고리즘 설계
   • N의 범위가 2000인 경우: 최대 $O(N^2)$ 알고리즘 설계
   • N의 범위가 100000인 경우: 최대 $O(logN)$ 알고리즘 설계
   • N의 범위가 10000000인 경우: 최대 $O(N)$ 알고리즘 설계

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

4. 소스코드 설계 및 코딩