728x90 반응형 Data Structure & Algorithm17 Dynamic Programming Steps 코딩문제에 단골로 등장하는 Dynamic Programming에 대해 더 알아보기 위해 공부한 유투브 동영상을 정리해봤습니다 https://www.youtube.com/watch?v=aPQY__2H3tE&t=10s&ab_channel=Reducible Dynamic Programming 이란? - 부분문제(subproblem)을 식별하고 해결해서 큰 문제를 해결하는 방식 [ 5 Steps to solve DP ] 1. Longest Increasing Subsequence (LIS) 문제 정의하고 살펴보기 a1에서 a(n)까지 [3,1,8,2,5]가 있을 때, 1,2,5는 연속되면서 계속 증가하는 Subsequence 중에서 3개로 가장 긴 길이에 해당 2. Visualize Examples => Dra.. 2022. 9. 25. Stack & Queue 개념 정리 Stack 이란? : Push와 pop 기능을 가진 one-ended linear data (LIFO) Complexity Analysis Pushing O(1) Popping O(1) Peeking O(1) Searching O(n) Size O(1) 벽돌을 길게 쌓아서 벽돌을 넣고(push) 벽돌을 빼는(pop)을 상상하면 훨씬 이해가 잘 되는 것 같아요 Queue 이란? : Enqueue 와 Dequeue 주요 기능을 가진 선형 데이터 구조 (FIFO) 식당 줄 서는걸 생각해보면 queue와 상당히 비슷한 걸 알 수 있습니다 줄을 서고(Enqueue) 줄에서 빠지고(Dequeue) ! Complexity Analysis Enqueue O(1) Dequeue O(1) Peeking O(1) Conta.. 2022. 9. 21. Singly & Doubly Linked List Linked List 란? A sequential list of nodes that holds data which point to other nodes also containing data 데이터를 가지고 있는 노드들의 연속적인 리스트 어디에 사용될까? List, Queue & stack, circular list separate chaining, hashtable 등등 ▶ Singly Linked List와 Doubly Linked List 비교 장점 단점 Singly Linked List 사용하기 용이함 메모리를 덜 사용함 이전의 요소에 쉽게 접근하기 어려움 Doubly Linked List 역방향 순회가 가능함 2배의 메모리가 소요됨 ▶ Singly Linked List와 Doubly Linked .. 2022. 9. 20. Big O notation & Array Complexity Analysis : Programmer은 아래 2가지를 고민한다 How much time does this algorithm need to finish? How much space does this algorithm need to finish? Big-O Notation Big-O Notation gives an upper bound of the complexity in the worst case, helping to quantify performance as the input size becomes arbitrarily large n : input 사이즈 Constant Time O(1) Logarithmic Time O(log(n)) Linear Time O(n) Linearith.. 2022. 9. 19. Linked List 총정리 LinkedList란? : 리스트와 달리 원소를 메모리에 저장하는 방식이 다른 선형 자료구조 개인적으로 Linked List는 꼬치와 비슷하다고 생각하는데요, 꼬치에 있는 각 재료들 = 원소들은 '노드'라고 불리고, 이 노드는 값을 지니고 있는 '데이터'와 다음 노드의 참조값을 가지고 있는 'Next'로 분류됩니다 빈 막대기에 재료를 끼운다고 가정하면, 처음으로 끼우는 재료를 Head라고 부르는데요 우리가 꼬치에 재료를 다 끼우면 꼬치를 다 만들었다고 하죠? 마찬가지로 Linked List에서는 재료를 다 끼우고 나면 None을 반환합니다 그러면 코드상에서 이러한 개념들이 어떻게 나타내질 수 있는지 봅시다 def __init__(self, nodes=None): self.head = None if nod.. 2022. 9. 14. 이전 1 2 3 다음 728x90 반응형
