오래 못 할 짓 하지 않기

문제 1  1. Recursion Tree 그리기위와 같은 형태로 나온다. ● 특정 Level  a에서의 node의 개수 = 2^a 개 ● Tree 높이 = T(n)이 그 다음 단계에서 얼만큼 줄어드는지 보면 된다.  = T(n/2)                   = 이런 경우에 마지막 높이일 때 줄어들어 있는 정도는 [ n/2^마지막 높이 ] 일 것이다.                   →  n / 2^h = 1                    →  h = log2 n   ● 각 레벨별 합  lv 0 : cn log (n)  lv 1 : cn log (n/2)lv 2 : cn log (n/4)...lv h : cn log (n/2^log2 n) = cn * {..

프로세스 : 실행중인 프로그램 ● 현재 활동중인 상태의 프로세스는 PC값과 , Register들로 표현된다. ● 메모리에서 Process의 Layouts 1) 코드 영역 ( = 텍스트 영역) - [ 실행할 수 있는 코드 = 기계어로 이루어진 명령어 ] 가 저장되어 있다. - CPU가 실행할 명령어가 담긴St다. 2) 데이터 영역 - 프로그램이 실행되는 동안 유지할 데이터 저장 ex) 전역 변수 위에 나온 코드 영역 / 데이터 영역은 고정된 크기를 하는 즉, 메모리를 정적으로 할당하는 영역이다. ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ 3) 힙 영역 - 실행되는 동안 동적으로 공간이 할당되는 영역 → 낮은 주소에서 높은 주소로 할당 4) 스택 영역 - 데이터가 일시적으로 저장되..

● Recurrences : 현재 주어진 함수를 더 작은 함수로 쪼개서 설명하는 방법 방법 1) Substitution Method : 푸는 방법이라기보단 알고있는 게 맞다는 걸 증명하는 방법 방법 2) Recursion - tree : Recursion tree를 만든다. - 각각의 node는 또 다른 작은 문제를 담고있다. → 각 Level의 cost를 합한다. → 모든 Level의 cost를 합한다. 이거 직접 손으로 풀어보기 T(1)은 constant한 값이다. 트리에 있는 Node의 합을 구하기 위해서는 Height를 알아야 한다. 각 레벨마다 Sum을 구했으니 그걸 다 더한다. 각 층을 내려갈 때마다 c뒤에 붙는 것의 분모가 1/4이 됨. = 등비수열의 합 ▼ 풀이 더보기 방법 3) Itera..

OS Design and Implemetation ● User Goal = 사용하기 쉬워야 한다. ● System Goal = Design과 Implement, Maintain이 간편해야 한다. Design할 때 고려해야하는 것 ● Policy = 어떤 게 되어야 하는가? = What ● Mechanism = 어떻게 구현할 것인가? = How OS Structure ● Monolithic 특징 1) 단조로운 구조 , Hardware의 기능이 제한적임 특징 2) System program / Kernel 영역이 나누어져 있다. ● Layered Approach : 가장 중심부 ( layer 0 ) = Hardware 가장 높은 곳 ( layer N ) = User Interface 특징 1) 만들기 단순하..

SELECT { Attribute } FROM { Table } Where { Condition } 쿼리의 구조는 다음과 같다. Select나 가장 처음에 오는 부분에는 Attribute나 세부적인 데이터가 들어간다. FROM 뒤에는 사용/참조할 Table을 적고 Where 뒤에는 조건을 적는다. 이에 실행 순서들을 보면 From → Where → SELECT순서로 실행시킨다. From 에 있는 Table에서 ▶ Where Condition에 맞는 Tuple의 ▶ Attribute를 Select 해서 보여준다. Select 특) ● 정렬 안 함 ( Order by로 가능 ) ● 중복허용 ( DISTINCT 로 중복 제거 가능 ) 출력될 때 내가 원하는 Column 이름으로 바꿀 수 있음 Where a> ..

