01. 취업 경향

가장 출제 빈도가 높은 알고리즘 유형: 그리디(쉬운 난이도) > 구현 > DFS/BFS를 활용한 탐색

Screenshot 2021-09-10 at 20.07.50.png

02. 알고리즘 성능 평가

알고리즘 설계 TIP

일반적으로 CPU 기반의 개인 컴퓨터나 채점용 컴퓨터에서 연산 횟수가 5억을 넘어가는 경우:
- C 기준: 통상적으로 1~3초 소요
- Python 기준: 통상적으로5~15초 소요 (PyPy 의 경우 때때로 C 보다 빠르게 동작하기도 함)
O(N3)의 알고리즘을 설계한 경우 N 의 값이 5,000이 넘어간다면 얼마나 걸릴까?
코딩 테스트에서 시간제한은 통상 1~5초임
- 문제에 명시되어 있지 않더라도 대략 5초 정도라고 생각하고 풀어야 함

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

시간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 수행 시간 분석
공간 복잡도: 특정한 크기의 입력에 대하여 알고리즘의 메모리 사용량 분석
동일한 기능을 수행하는 알고리즘이 있다면, 복잡도가 낮을수록 좋은 알고리즘

복잡도를 표기하는 방법

Big-O Notation: 가장 빠르게 증가하는 항만을 고려하는 표기법
- O(N)
```
arr = [2,4,1,3,5] # data
summary = 0

for x in arr:
	summary += x
print(x)
```
- O(N2)
  - 모든 2중 반복문의 시간 복잡도가 O(N2)인 것은 아님
  - 소스 코드가 내부적으로 다른 함수를 호출한다면 그 함수의 시간 복잡도까지 고려해야 함
```
arr = [2,4,1,3,5] # data

for i in arr : 
	for j in arr :
		temp = i * j
		print(temp)
```

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