KOOC/Linear Structure & Dynamic Programming18 Binary Search Tree <6-2> > Binary Search Tree : a simple structure Insert Operation of Binary Search Tree Search Operation of Binary Search Tree Binary Search Tree : a simple structure 이진검색트리(BST)란, degree 가 2인 Tree를 말한다. BST의 설계 목적은 저장된 데이터를 더 빠르게 찾는 것이다. 위 그림에서, 링크드리스트와 BST에서 '1004'를 찾는 과정을 비교해보자. 링크드리스트는 직렬구조로 데이터를 저장하기때문에, 1004를 찾기 위해 4번에 retrieval이 발생한다. 하지만, 데이터 저장에 일정한 규칙이 있다면 BST가 훨씬 빠르다. 예를 들어 특정 노드(1003)의 왼쪽에.. 2023. 12. 29. Binary Search Tree <6-1> > Tree as an abstract data type Terminologies of tree structure Characteristics of trees Tree as an abstract data type 2023.10.19 - [KOOC/Linear Structure & Dynamic Programming] - Linked list, Stack, Queue Linked list, Stack, Queue > Abstract Data Types Array Abstract Data Types ADT란, 데이터 구조를 추상화한 것으로 아래의 특징을 가진다. 데이터의 저장: 어떤 데이터가 저장되는지 설명한다. 데이터의 운영: 데이터의 저장, 검색 등의 statfinance.tistory.com Astra.. 2023. 12. 27. Simulation <5-1> > Modeling Simulate Modeling 모델링이란, 현실세계의 문제를 간략하게 추상화하는 것이다. 모델링한다는 것은, 그 문제의 핵심만을 가져와 형상화한다는 것이다. 모델링을 하는 이유는, 현실문제를 전부 trace 하기 어렵기 때문에, 해결을 위해 필요한 핵심들로만 구성함으로써 문제의 본질에 더 집중하고 신속하게 해결하기 위함이다. Simulate 모델링 정의에 따라 수많은 이론들이 생겨났다. 대표적인게 경제학이다. 시장의 현상을 알고, 시장에서 발생하는 문제를 해결하기 위해 수요공급모델이 탄생한 것이다. 통계학에서도 회귀모델 같은 통계모델들은 현실의 문제를 해결하기위해, 예측을 위해 성립된 이론이다. 이런 모델링을 Numerical modeling 이라고 하며, 어떤 현상을 공식화하고, .. 2023. 12. 11. Recursions and Dynamic Programming <4-3> > Dynamic Programming Fibonacci in DP Assembly Line Scheduling Dynamic Programming 다이나믹 프로그래밍은 overlapping sub-instance 로 정의한 문제를 풀어내는 알고리즘이다. 다시 말하면, 작은 단위의 문제부터 풀어낸다는 거다. 왼쪽 그림에서 Recursion은 F(4)를 풀기 위해 하위 F(3), F(2)를 푸는 구조였다. 하지만 다이나믹 프로그래밍은 F(0)부터 풀어낸다. 즉, 작은 단위의 문제를 풀어 그를 바탕으로 F(4)를 푸는 구조다. 다이나믹 프로그래밍에서는 작은 단위의 문제를 푼 값을 기록하는 테이블이 필요하며, 테이블에 기록한 값을 기반으로 더 큰 단위의 문제를 풀어간다. 테이블에 기록하는 것을 memoizat.. 2023. 11. 13. 이전 1 2 3 4 5 다음 반응형