OS와 유저 사이 Interface 3가지 1. CLI ( Command Line Interface ) : shell 같이 커맨드 쳐서 띄우고 하는 거 2. GUI ( Graphical User Interface ) : Windows , 마우스 같은 거, 3. ( 비교적 새로 나온 거 ) Touch - Screen Interface : Android OS와 프로그램 사이에서의 Interface = System calls API : Application Programming Interface OS의 API = System call System calls의 위치는 다음과 같다. - System calls은 OS에서 사용가능하도록 만들어진 서비스를 이용할 수 있게 해준다. - OS 커널로 Function ca..

f(n) =< c g(n)이라고 할 때 5n^2 = O(n^3) 라고 가정하면 n과 c가 어떻게 되어야 하는가? 현재 형태를 식에 맞춰보면 0 ≤ 5n^2 ≤ c * n^3 이렇다. 0 ≤ f(n) ≤ c * g(n) c가 어떻게 되든 g(n)의 계수가 작아지지 않고 n이 어떤 상수가 되든 f(n)의 계수가 커지지 않으므로 답은 무수히 많다. 질문 : C도 고려를 해야하나? 상수는 떼고 그냥 차수만 생각하면 되는 거 아니었음? 2번 문제 풀기 전에 Notation 사이에 =가 있고 f(n) = g(n)이런 꼴이라면 → f(n)은 g(n) 노테이션 종류에 속한다. 1) O - O(n^3)는 5n^2보다 크거나 같다. 2) X - 위에 설명했으니 패스 3) n^2 + cn = O(n^2) 맞음 4) 5) 같..

OS란? Hardware와 유저 사이에서 일을 해주는 곳이라고 생각하면 된다. - OS 는 Kernel과 부가적인 프로그램으로 이루어져 있음. Operation Device Controller는 Local buffer를 가지고 있다. > 만약 출력장치에 필요한 정보들이 한 번에 들어가면 그것들은 처리하지 못한다. ex) 프린터기에 여러 명령 한꺼번에 넣기. 따라서 Device Controller가 Buffer에 담아두었다가 , 사용 가능하다는 신호(Interrupt)가 오면 그 때 하나씩 가져간다. Interrupt : 하드웨어나 소프트웨어에서 주의를 해달라고 알려주는 신호 Device(Hardware or Software) ↔ CPU ex) 사용자가 어떻게 해달라 , 어떤 일이 끝났거나 시작되어야 한다..

Network Data Model은 이렇게 만들 수 있다. DB 사용 초기에는 이런 방식으로 했는데, 화살표는 포인터로 구현되었다. 하지만 이렇게 하기에는 무엇보다 포인터가 너무 많아져서 사용하면서 꼬이는 게 많았다. 데이터 Entity의 계층구조를 이용하여 Pointer 개수를 줄여 사용한다. Schema와 그 안에 들어가는 Attribute들을 나타낸다. Relatioanl Data Model에서는 위와 같이 나타낸다. Table간의 관계를 먼저 나타내고, 아래에서 Attribute들의 관계를 나타낸다. 이 단계에서부터는 화살표가 pointer를 의미하지 않는다. Object - Oriented Data Model 자바에서 했던 거 생각하면 된다. Entity class를 만들어서 그와 관련된 Att..

함수 f(n)의 성능을 분석하는 방법으로는 다음과 같이 5개가 있다. 우리가 주로 볼 것은 Theta 와 Big - O 이다. ● Theta는 f(n)과 g(n)의 성능이 비슷비슷할 때를 의미하고 ● Big-O는 f(n)의 성능이 g(n)의 성능보다 같거나 낮을 때를 의미한다. n이 무한대일 때 [ f(n) / g(n) ] 의 값이 무한대가 아니라면 f(n) = O(g(n))이라고 할 수 있다. ( *예를 들어 f(n) = 2n^2 / g(n) = n^3 일 때 값은 0이다.) O-notation은 주로 f(n)의 upper bound를 나타낸다. 이거를 이해해보려면 O(n^2) 일 때 여기에 속하는 집합 f(n)으로는 { n^2 , 2n^2 -1 , 100n^2 , n , log n , }이 있다. n..