무제 무제

n개의 원소를 하나의 자료구조로 합쳐 조작하고 탐색하기 용이하게 만드는 자료구조 n개의 원소가 n개의 set으로 초기화됨 (MakeSet()) Tree를 사용하는 것이 효율적. Tree의 구현은 각 node의 parents를 저장하는 배열로 (parents[i] = j) Union() -> 두 set을 하나의 set으로 합치는 작업 (O(n)) void simpleUnion(int i, int j) {parent[i] = j;} 효율적인 union을 위해 set의 height정보도 같이 저장하고 union시 높이가 낮은 set을 높이가 큰 set에 붙여서 합침 두 set의 height가 같으면 union된 set의 height 증가 Find() -> 어떤 set안에 특정 element가 들어있나 찾음(포..

여러 개의 list에서 가장 작은 값이나 가장 큰 값을 찾을 때 사용 리프는 각 list의 첫번째 값들. Winner Tree - Tournament의 승자를 node에 기록. root node는 트리에서 가장 작은 값 최종 승자는 승자가 속해있던 list의 다음 값으로 교체되고 재실행 Loser Tree - Tournament의 패자를 node에 기록 K-way merge sorting이나 Bin Packing 문제 해결에 적용됨 Bin Packing에서 Best Fit decreasing알고리즘에 Selection Tree가 사용됨 First Fit decreasing: Item을 내림차순으로 정렬한 후 첫번째부터 남는 공간이 있는 bin에 item을 채우고 안되면 새로운 bin 사용 Best Fit..

필요한 기능: IsEmpty(), Search(key), Insert(key, value), Delete(key) Search(), Insert(), Delete()의 시간복잡도 각 노드는 key와 value로 구성되어있고, root의 왼쪽 subtree의 키는 항상 root의 key보다 작으며 오른쪽은 root의 key보다 큼 Indexed Binary Search Tree는 key,value이외에 left subtree의 node개수도 저장 InOrder로 읽으면 sort된 배열의 key가 나옴 Binary search tree를 밸런싱하기 위한 방법으로는 AVL tree와 RB tree가 있음

Max priority queue: root의 값이 가장 크고 자식의 값은 부모보다 작거나 같은 Tree Min priority queue: root의 값이 가장 작고 자식의 값은 부모 보다 크거나 같은 Tree empty(), size(), insert(), top(), delete()등의 기능이 있음 empty(), size(), top()은 O(1), insert()와 delete()는 O(logn) Binary 형태의 Priority queue는 Heap Sort에 사용됨 (Average, best, worst O(nlogn) Job Scheduling Problem에서 LPT algorithm 에 사용됨 (Max priority queue로 가장 긴 일을 골라 Min priority queue로..

Arithmetic expression을 Tree로 표현 Prefix - 연산자가 앞 ex) a+b -> +ab Infix - 연산자가 중간 ex) a+b Postfix - 연산자가 뒤 ex ) a+b -> ab+ Infix는 컴퓨터에서 Parsing이 어려워(Tiebreaker, Delimiter등 필요) Prefix나 Postfix로 표현함 Postfix로 표현했을 경우 식을 왼쪽부터 오른쪽으로 읽어나가며 피연산자는 stack에 저장, 이 후 연산자가 나오면 스택에서 피연산자를 꺼내 연산하면 됨 Infix를 Postfix로 바꾸려면 식을 왼쪽에서 오른쪽으로 읽어나가면서, 피연산자는 그대로 Postfix식에 적음 ( 연산자는 연산자 stack에 push ) 연산자가 나오면 (가 나올 때 까지 stack..

문제 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example: Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 ..

문제 Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. Approach O(n^2)에 답 찾으면 답 리턴 좀 빠르게 만들어보려고 원래 nums[i] + nums[j] == target 대신 ta..