개요 및 출제 경향 / 알고리즘 성능 평가

자신만의 소스코드 관리하기❗❕

Team-Notes : 자신이 자주 이용하는 알고리즘 코드를 라이브러리화 하는 습관 들이기

 

출제 경향

---

출제 빈도 높은 알고리즘 유형

• 그리디
• 구현
• DFS / BFS 를 활용한 탐색

그 외 )

• 다이나믹 프로그래밍
• 정렬
• 이진 탐색
• 최단 경로
• 그래프 이론

 

 

알고리즘 성능 평가

---

복잡도

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

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

• 시간 : 알고리즘의 수행 시간 분석
• 공간 : 알고리즘의 메모리 사용량 분석

 

- 빅오 표기법(Big-O Notation)

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

차수가 가장 큰 항만 남김 (계수는 제외)

실행시간이 빠른 순서

시간 복잡도 계산하기

arr = [1,2,3,4,5]  # N = 5
summary = 0    # 합계를 저장할 변수

for x in arr:
	summary += x
   
print(summary)

수행시간은 데이터의 개수 (N)에 비례할 것임을 예측

따라서, 시간복잡도 : O(N)

 

arr = [1,2,3,4,5]

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

시간 복잡도 : 

 

 

알고리즘 문제해결 과정

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

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

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

4. 소스코드 설계 및 코딩

 

import time
start_time = time.time()
end_time = time.time()
print("time:", end_time - start_time)

 

 

참조 : https://www.youtube.com/playlist?list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC