문제 해결 방법의 종류 brute-force approach : 모든 경우에 대해서 다 계산하고 가장 좋은것을 택하는 방법. n이 커지면 너무 오래걸려 실행 불가능하다. divide and conquer approach dynamic programming approach greedy approach Dynamic Programming(DP) 주어진 문제를 하위문제로 나누어서 해결한다. 하위 문제가 서로 연관이 있을 때 사용 (divide and conquer은 서로 연관이 없을 때 사용) optimization problem(최적해를 구할 때) 를 풀 때 사용 (최적화문제 : 답이 여러개인 문제에서 가장 좋은 답을 찾는 문제 ex. 최단경로 문제) 모든 하위 문제를 풀고 그 결과를 저장해두어 그 결과를 ..
Binary Search Tree 이진탐색과 연결리스트를 결합한 자료구조이다. 각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값만 있어야한다. 각 노드의 오른쪽 서브트리에는 해당 노드보다 큰 값만 있어야한다. operation : SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, DELETE average case : O(log n) (평균 높이 : log n) worst case : O(n) Search 루트에서 시작. k를 찾을 때 key[x]>k 이면 x의 왼쪽 subtree에서 search key[x] 그냥 삭제 Case2: 삭제할 노드에 자식노드가 1개 있을 때 -> 해당 노드를 지우고 해당 노드의 자식과 부모를 연결 Case3: 자식노드가..
hashing dictionary (key, value)를 implementing insert, search, delete 연산의 average-case : O(1) find minimum과 같은 sort연산은 비효율적이다. dictionary dynamic-set data structure. 동적으로 크기가 변한다. operation : insert, search, delete hash table key : hash function의 input. U : universe of keys. 모든 가능한 키의 집합 K : actual keys. 딕셔너리에 매칭된 실제 키 Hash Table을 만들 때 U를 저장할 필요 없다. |k|=n의 사이즈를 테이블로 만든다. 하지만 좁은 장소에 여러개를 저장해야하므로 h..
