Message Digest는 간단히 말하면 Message Hashing이다.
- 단방향으로만 동작하고 역방향 유추는 불가.
- 암호 저장, file이 동일한 파일인지 비교하는데 쓰인다.
Java Ref - java.security.MessageDigest 존재.
좀 더 복잡하게 하기 위해서 Ref
Salting- 메시지 앞에 특수값을 삽입. (사용자별로 다르게 할 수도 있음)
Key Stretching- Digest하고 그 값을 또 Digest하는 multi-chain형태의 Digest.
=> 위 둘을 잘 섞어서 Adaptive Key Derivation Functions 이라고 부른다.
대표적인 게 PBKDF2랑 bcrypt, scrypt가 있다.
이 존재한다.
HTTP1.1이 현재까진 대세인데
HTTP2.0은 2015년 5월에 spec이 발표되었고, 대부분의 브라우저에서 2015년 말부터 지원한다.
- web site들은 10%미만이 이를 지원.
주요 특징.
- HTTP2.0 서버 Push
: 기존에는 index.html을 파싱하고 나사 style.css, javascript.js를 받지만, HTTP 2.0에서는 서버가 index.html 을 내려주면서 같이 css와 js도 내려줄 수 있다.
- HTTPS over TLS
:원래 https는 SSL기반인데, 2.0에서는 https가 TLS기반(SSL의 브랜치)으로 동작한다.
(SSL vs TLS: REF1, )
-같은 말이다. 네스케이프에 의해서 SSL이 발명되었고, 이것이 점차 폭넓게 사용되다가 표준화 기구인 IETF의 관리로 변경되면서 TLS라는 이름으로 바뀌었다. TLS 1.0은 SSL 3.0을 계승한다. 하지만 TLS라는 이름보다 SSL이라는 이름이 훨씬 많이 사용되고 있다.
( REF2-의심감)
SSL - 7.Application Layer 와 4.Transport Layer 간에서의 보안.
TLS - 서버인증은 선택사항, 반드시 공개키만 사용.
- SPDY (pronounced like "speedy") : TCP pipe는 쓰면서도 TCP와 다른프로토콜을 사용하는데 HTTP2.0 초기에는 SPDY방식으로 HTTP가 바뀔 것으로 제안 되다가 몇가지 문제가 있어 빠진 것으로 보임.
SOLID라고 부르며: 굿 REF
경험적으론 이미 다 아는 내용이긴 하지만,
다음과 같이 객체지향 5원칙을 정리한 사람들이 있다.. 글로 보니 새롭군요..
S- single responsibility principle
O- open-closed principle :
L- Liskov Substitution principle
- 어떤 함수 m(p)에서 P클래스의 p instance가 잘 동작하면, 그를 상속받은 C클래스의 c instance도 잘 동작해야 한다 m(c)
(일반적으로 잘 동작함. 하위 클래스에 부모에게 있는 method가 없거나 다른일을 하거나 하면 문제..)
I- interface segregation principle
- I/F는 가능한한 기능별로 세분화해서 구현해야 한다.
D- dependency Inversion principe
- 하위레벨 모듈의 변경이 상위레벨 모듈의 변경을 요구하던 관계를 끊음.
- 상위 클래스에서는 하위클래스 일들을 전혀 할 필요가 없다.
OSI 7계층을 아주 간단히 정리하면 다음과 같다.
7: Application Layer (응용 계층)
- 텔넷 등
6: Presentation Layer
- Encoding/Decoding 압축/암호화 등이 이루어지는 Layer이다.
5: Session Layer
- 운용 체제에서 다루어주는 TCP/IP 세션 생성 및 해제.
4: Transport Layer(트랜스포트 계층)
- 쉽게 TCP를 이용하는 계층이라고 보면 된다.
- End-to-End간 통신을 다루는 최하위 계층이다.
- 오류검출, 흐름제어, 중복검사 등이 이루어진다.
3: Network Layer
- IP와 라우팅 기반으로 데이타 통신이 이루어진다.
- 패킷 생성이 이루어지며, QoS관리 등이 이루어진다.
2: Data Link Layer (데이터 링크 계층)
- MAC Address 기반으로 통신을 하는 계층.
- CRC 체크등 에러체크 가 이루어 진다. (+재전송/흐름제어)
1: Physical Layer(물리계층)
- H/W Layer로서 가장 복잡한 계층이다.
<Self-Balanced Tree>
B-Tree: 2개 이상의 child를 가짐..
ㅁ 2-3 B-Tree (I think - 2 max, 3 Node)
Information (keys and associated data) is stored only at leaves
부모는 leftMax, middleMax를 저장. (left children's Max, middle children's Max)
Insert Operations: (value k)
(2가지 예외)
- T is empty일 때, 싱글 node with k 생성.
- T is 1 node(m) 일 때 : (1 parent, 2 child node로)
=> 1.node(n)k포함 생성,
2.new 내부node (with n,m are child node) 생성
+ leftMax,middleMax 세팅.
(general)
- insert(T,k)
ㅁ 2-3-4 Tree : 3개의 data와 4개의 child node를 가질 수 있다.
<Self-Balanced Binary Tree>
root는 블랙노드
레드노드(temp노드)가 항상 블랙child를 가짐.
삽입시에 레드노드를 삽입하는데, 레드-레드 될 경우 회전으로 해결.
특징: 최장거리 노드도 최단거리의 2배가 이하임.
AVL Tree: Refwiki - Height balanced 이진트리 - 각 two child간의 depth가 1 밖에 차이가 안남.
- depth가 좋으 므로 Red-Black Tree보다 탐색속도가 좋음.
- 특징: 4가지 회전 방식이 존재함 (할아버지 노드까지만 보면 됨)
LL/RR은 한번만 회전. LR/RL은 2번 회전.
- self balanced이면서 속도도 빠름. 이 역시 위 둘과 같이 회전으로 balancing.
- 최근 access한 값을 다시 access 할 수 있도록 배치.
- cache나 gc에 자주 쓰임.
- zig (parent root, x is child) , zig-zig (p!=root, p,x 같은 방향), zig-zag (p!=root p,x다른 방향) case 존재.
[기본 회전 알고리듬] Ref
Root Pv C A B
Pivot = Root.OS (O=Opposite side) Pivot설정. Root.OS = Pivot.RS (R= Rotate side) Pivot.RS를 1.detach Pivot.RS = Root Pivot.RS를 2.Set Root = Pivot Root설정.
Class aClass = MyObject.class Field field = aClass.getField("someField"); //for node : MyObject node = new MyObject(); Object value = field.get(node); field.set(node, value);
<other tree>
- Heap Tree와 비슷하게 min(or max)값이 제일 위에 있으나, complete tree가 아님.
- 한번 구성하면 끝날 듯( self balanced가 아님)
KD Tree : k dimensional Tree이다. left-child에 tree하나, right-child에 tree하나 가 관리되는데..
recurive하게 여러개의 tree가 계속 관리될 수 있다.
Huffman Tree: 압축알고리듬 허프만 코드- (확률빈도가 높은 char을 짧은 bit로 관리하는 코드 방식. )
를 생성할때 사용하는 binary Tree이다.
왼쪽이 0, 오른쪽이 1 간단하다. 빈도수가 낮은것부터 밑에서 tree를 만든다.
Heap Tree: complete binary tree (즉 포화트리에서 마지막 자식은 왼쪽노드부터 채움)
k 의 parent는 k/2; k의 2자식은 2k 와 2k + 1. (array로 구현하고 첫자리를 비움. array size는 2^(h+1) 이 되겠죠.)
최상위 root에는 최소값(Min Heap)이나 최대값(Max Heap)을 관리.
- complete binary tree는 배열로 관리 가능함. h로 관리되겠죠. 2^(h+1) -1 개가 max 노드개수임.
-Priority Queue 가 Heap으로 구현됨. (단, 이 때는 중복 허용)
insert: 일단 마지막 leaf에 넣고.. 자리바꾸기.
removeMax: 최상위 삭제하고, 마지막 leaft를 최상위로 배치.. (그 후 자리바꾸기)
java의 enum은 c처럼 간단한 enum기능에, 약간의 static class같은 기능이 추가되었다.
new를 해서 쓰지는 못하고, 상수에 value가 매핑되어 있는 형태로 사용가능하며
Serializable,Comparable, Runnable 모두 구현가능하다.
1. 간단한 java enum:
enum Day { MONDAY, TUESDAY, WEDNESDAY }
==> 항상 이값으로만 사용가능. c처럼 숫자로 자동 대체되지 않음.
2. enum에 value를 추가시:
enum Coin {
PENNY(1), NICKLE(5), DIME(10), QUARTER(25);
private int value;
private Coin(int v){
value = v;
}
public int getValue(){
return value;
}
//참고: toString()오버라이드 안해도 PENNY찍힘.
public String toString(){
return super.toString()+":"+value;
}
}
public class EnumTest {
public static void main(String args[]){
for(Coin c : Coin.values())
System.out.println(c.toString()); //오버라이드안하면 c = c.toString();
//비교시
if (c == Coin.DIME) { }
if (c.getValue() == Coin.DIME.getValue()) { }
}
}
3. enum에 value,color를 추가시:
enum Coin {
PENNY(1,"gold"), NICKLE(5,"white"), DIME(10,"silver"), QUARTER(25,"silver");
private int value;
private String color;
private Coin(int v, String c){
value = v;
color = c;
}
}
:: (Double colon) : reduce에서 standard에 맞으면 사용할 수 있는 연산자.
reduce( (int left, int right) -> Math.max(left, right) )
--> reduce(Math::max);
List의 각 항목을 제곱해서 출력하기:
LinkedList<Integer> list = new LinkedList<Integer>();
list.add(0); list.add(10);list.add(2);
list.stream()
.map( i -> i*i )
.forEach(System.out::println); //= forEach(i -> System.out.println(i));
Sum구하기:
int sum = list.stream()
.reduce(0, (x,y) -> x+y ); //identity(sum variable), Operation
각항목을 제곱한 LinkedList 만들기
LinkedList<Integer> list2 =
list.stream()
.map( i -> i*i )
.collect(Collectors.toCollection(LinkedList::new)); //.collect(Collectors.toList());
Merge sort(합병 소트): O(nlogn) 단점 O(n)스페이스 필요. Ref-Site
- 반씩 분할하는 divide & conquer 소트의 일종.
- merge_sort (int[] arr, int low, int high) {
int mid=0;
if (low < high) {
mid = (low+high) / 2;
merge_sort(arr, low, mid);
merge_sort(arr, mid+1, high);
merge(arr, low, mid, high); // 이 안에서 스페이스 필요.
}
}
- qSort는 최악에 O(n^2)이지만 실제로는 평균적으로는 qSort가 20%정도 빠르다고 함.
=> qSort 최악의 경우: pivot을 정할때.. pivot이 최대값이면.. 글케 됨.
Radix sort(̧기수 정렬) : Ref-Site
- O(pN) 이며, 2^20(백만개)정도의 숫자를 소팅할때 16진수로 한다고 치면 4자리 수이므로
4번 * N 정도로 할 수 있어 일반 정렬 O(n logn) = O(n * 20) 보다 훨씬 빠른 경우가 발생한다.
Insertion Sort(삽입 정렬): Ref-Site
- O(N^2) 이지만 구현이 매우 간단하고, 길이가 짤을 때 속도가 좋고 안정적이라는 장점이 있다.
c코드-참고
void insertion_sort (int *data, int n ) {
int i, j, remember;
for ( i = 1; i < n; i++ ) {
j=i;
remember = data[i];
while ( --j >= 0 && data[j] > remember)
data[j+1] = data[j]; //쭉 copy
data[j+1] = remember;
}
}
참고: 자바에서는 리스트의 기본 정렬 방식으로
1) Merge Sort를 사용하거나
2) tuned depending on the datatypes Quick Sort를 사용
+ 개체수가 7개 이하일 때 Insertion Sort 방식을 사용한다.
==============Data Structure=================
Heap: complete binary tree (즉 포화트리에서 마지막 자식은 왼쪽노드부터 채움)
최상위 root에는 최소값(Min Heap)이나 최대값(Max Heap)을 관리.
- complete binary tree는 배열로 관리 가능함. h로 관리되겠죠. 2^(h+1) -1 개가 max 노드개수임.
-Priority Queue 가 Heap으로 구현됨.
-median을 구하기에 가장 최적의 자료구조는
바로
Min Heap과 Max Heap을 동시에 하나씩 관리하는 것이다.
예를 들어 100까지의 숫자가 있다면 Max Heap으로 50까지 관리하고, Min Heap을 51부터 관리하면
median이 50 or 51 or 50.5 로 바로 구할 수 있다.
text 추천에 가장 많이 사용되는 변형된 Tree 로서, 마지막 노드에서만 숫자(접근빈도)를 관리한다.
- 일반적으로 Root에는 데이타를 관리하지 않으며, mutliNary tree이다.
- 마지막에 숫자를 관리하지 않아도 서치에는 유용하다. O(L)탐색, 생성은 O(M*L), M은 단어수, L은 가장 긴 단어길이.
참고:
HashTable : O(1+N/B) (B=bucket)
<Tree traverse>
java에서 binary tree는 간단히 node class로 구현이 된다.
그 후, traverse에는 2가지 방식이 있는데..
DFS: Depth First Search - 깊이 부터 서치하는 일반적인 방식.
이렇게 node로 구성된 BinaryTree 를 DFS로 traverse하는 방법에는 2가지가 있는데
1. recursive (좀 안좋은: 참고 )
출력은: printInOrder(node) {
if (node!=null) {
printInOrder(node.left);
System.out.println(node.value);
printInOrder(node.right);
}
2. loop 이용.. loop를 이용한 방법은 다음과 같다. myREF REF
주로 stack이용.
BFS: Breadth First Search - 같은 depth에 있는 형제들 먼저 출력. (아래코드 참조) -Queue이용.
q.add(root);
while (q.size() > 0) {
node = q.poll();
print ( node.value );
if (node.left != null) q.add( node.left);
if (node.right !=null) q.add (node. right);
}
<Direct Graph Traverse>
Dijkstra : Vertex(node)---edge---> w 로 갈 때 각 Edge마다 Weight가 있는 경우, 적합.
log(n^2)으로 vertex를 늘여가면서 가까운 Destination으로의 path를 찾아나간다.
핵심공식: distance[w] = min(distance[w], distance[u] + weight[u][w])
(아래 표 참조 1에서 출발:)
w S D(2) D(3) D(4) D(5)
1 S{1} 10 무한 30 100
2 S{1,2} 10 60 30 100
1에서 가까운 w를 하나씩 추가하면서 진행해 나가므로, 가까운 Vertex관리가 필요한데,
A. (Linked)adjacent List 로 관리하거나
B. priority Queue로 관리할 수 있다. (모든 Vertex에서 다해도 되지만, S 에 들어가는 거 위주로 해도 된다.)
BFS: tree에서 처럼 weight없이 탐색한다. 탐색방식은 Dijkstra와 근본적으로 같다.
<MST:min Spanning Tree> REF
Prim 알고리듬: O(n^2) => 보통 점만 주어질 땐, link가 많으므로 이럴때 적합.
- 노드 하나를 기준으로 그 외부와 연결되는 가장 min 값을 연결한다.
- 연결된 Set 과 그 외부 Set(외부를 전체 Set으로 보고) 또 가장 min 값을 연결한다.
(구현이 간단함)
내가 구현한 예제: disjointSet 이용.
int dist(int[] p1, int[] p2) {
return Math.abs(p1[0] - p2[0]) + Math.abs(p1[1] - p2[1]);
}
class Node {
int id; //1~5
int dist;
int pid1;
int pid2;
public Node(int pid1, int pid2,int id, int dist) {
this.pid1 = pid1;
this.pid2 = pid2;
this.id = id;
this.dist = dist;
}
}
/** MAIN */
public int minCostConnectPoints(int[][] points) {
if (points.length <= 1 ) return 0;
//4point case: 3*2 = 6개? (n-1!)
int N = points.length;
//20개 중 작은값 4개를 뽑아서 더하면 될듯. (단 이미연결된거 방지 체크)
//int dists[] = new int[ N * (N-1)];
PriorityQueue<Node> pq = new PriorityQueue<>(new Comparator<Node>() {
@Override
public int compare(Node n1, Node n2) {
return n1.dist - n2.dist;
}
}
);
//10개 노드: 4 + 3+ 2+ 1
int id = 0;
for (int i = 0; i < N-1; i++) {
for (int j = i+1; j < N; j++) {
Node node = new Node( i, j, id++, dist(points[i], points[j]));
pq.add(node);
}
}
System.out.println( "Total NODE: :" + id);
//필요 node는 (n-1)! -1 ///////////////////////
int k = N - 1;
int totDist = 0;
// HashSet<Integer> hs = new HashSet<>();
DjSet djSet = new DjSet(N);
while (pq.size() > 0) {
// while (k > 0) {
Node node = pq.poll();
System.out.println("node poll:" + k);
//TODO check.
if (!djSet.isConnected(node.pid1, node.pid2)) {
//add node.pid1, node.pid2
djSet.union(node.pid1, node.pid2);
totDist += node.dist;
k--;
}
//DjSet 도입이전 코드: 섬이 2개 생기면 이미 추가되어서 오류가 생김.
// if ( !hs.contains(node.pid1) || !hs.contains(node.pid2) ) {
// //System.out.println(node.dist + "," + node.pid1 + "," + node.pid2 + ",");
// hs.add(node.pid1);
// hs.add(node.pid2);
//
// totDist += node.dist;
// k--;
// }
}
return totDist;
}
구현에 DisjointSet(서로소 집합)과 union 이 필요할 것 같아서 링크 REF
/////////// DjSet: find, union, isConnected ////////////////////////////
class DjSet {
int[] parent;
int[] size;
public DjSet(int n) {
parent = new int[n];
size = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = i;
}
}
//find parent //////////////
int find(int x) { //union하면서 아직 update안된 parent들 udpate하면서 find
if (parent[x] != x) {
parent[x] = find(parent[x]); // 경로 압축: 부모를 찾아서 업데이트하면서 재귀적으로 호출
}
return parent[x]; // 노드 x의 부모 반환
}
boolean isConnected(int x, int y) {
return find(x) == find(y);
}
void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
if (size[rootX] > size[rootY]) parent[rootY] = rootX;
else if (size[rootX] < size[rootY]) parent[rootX] = rootY;
else {
parent[rootY] = rootX;
size[rootX]++;
}
}
}
구현에 DisjointSet(서로소 집합)과 union 이 필요할 것 같아서 링크 REF
Kruskal 알고리듬: O(eloge) - e 가 적당하다면 이 알고리듬이 훨씬 낫다.
- 일단 min Edge 들을 연결한다. (단 cycle이 안생기는 방식으로 연결)
- 마지막엔 Set 과 Set 간 연결들이 필요.
<TSP: Travelling Salesman Problem>
모든 노드를 한번씩만 돌아서 다 돌때 최소 weight 찾는 문제로, 일반적으로 알고리듬이 없다.
즉 모든 경우의 수를 다 해봐야 한다.
====Tree BFS code (순서없이 BFS Breadth First Search )======
위에 5줄이면 충분함. detail을 포함한 세부구현은 아래 더보기 참조.
class Node{
int value;
Node left;
Node right;
public Node (){
left=right=null;
}
public Node (int v){
value = v;
}
}
class Test {
/* DFS */
public void printInOrder(Node node){ //이함수는 DFS recursive test용 임.
if (node != null){
printInOrder(node.left);
out(":" +node.value);
printInOrder(node.right);
}
}
/* simple class for Marking a New Line in the Queue
*/
class NewLine extends Node{
}
/* print same depth nodes at the same line
* @param binTree : root Node of binary Tree
*/
public void printBFSTree(Node binTree){
if (binTree == null) return;
Queue<Node> queue = new LinkedList<Node>();
queue.add( binTree );
queue.add( new NewLine()); //depth seperator
while (queue.size() > 0){
Node node = queue.poll();
if ( node instanceof NewLine) { //(Depth changed)
System.out.println(); //print new Line
if (queue.size() > 0)
queue.add(node); //add NewLine for added sibling
}else { //(general Node)
//print Node's value
System.out.print(node.value + " ");
}
if (node.left != null) {
queue.add( node.left );
}
if (node.right != null) {
queue.add( node.right );
}
}
}
 by yongary |
||
|
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 | ||
| 6 | 7 | 8 | 9 | 10 | 11 | 12 |
| 13 | 14 | 15 | 16 | 17 | 18 | 19 |
| 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 | 31 |
