2-2

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으로 한 요소를 고르고, (거의 젤 마지막애로 설정함) (같거나?)작은건 왼쪽, (같거나..

0. 디자인 프로세스 1. miniworld설정 후 요구사항 분석~ (who? system analyst) 2. conceptual design ; 디비의 골격을 결정함 (사람이봤을때의 디자인) (DBMS이해불가) conceptual design - er model!! -high-level data model 3. logical design (data model mapping) ; DBMS가 이해가능! - 여기까지만 해도 ok. dbms에 원하는 골격 알려줄수 ㅇ logical(conceptual?) schema 4. physical design (internal schema) - 여기까지 하면 물리적으로 더 잘 돌릴 수 있ㄱㅔ 되겠죠? ER모델 ; er모델로 conceptual design(개념적 디자..

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보기로함

* unix : 유닉스(Unix)는 벨 연구소에서 개발한 운영 체제로, 대부분의 현대적 컴퓨터 운영 체제의 원형이 되었다. 윈도우를 제외한 리눅스, 안드로이드, macOS, iOS[1] 등의 대부분의 운영 체제가 유닉스를 그 뿌리로 하고 있다. 0. history bell lap에서 만듬 ,, 에디션 발전,, 1. 구조 architecture 커널 : 운영체제의 핵심. 쉽게 말해, 소프트웨어와 하드웨어간의 커뮤니케이션을 관리하는 프로그램(커널은 원래 하드웨어에 있다가, 부팅하면서 메인메모리 RAM으로 가져와진다. bootstrap ! 위에 초록색쓴거는 개소리가틈 쉘 : 사용자-운영체제 사이의 커뮤니케이션이 가능하도록 명령어를 해석해 줌 -> CLI(명령어. 커맨드라인) / GUI (그래픽기반) 이 있다(..

시스템 = 하드웨어 + 운영체제 : 하드웨어와 운영체제를 하나로 묶어서 시스템이라 할수 있음 (ex. A라는 시스템은 CPU가 Intel 기반이고 운영체제는 Windows이다.) 즉, 시스템 프로그램은 하드웨어와 운영체제를 기반으로 하는 시스템에서 동작하는 프로그램이라고 할 수 있다. -> 시스템 프로그래밍 - 컴퓨터 시스템을 만들거나 혹은 그것을 활용하는 프로그램의 개발 - 하위로는 펌웨어와 같은 하드웨어 프로그래밍, 상위로는 응용 프로그래밍이 있음 - 어떤 프로그래밍 범주에서도 이 개념이 기반이 됩니다. - 기본적으로 운영체제 바로 위에서, 운영체제(시스템)의 제공 기능을 십분 활용하는 프로그래밍입니다. ->시스템 프로그래밍이란 운영체제와 같은 커널 및 핵심 라이브러리를 직접 사용하여 하위 레벨에서 ..

* 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[..