Hyun's Wonderwall

Greedy Algorithms 그리디 알고리즘: 각 단계에서 최적의 수를 찾아 전역 최적해를 구함.- ex) 수업 시간표 짜기: (1) 젤 빨리 끝나는 과목 먼저 신청 (2) 첫번째 과목 끝난후 시작해서 젤 빨리 끝나는 과목 신청- 그리디 알고리즘은 지역 최적해로 전역 최적해를 구하는 방식. DP로 얻은 최적해보다 덜 최적일 수 있음. Activity Selection Problem 행동 선택 문제- 입력: n개의 행동이 담긴 집합 S = {1,2,..n}. 시작 시간 si, 종료 시간 fi라 할때 행동 i는 [si,fi)를 차지함.- 목표: 호환가능한. 안겹치는 행동들로 최대 개수의 행동을 하기. (시간을 얼마나 쓰는진 고려대상x)S = { [1,4), [5,7), [2,8), [3,11), [8,1..

12.1동적 프로그래밍(DP): 격자(배열) 만들어 사용- 분할정복 DAC와의 비교: 문제를 부분 문제로 나누어 해결하는 것이 비슷.- DAC는 하위 문제들이 서로 독립적, DP는 서로 연관.- 하위 문제들이 겹침 -> DAC는 중복 계산하지만 DP는 table에 저장하는것으로 단 1번만 계산. DP 알고리즘 수립1. 최적해의 구조 특징을 찾는다.2. 최적해의 값을 재귀적으로 정의한다.3. 최적해의 값을 상향식(bottom-up)으로 정의한다.4. 계산된 정보들로부터 최적해를 구성한다. DP 알고리즘의 구성요소1. Optimal sub-structures 최적의 하위구조2. Overlapping sub-problems 겹치는 부분문제3. Memoization and reuse 메모이제이션과 재사용 Opt..

Red-black tree- 트리의 균형을 보장 -> 최악의 경우에도 O(lgn) 시간에 수행.- color 속성: red 또는 black. // BST에서 상속되는 속성 key, left, right, p- 리프노드(빈 트리)들은 흑색인 경계노드 T.nil. 널포인터 역할임 // T.nil.color=black.- 루트노드의 부모노드도 T.nil - key가 있으면(nil아니면) 다 내부노드, 모든 내부 노드는 자식 2개 가짐. (nil 리프는 보여지지 않을 뿐)- 맨밑 경계노드 T.nil 만이 리프노드=외부노드. 항상 흑색. RBT는 (BST에서의) NULL 대신 T.nil 가리켜 사용 레드블랙트리의 특성1. 모든 노드는 red거나 black이다.2. 루트 노드는 black이다.3. 모든 리프 노드(..

Binary Search Tree (BST, 이진검색트리)- 동적 집합 연산을 지원하는 자료구조. (search, minimum, predecessor, successor, insert, delete)- 수행시간이 트리의 높이에 비례: O(h)- 한 노드의 왼쪽, 오른쪽 자식노드도 각 서브트리의 루트가됨 -> 재귀적으로 이진탐색트리- 노드들이 연결된 자료구조. - root(T)가 T의 루트노드를 가리킨다. // p[root[T]]=NIL- null도, 노드가 1개여도 BST이다. - 각 노드가 포함하는 필드들: key, left(왼쪽 자식 노드의 포인터), right(오른쪽 자식 노드의 포인터), p(부모 노드의 포인터), satellite data(부속 데이터)- 루트 노드는 부모노드가 NIL인 유일한..

Entity Sets 개체 집합* An entity is an object that exists and is distinguishable from other objects.* An entity set is a set of entities of the same type that share the same properties.* entity는 a set of attributes로 나타나진다.ex. instructor = (ID, name, salary)* 속성들의 부분집합은 primary key를 만든다 -> set의 각 구성원들을 unique하게 식별한다.(테이블이 Entity set이고 튜플이 entity이다) ER Diagram에서 Entity set 표현하기- Rectangles = entity se..

전. 단일 셀 WLAN엑세스포인트가 Ethernet switch에 연결되어있고, 이더넷 스위치는 다른 이더넷 스위치에 합쳐지거나 bridge/router/switch로 연결될 수 있음.CM: 제어 모드, UM: 사용자 모드 다중 셀 WLAN같은 주파수대역 쓰면 interference. 주파수를 잘 정해서 써야함.- 여러 CM들이 Ethernet Switch에 연결됨.  Ad Hoc WLAN: central AP가 없음.  Wireless LAN에서 중요한 것들: throughput, 하나의 ap에 몇개의 노드 연결할 수 있는지, 백본 LAN에 연결, 얼마만큼 커버? 배터리? 전송? 보안?  옆에 있는 타 네트워크와의 operation은 어떤지. 라이센스 FREE이다. handoff/roaming 필요. ..

9. Wide Area Networks (WAN)10-11. Cellular Wireless Networks12-13. Local Area Networks (LAN)13-14. Ethernet14. Wireless LANS (Wifi 등) 이중 Ethernet부터 타이핑으로 정리한다.Ethernet Links by SpeedEthernet은 유선 연결이다.다양한 capacity - High Throughput 내는 것들이 많이 사용된다. Traditional Ethernet* 가장 이른 방식은 ALOHA - station은 아무떄나 프레임을 보낼 수 있었다. 동시에 보내면 충돌 발생. 재전송 전에 랜덤한 시간만큼 기다린다.* slotted ALOHA: time slot이 있는 ALOHA. 유용성 증가 C..

Accessing SQL from a Programming Language* DB 프로그래머가 general-purpose programming language를 써야 하는 이유1. SQL은 범용 프로그래밍 언어가 아니라 모든 쿼리를 표현할 수 없다.2. Non-declarative actions 은 sql로 수행될 수 없다.* two approaches to accessing SQL from a general-purpose programming language(1) A general-purpose program - can connect to and communicate with a database server using a collection of functions (ex. JDBC)(2) Embedd..

Joined Relations* Join operations는 두 개의 관계를 취하고 결과적으로 다른 관계를 반환.* join 연산은 두 관계의 튜플을 (어떤 조건하에서) 매치하는 카티젼곱이다. 또한 조인 결과 존재하는 속성들을 나타낸다.* join 연산은 from 절 안에 subquery expressions로 쓰인다. // FROM (... join ...)[3가지 조인 종류] (1) Natural join, (2) Inner join, (3) Outer join 1. Natural Join in SQL* natural join은 조인하는 테이블들의 모든 속성에 대해 동일한 속성(컬럼)이 존재하면 결과값에 하나만 남긴다.* 두 테이블 간 동일 이름, 동일 데이터 타입인 컬럼을 찾아서 조인 조건으로 설..

기말고사 범위 정리 Where Clause Predicates* SQL은 "between" 비교 연산자를 포함한다  ex. select * from i where salary between 90000 and 100000* 튜플 간 비교 -  select * from instructor i, teaches t where (i.ID, dept_name) = (teaches.ID, 'Biology'); Set Operations* A or B 찾기: 합집합. (select c_id from section where sem='Fall' and year=2017) union (select c_id from section  where sem='Spring' and year=2018)* A and B 찾기: 교집합...