ㅇTL

dynamic programming = big problem을 smaller prob로 쪼개는 것, 이때 각 정보를 re-use한다 (저장해두고 나중에 다시 사용함) 캐시한다 ~.~ (divide and conquer은 쪼개고 아래 정보들 다시 사용 xx. revisit안함) Assembly-line scheduling given: 두개(이상)의 assembly lines goal: fastest assembly time and path 구하기 -> 가장 빠른 path와 그때의 time을 찾는다 ! -> 이전 노드들에서 다음 노드로 가는 가장 빠른 웨이를 찾는 방식 알고리즘 설명 슈도코드 space constumption -> s: 2n, l:2n -> Θ(n) running time : 각 테이블에 한..

lower bounds for sorting - comparison sorts comparison sorts =비교만 사용하여 정렬하는 알고리즘 (heap sort, mergesort, insertion sort, selection sort, quick sort) -> worst case의 lowerbound는 (worst의 최소. 무조건이거보다는더안좋다) : Ω(nlgn) decision-tree model - comparisoin sort은 이 디시션 트리의 관점으로 볼 수 있따 ! (이게 기본개념) - 모든 친구들이 distinct라고 가정함 -> 이거보다 더 작은 worst running time가진 두가지 방법 소개 counting sort = comparision말고 counting을 사용하는..

quicksort = 분할 정복 알고리즘. (그대로 해결할 수 없는 문제를 작은 문제로 분할하여 문제를 해결하는 것) 1. 피벗 하나를 정해서 앞에는 피벗보다 작은걸 배치하고 뒤에는 피벗보다 큰아이들을 둔다 2. 피벗 앞부분에 대해 quicksort를 한다 3. 피벗 뒷 부분에 대해 quicksort를 한다 (맨 마지막에는 q=마지막 요소 전꺼, r=마지막 요소가 될 꺼고, 그담에는 p=q+1이되는데, 그럼 첫요소여야되는게 맨 마지막인덱스보다 같거나 커지니까 끝나도록함 !! p(맨처음이)>=r(맨마지막)보다 같거나 커지면 종료합니다 (걍 맨처음(p)가 r보다 작아야 실행합니다 ㄱ ) partition ! = pivot으로 한 요소를 고르고, (거의 젤 마지막애로 설정함) (같거나?)작은건 왼쪽, (같거나..

Heap 0. concepts 완전 이진트리의 일종 ( 완전 이진 트리란 마지막 레벨을 제외한 모든 레벨의 node가 완전히 채워져 있으며 마지막 레벨의 node들은 가능한 한 왼쪽부터 채워져 있는 구조를 말한다. ) 반 정렬 상태(느슨한 정렬 상태) 를 유지함. 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도! 걍 부모가 더 크다 종류 2개 ; max-heaps(부모가 자식보다 같거나 큰 것. root가 젤 큰애^^) , min-heaps(수업에서 x) ->array 저장 가능 array에 저장될 수 있다 레벨 순서대로 저장~ root = A[1] i 노드의 parent 인덱스 = i/2의 정수 (언더) (3/2 = 1) i 노드의 left 인덱스 = 2i i 노드의 right 인덱스 =..

: 러닝타임 식에 자기 자신이 또들어잇을 수 잇음 recursive~ -> 푸는 방법 (guess->증명 으로 푸는데, guess시에는 2쓰고 증명에는 1쓴다) 1. substitution method 2. recursion-tree method 3. master methond -> 목표 : Θ / O bound를 찾는 것 substitution methond 1. solution을 guess한다 (- guess할 때 recursion-tree method 사용함) 2. mathematical method (수학적 귀납법)으로 추측이 맞는지 증명한다 - basic or boundary condition 이 true인지 보여준다 - inductive step~ (n=어떨 때 성립한다고 가정 -> n일때 성..

-> 알고리즘이 얼마나 효율적인지 따져보기 위함 ! 0. 정리 (최고 차항만 비교하면 됨) 𝑂(𝑔) = g가 upper bound / worst case ! Θ(𝑔) = tight bound Ω(𝑔) = g가 lower bound / best case ! 1. O-natation (𝑂(𝑔)=f) -def : g(n) is asymptotic upper bound of f(n) = -ex (proof) 걍 pdf보기로함

* sorting 알고리즘 리스트를 입력받아서 increasing order로 된 순열 (걍 정렬된 리스트)를 리턴함 1. Insertion sort a. 원리 : 정렬된 쪽에 키를 하나씩 넣는다. 키 넣을 땐 정렬된 쪽의 젤 큰거부터 작은거까지 비교하면서 자리를 찾는다 -> 비교 대상이랑 키를 비교하고, 비교대상이 더 크면 비교대상을 뒤로 민다. 그리고 끝까지 이 과정을 하고 비어있는 자리 (i+1)에 저장해둔 키를 넣는다 b. pseudo code 슈도코드 INSERTION-SORT(A) for j=2 to A.length key=A[j] //key 저장해둠 i=j-1 //i는 비교 대상 while i>0 and A[i]>key //크면 그 큰친구를 오른쪽으로 밀고, 작으면 걍끝냄! A[i+1]=A[..