What is the PKCS algorithm version of PostgreSQL?
tl;dr: pgcrypto는 PKCS#7을 사용한다. PostgreSQL의 pgcryto는 encrypt/decrypt에 padding을 어떤것으로 할 지 선택할 수 있도록 해주고 있다. 그런데 선택지에 대한 설명이 너무 부실하다. 선택지가 pkcs와 none이 있는데, none이야 아무것도...
Algorithm
Intractability
What is a general-purpose computer? Are there limits on the power of digital computers? Are there limits on the power of machines we can build? 컴퓨터 과학자들이 computation...
Problem Reduction
앞으로 남은 3챕터에서 배울 내용은 reduction, linear programming, intractability 이다. 따라서 지금까지의 관심에서 좀 벗어나 from individual problems to problem-solving models from linear / quadratic to polynomial /...
Data Compression
Data Compression 주된 이유는 전송 시간과 저장 공간을 절약하기 위해서다. 무어의 법칙이 말해주듯이 제품의 성능은 점점 좋아지는데, 그럼에도 불구하고 사람들이 만들어 내는 데이터의 양은 더 급격히 증가한다. 그래서...
Regular Expression, NFA
Regular Expression 이전까지 배웠던 패턴매칭 기법들은 모두 단일 패턴만을 찾았었. (e.g substring search) 일치하는 집합 을 원한다면 어떻게 해야할까? 예를 들어 유전자 분석에서는 Fragile X syndrome 은 GCG(CGG|AGG)*CTG...
Maximum Flow
Min Cut edge weighted 그래프에서 st-cut 이란 vertices 를 두개의 disjont sets 으로 나누는 것이다. 이때 s, t 는 각각 다른 집합 A, B 에 속해있다. (http://en.wikipedia.org) capacity...
Substring Search Algorithm
Intro to Substring Search N 길이의 텍스트에서 M 길이의 패턴을 찾는 문제다. 일반적으로 N >> M 이다. N 이 좀 많이 (무한히) 길기 때문에 지난시간까지 배운 알고리즘을 적용하기가...
R-way, Ternary Search Tries
String Symbol Table 지난 시간에 symbol-table 의 구현으로 red-black tree, hash table 의 성능을 살펴봤었다. red black tree 는 search, insertion, delete 에 compareTo 를 이용해 log N,...
Radix Sort, Suffix Sort
Strings in Java 문자열은 Character (문자) 의 나열이다. C 에서 하나의 캐릭터는 8-bit 인데, 자바의 경우에는 16-bit unsigned integer 로 표시한다. 스트링의 길이를 얻기 위해 length, 인덱싱 하기...
Graph Challenges, Minimum Spanning Trees, Shortest Paths
Graph Process Challenge 1 Is a graph bipartite? 그래프가 bipartite 인가 하는 문제는, 그래프의 노드를 이렇게 두 그룹으로 나눌 수 있느냐 하는 문제다. (http://en.wikipedia.org) 알고리즘이 얼마나 어려운가는 이렇게...
Hash Table, Universal Hashing, Bloom filters
Hash Table 해시 테이블의 연산은 key 를 이용해 이런 작업들을 한다. (1) insert: add new record (2) delete: delete existing record (2) lookup: check for a particular record...
Dijkstra, Heap, Red-Black Tree
Dijkstra's Shortest-Path Algorithm BFS 는 undirected graph 에서 최단 경로를 찾지만, 이건 모든 edge 의 길이가 1일때만 그렇다. 다익스트라(dijkstra, 데이크스트라) 알고리즘은 directed graph 에서 non-negative length 에 대한...
Graph Search and Connectivity
기본적인 그래프 탐색 방법 DFS, BFS 에 대해 배우고 약간씩 응용하여 shortest path, conncected components, topological order, strongly connected components 등을 찾는 방법을 배운다. 마지막 부분에선 웹이 어떻게...
Graphs, The Contraction Algorithm
이번엔 지난시간에 배운 randomized algorithm 을 새로운 domain 인 그래프에 적용해 보고, contraction algorithm 이 무엇인지 알아본다. Graphs 용어 정리부터 시작하자. edge (E) 는 pair of vertices 와...
Randomized Selection
Intuition 중복이 없는 n 개의 원소를 가진 배열에서 i 번째로 큰 원소를 얻고 싶다고 하자. 간단한 방법은 먼저 정렬을 한 뒤 거기서 i 번째 원소를 고르면 된다. 이...
Divide and Conquer
Divide and Conquer (분할 정복) 을 배운다. merge, quick sort 를 배우고 이 과정에서 왜 combine 단계가 O(n) 이 되어야 하는지 알아본다. 뒷부분에서는 Big O 뿐만 아니라 master...
Analysis of Algorithms
Analysis of Algorithms, by Kevin Wayne, Robert Sedgewick in Coursera 알고리즘을 분석해야 하는 이유는 (1) Predict performance (2) Compare algorithms (3) Provide guarantees (4) Understand theoretical basis 그...
Algorithm I, Chapter 1
Algorithm Part 1, Coursera Union Find Dynamic Connectivity N 개의 오브젝트가 있을때, Union command: connect two objects Find/connected query: is there a path connecting the two objects? 이렇게...
C++ 이진탐색트리(Binary Search Tree) 구현 및 설명
Binary Search Tre 이번 포스팅에서는 이진 탐색 트리(Binary Search Tree) 에 대해 알아보겠습니다. 이 글은 직접 작성했기 때문에 내용에 오류가 있을 수있습니다. 따라서 잘못된 내용이 있거나, 레퍼런스에 관해서...
C++ 정렬 알고리즘, Merge, Quick, Selection, Insert, Bubble, Heap
Stability 우선 A에 대해 정렬을 하고, 그 정렬된 결과를 바탕으로 B에 대해 정렬했을때 정렬 순서가 그대로 유지되는 알고리즘을 stable 하다고 합니다. merge 가 대표적인 stable 정렬, quick 이...