본 포스팅은 필자가 Udemy에서 Andrei Neagoie의 Master the Coding Interview: Data Structures + Algorithms를 수강하며 공부한 내용을 정리하는 글이다.
알고리즘: 어떠한 문제를 해결하기 위한 방법
빅오 표기법: 알고리즘 간에 효율성을 비교하기 위한 표기법
클린코드의 가장 중요한 부분은 두 가지로 나뉜다.
1. 가독성(Readable)
2. 확장성(Scalable) -> 이 부분이 Big-O 표기법에 해당한다.
확장성이란, 클라우드에서 작업량 증가할 시 부하를 감당할 수 있을만한 Resource Capacity를 갖고 있느냐에 대한 내용이다.
빅오 표기법 성능비교
그래프에 나와 있는 시간 복잡도의 성능을 비교하면 다음과 같다.
(왼쪽에서 오른쪽으로 갈수록 효율성이 떨어진다.)
빅오 표기법을 단순화하고자 다음 법칙들을 적용해야 한다. 다음은 가장 자주 사용되는 법칙들이다.
1. 상수항 무시
O(2N) -> O(N)
O(N² + 2) -> O(N²)
2. 영향력 없는 항 무시
O(N² + N) -> O(N²)
O(N²)이 가장 지배적이기 때문에 그 외에 영향력이 없는 항들은 무시한다.
Big-O는 '규모'를 중요하게 여기기 때문임!
ex) N이 5000이라면 N²은 25000000이 된다.
그에 반해서 N+N은 10000, 따라서 영향력이 가장 큰 항은 N²이 된다.
강의에서 나온 Rule Book
Rule 1: Always worst Case
Rule 2: Remove Constants
Rule 3: Different inputs should have different variables/ 0(a+b). A and B arrays nested would be 0(a*b)
+ for steps in order(순서대로 다 더하고)
+ for nested steps(중첩된 반복문 곱하기)
Rule 4: Drop non-dominant terms
자료구조: 데이터를 저장하는 방법
알고리즘: 프로그램을 작성하기 위해 자료구조를 사용하는 방법
따라서, 좋은 프로그램을 만드는 방법은 적절한 자료구조를 선택하고
그에 적합한 알고리즘을 선택하여 코드를 작성해야 한다.
'알고리즘, 자료구조' 카테고리의 다른 글
| 2. 빅오 표기법 (Big-O notation) - [알고리즘, 자료구조] (0) | 2021.01.27 |
|---|
