CS/DSA2 [DSA] 1. 1-D Dynamic Programming TABLE OF CONTENTS SolutionBrute Force = Decision TreeMemoization(=Caching) = Backtracking(=dfs)(Base Case → Cache Hit → 내려가기 → 올라왔을때)DP = Bottom-UP Approach(=Memoization logic을 거꾸로 적용해서 표/그림/공식 제작)1. Climbing Stairs한번에 계단을 1개 혹은 2개씩만 올라갈 수 있을때 n개의 계단을 오를 수 있는 방법의 수를 구하라# O(n), O(n)class Solution(object): def climbStairs(self, n): if n == 1: return 1 if n == 2: .. 2024. 7. 12. [DSA] 1. Data Structures and Algorithms TABLE OF CONTENTS 1. What is good code?무엇이 좋은 코드일까? => 2가지 조건을 만족시키면 된다. 바로 Readability와 Scalability이다. 하지만 대부분의 경우 Speed와 Memory는 trade-off 관계이다. 하나를 최적화 시키면 다른 하나가 안좋아진다는 말이다. 따라서 보통 Time Complexity를 최적화하는 경우에는 Space Complexity를 포기하고, HashSet이나 HashMap과 같은 추가적인 자료구조를 사용하면 되는 것이고, Space Complexity를 최적화 하는 방법은 Time Complexity를 포기하면 된다. 2. Big O그러면 Big O notation이란 무엇일까?빅오란 결국 복잡도를 표기하는 방법이다. 이렇.. 2024. 7. 12. 이전 1 다음
