Hyun's Wonderwall

Minimum Spanning Tree- 무방향 연결 가중치 그래프. n개의 모든 정점 n-1개의 간선으로 연결.- MST는 유일하지 x 전체 트리의 가중치합.. GENERIC-MST -> A는 매 반복에서 선택된 안전간선들의 집합.A에 대해 safe edge (u,v)를 찾아서 A에 합한다. 그것을 A 가 최소신장트리 되기 전까지 반복GENERIC-MST(G,w) A 크루스칼(Kruskal) 알고리즘- forest를 이룸.- 가중치값 최소 간선 선택함. (cycle 생기지 않게)프림(Prim) 알고리즘- single tree가 계속 확장됨. (시작정점o)- 트리에 있지 않은 정점을 트리에 연결시키는 가중치값 최소 간선 선택함. Kruskal 알고리즘의 실행- 간선이 잇는 정점 이미 같은 집합 안에 있..

그래프 G = (V,E)- 정점 V, 간선 E.- 무방향, 방향 그래프- 차수: 인접 간선의 개수 (방향: in-degree, out-degree / 무방향: degree)- weighted graph 가중치 그래프- connected graph 연결 그래프. strongly connected 강연결 그래프.- 희소 sparse, 밀집 dense - 스택, 큐 그래프로 표현 가능 인접행렬 Adj[i][j]. Θ(V^2) 공간 필요인접리스트 Adj[v] = {1, 2}. Θ(V+E) 공간 필요. 시간복잡도 O(n)- 인접리스트 무방향이면 값 2번 있어야. 가중치그래프는 노드 (key,value) 로 구성.- |adj[v]| = out-degree 갯수 (각 정점의 외차수의 개수만큼 인접노드.)- 삭제랑 탐..

Huffman Codes 허프만 압축 (허프만 코드)- Binary character code. 각 문자는 고유 이진 문자열로 표현됨.* Fixed-length code: 고정길이 방식 (6개 문자 나타내는데 3bit 필요.)* Variable-length code: 가변길이 방식 (등장 빈도수 고려해 codeword 부여 가능. 자주등장-짧은 codeword. 굿) Prefix Codes: 어떤 codeword도 다른 codeword의 접두사가 아님- 인코딩과 디코딩에 용이. 각 문자를 나타내는 코드워드를 차례대로 concat하고 쪼개면 됨.  (인코딩) "abc" -> 0.101.100 = 0101100 | (디코딩) 001011101 = 0.0.101.1101 -> "aabe"- 문자는 이진트리의 ..

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인 유일한..

힙 정렬- 최악: O(nlgn)- 제자리 정렬.- Heap 자료구조 특징- Heapify(), BuildingHeap(), HeapSort()- 우선순위 큐 Heap 자료구조- 힙은 완전이진트리 (맨 마지막 level 제외 꽉 차있는 이진 트리)  - 트리는 무조건 부모/자식 단일 연결. 상향: 부모, 하향: 자식.- 배열로 구현된다. (노드에 1번부터 번호 붙어있. 삽입 순서=배열 인덱스. A[0] 안쓰는 경우로 설명함.)- root 노드 A[1]- i번째 노드 A[i]: 부모 노드 A[i/2], 왼쪽 자식 노드 A[2i], 오른쪽 자식 노드 A[2i+1] Heap 용어- 노드의 height: 리프부터 노드까지의 간선 개수- 트리의 height: 루트노드의 높이- 노드의 ..

재귀적인 탐색. Binary Search: (1) 분할 (2) 정복 (3) 결합 - 피보나치 수열 Binary Search Tree: 문제는 하나, 부분 문제들로 잘려진다. - 매 단계마다 찾는 key값과 중간값이 같은지 본다. (상수번 반복이라 Θ(1)) - (1) 같 = stop (2) 작 = 왼 sub arr, (3) 큼 = 오 sub arr - 시간복잡도 Θ(lgn) BST의 점화식 T(n) = T(n/2) + Θ(1) - 부분 문제의 개수 1개므로 a=1. - 부분 문제의 크기 n/2이므로 b=2 - 결합의 시간복잡도 Θ(1) 마스터정리 case 2. Θ(lgn) # 수도 코드 BinarySearch(A[1..N], value) { if (N == 0) return -1; // not found..

4-1. Recurrence 점화식 분할정복기법1. 분할, 2. 정복, 3. 결합 T(n) = { 1  // n = 1 (base case)             T(n-1) + 1 // n > 1 (recursion case)점화식의 해: T(n) = n T(n) = { 1 // n =1              2T(n/2) + n // n > 1점화식의 해: T(n) = nlgn + n 팩토리얼 예시 점화식의 관심사는 계산비용이다.T(n) = aT(n/b) + D(n) + C(n)* a개의 부분문제 (크기 n/b)* D(n): 분할하는 비용* C(n): 부분문제들의 답을 다시 결합하는 비용재귀적 알고리즘들은 점화식으로 표현될 수 있다. 점화식을 푸는 3가지 방법..