전체 글 (177) 썸네일형 리스트형 6-3강 - Dynamic Programming 3 (the principal of optimality, 행렬 곱셈) 간혹 Dynamic Programming을 적용할 수 없는지 알아내는 방법이 바로 The Principle of Optimality입니다. cf> The Principle of Optimality instance 전체에서 optimal solution이면 → subinstance 한정해서도 optimal solution이어야 한다. 1> 예제 1 - P(s, t)가 shortest path -> P(s, w)와 P(w, t) 모두 shortest path (True) - reverse : P(s, w)와 P(w, t) 모두 shortest path -> P(s, t)가 shortest path (False) 2> 예제 2 - Floyd's shortest path problem Dk (i, j)가 i에서.. 6-2강 - Dynamic Programming 2 (최단거리 유형, 플로이드 알고리즘 ) 2. All Pairs Shortest Paths 0) 최단 경로 문제 유형 1> Shortest path finding problem u와 v간의 최단 경로 찾기 2> Single source all destination shortest path problem 하나의 출발점(single source)에서 각 정점(all destination)까지 도달하는데 (필요한 비용을 계산하여) 최단 경로들을 구합니다. 3> All pairs shortest paths problem 모든 점들간의 거리 중 최단거리(경로)를 구하는 문제 cf> 최단 경로 문제의 공통적인 solution step 1 : shortest path의 distance(cost)를 구하기step 2 : 그 distance(cost)를 가지는.. 6-1강 - Dynamic Programming 1 (DP, Binomial Coefficient) 0. Dynamic Programming (instance I [size는 n]이 있을 때,) 1) bottom-up 방식 - recursive property 1> bottom-up으로 cost 계산 instance I에 대한 optimal solution은 I의 sub-instance에 대한 optimal solution을 이용하여 푼다. 2> top-down으로 sol 구한다. sub-instance에 대한 cost를 모두 구해놓고 (bottom-up) 이들을 고려하여 다시 top-down으로 optimal solution을 구한다. 2) Programming = array(table) 1> Divide & Conquer와 다른 점 sub-instance들이 중복되며 solution을 구한다. 2>.. 5-1강 - Divide and Conquer 0 (Solving Recurrences Equations) 0. Solving Recurrences Equations 0) Solving Recurrences by Induction 이렇게 풀기는 너무 어렵습니다. 그래서 general term 구하는 다른 방법들에 대해 하나씩 알아보겠습니다. 1) Using Characteristic Equation - 문제 : Homogeneous Linear Recurrences 1> Theorem 1(서로 다른 근을 가지는 경우) → [1] r (r0 ~ r_k-1)에 관한 equation으로 만들고 r들(r0 ~r_k-1)을 구한다. → [2] 위 theorem에 따라 t_n을 만든다. → [3] t0 ~ t_k-1 초기값 대입 → [4] k개의 선형 연립 방정식을 통해 c1 ~ ck를 구한다. ( tn의 general.. 4-4강 - Combinational System Design 4 (ROM, PLA, PAL) 8. ROM 한 번 기록한 정보는 반영구적으로 기억되며 (첫 내용 작성에 특수 기기가 필요하고), 삭제나 수정이 불가능한 기억장치를 가리킨다. (동적으로 write할 수 없는 장비이다.) 1) 예시 (8-Word X 4-bit ROM) 8이라는 word가 들어가려면 3개의 input lines을 필요로 한다. (2^3 = 8) 4개의 output line을 가진다. 1> Truth Table 2> 회로 먼저 decoder로 3개 input을 8개의 minterm으로 변환한다. truth table을 기반으로 각 F_0~F_3을 minterm꼴로 나타낸다. 그리고 minterm을 기반으로 아래와 같이 switching element를 연결한다. 3> 장점 : 미리 만들어두고 빨리 구현할 수 있다. 4> 단.. 4-3강 - Combinational System Design 3 (Multiplexers, Bus) 6. Multiplexers 주어진 input에서 data가 1개만 나간다. select signal에 따라 ... 1) Multiplexers 0> 정의 : 주어진 input data 중에서 1개의 data를 선택해서 출력하는 회로 (Data Selector) 2^m개의 input이 있을 때, m개의 select signal의 조합으로 1개의 output을 출력하는 회로이다. 1> input : n (2m) 2> select signal : log2n (m) 3> output : 1 2) 예시 1> 2X1 Multiplexer - S = 0 → D_0~D_1 중에서 D_0 선택 - S = 1 → D_0~D_1 중에서 D_1 선택 2> 4X1 Multiplexer S_1과 S_0가 0 또는 1을 가지는 .. 4-2강 - Combinational System Design 2 (Adder/Subtractor, Decoder) 4. Adder/Subtractor select signal이라는 것을 이용해서 덧셈과 뺄셈을 모두 수행할 수 있게 한다. 1) 구성 1> input : A = a_n-1...a_0, B = b_n-1...b_0 2> select signal : S 3> output : F = f_n-1...f_0 2) select signal에 따른 연산 1> S=0 A와 B와의 덧셈을 수행 2> S=1 A와 (1+B')와의 덧셈을 수행 3) 회로도 1> select signal = 0 B가 원래 값 그대로 Adders/Subtractor에 들어갑니다. select signal은 0이 Adders/Subtractor에 들어갑니다. 수행 연산 : A + B 2> select signal = 0 B가 1과의 XOR 연산으.. [Java] 2-3강 - 객체 지향 프로그래밍 3 (Abstraction - Interface) cf> OOP의 4가지 특징 1) Encapsulation accesss modifier에 의해 필요한 것만 접근 가능하게 한다. 2) Abstraction interface : a specification without implementation (명세만 되어있고 구현되어 있지 않은) abstract classes (interface와 유사) 3) Inheritance 4) Polymorphism 4. Interface 1) Interface의 정의 만드려는 method에서 argument의 type이 매번 바뀌는 경우 method를 여러번 정의해야 할 수 있다. 이 때, implement(구체적 구현)없이 specification(method를 declare)을 하는 것을 interface라고 한다... 이전 1 2 3 4 5 6 7 8 ··· 23 다음
