기확자와 기획서, 애증의 관계
http://minieetea.com/2014/07/archives/1903
자기전에 트위터 하다가 위의 글을 읽고 공감도 가고 생각나는 것들이 있어서 안자고 이렇게 글을...
회사에 사람이 조금씩 늘어나면서 자꾸 뭔가 프로세스를 만들려고 한다. 예를 들면, 이런거지. 기획 -> 디자인 -> 개발. 또한 하나를 할 때도 린하게 하기 보다는 큰 그림을 그리고 모든 것을 완벽(스스로 생각할 때 그렇겠지?)하게 한 다음에 진행을 하고 싶어들 하는 것 같다. 그런데, 난 이것에 반대의 입장이다. 세상에 완벽한게 있을까?(물론 애플은 뭘 내놓아도 참 잘 만들긴 하더라만). 특히나 멤버들의 능력이 엄청나게 뛰어나지 않은 상태에서는 절대 불가능할 것이다. 그러니 완벽하게 하려고 하면 할 수록 시간만 많이 잡아먹고 결국에는 그냥 무난한 또는 별거 아닌 결과만 나오게 된다고 생각한다.
나는 이것보다는 점진적으로 조금씩 무언가를 해나가는 것이 더 낫다고 생각한다.(린이 이런거지?) 회사에서 모바일 앱을 개발한다면 앱을 쓰다보면 불편한 점, 있으면 좋을 것 같은 기능들이 보일 것이다. 이것들을 그냥 바로바로 주위에 이야기 하는 거다. 개발자가 간단히 작업할 수 있는 일 같으면 개발자에게 바로 이야기해서 작업을 하도록 하고, 좀 더 심도있는 이야기가 필요할 것 같으면 스탠드업 미팅(이걸 한다면!) 같은 시간에 이야기를 꺼내어 관련된 사람들이 모여서 틀을 만들고, 간단하게 정리하고, 개발자는 그걸 구현하고, 베타 테스트를 하고, 반응이 좋으면 릴리즈를 하고 좋지 않으면 제거하고. 제거의 경우 시간낭비로 볼 수도 있겠지만 난 이러한 것들이 모여서 더 나은 발전을 이룰 수 있을 거라고 생각한다.
이렇게 어떤 생각이 떠올랐을 때 그걸 기획하고 디자인하고등등 너무 프로세스에 얽매이기 보다는 그냥 바로바로 만들어서 실제로 사용해 보는 것이 머리로만 고민하는 것 보다는 훨씬 더 빠르게 앱을 발전시킬 수 있다고 믿는다. 사용자의 피드백도 금방 얻을 수 있잖아?
2015년 7월 9일 목요일
2015년 6월 17일 수요일
BitMessage 분석
command, address version number, stream number, label, 개수, passphrase, hash값의 앞의 몇자리를 0x00으로 할 것인가, nonce trials per byte, payload length extra bytes
현재 최신 address version number는 4
nonce trials per byte는 현재 320이 최소, payload length exxtra bytes는 현재 1400이 최소
command: createChan, joinChan, createRandomAddress, createDeterministicAddress, getDeterministicAddress
address 만들기
1. 32bytes random으로 private signing key와 private encryption key를 만든다.
2. Elliptic Curve DSA 알고리즘 사용하여 public key 생성한다. 64bytes가 만들어진다.
3. 앞에서 생성된 두개(signing과 encryption)의 public key를 앞뒤로 붙인후(public signing key + public encryption key) sha512에 의한 hash를 구한다.
4. 구해진 digest를 가지고 ripemd160에 의한 hash를 구한다.
5. ripe.digest의 앞자리(1 or 2)가 0x00일 때까지 반복한다.(address의 크기를 줄이기 위한 작업)
6. address version number의 인코딩 + stream number의 인코딩 + ripe.digest
7. verify를 위해 앞의 값에 sha512를 두번 적용한 후 앞의 4bytes를 checksum으로 사용한다.
8. (6에서의 값의 hex + 7에서의 checksum의 hex) 를 integer로 변경한다.
9. integer를 base58로 인코딩한다.
10. 앞에 BitMessage를 의미하는 BM-를 덧붙인다.
양의 정수 인코딩하기
1. 253보다 작으면 big endian unsigned char
2. 253에서 65535(2^16)사이이면 (>B, 253) + >H unsigned short
3. 65536에서 2^32사이이면 (>B, 254) + >I unsigned int
4. 2^32에서 2^64사이이면 (>B, 255) + >Q unsigned long long
5. 2^64보다 큰 수는 없다.
Wallet Import Format
1. 0x80 + private key
2. sha256을 두번 적용한 hash를 구한다.
3. hash된 결과의 앞 4bytes를 checksum으로 사용한다.
4. 1의 끝에 checksum을 추가한다.
5. base58로 인코딩한다.
signature 계산
expires time + object type + address version number + stream number + tag + 0x00000001 + public signing key + public encryption key + nonce trials per byte + payload length extra bytes
위의 내용을 private signing key로 sign한 것이 signature이다.
encrypted 계산
0x00000001 + public signing key + public encryption key + nonce trials per byte + payload length extra bytes + signature의 length + signature
위의 내용을 address의 double hash의 앞 32bytes로 암호화 한다.
실제 다른 node에 전달되는 값은 아래와 같다.
payload = POW에 의해 계산된 nonce + expires time + object type + address version number + stream number + tag + encrypted
inventoryhash: payload에 sha512를 두번 적용한 hash의 앞 32bytes
inventoryhash -> object type, stream number, payload, expires time, tag)
현재 최신 address version number는 4
nonce trials per byte는 현재 320이 최소, payload length exxtra bytes는 현재 1400이 최소
command: createChan, joinChan, createRandomAddress, createDeterministicAddress, getDeterministicAddress
address 만들기
1. 32bytes random으로 private signing key와 private encryption key를 만든다.
2. Elliptic Curve DSA 알고리즘 사용하여 public key 생성한다. 64bytes가 만들어진다.
3. 앞에서 생성된 두개(signing과 encryption)의 public key를 앞뒤로 붙인후(public signing key + public encryption key) sha512에 의한 hash를 구한다.
4. 구해진 digest를 가지고 ripemd160에 의한 hash를 구한다.
5. ripe.digest의 앞자리(1 or 2)가 0x00일 때까지 반복한다.(address의 크기를 줄이기 위한 작업)
6. address version number의 인코딩 + stream number의 인코딩 + ripe.digest
7. verify를 위해 앞의 값에 sha512를 두번 적용한 후 앞의 4bytes를 checksum으로 사용한다.
8. (6에서의 값의 hex + 7에서의 checksum의 hex) 를 integer로 변경한다.
9. integer를 base58로 인코딩한다.
10. 앞에 BitMessage를 의미하는 BM-를 덧붙인다.
양의 정수 인코딩하기
1. 253보다 작으면 big endian unsigned char
2. 253에서 65535(2^16)사이이면 (>B, 253) + >H unsigned short
3. 65536에서 2^32사이이면 (>B, 254) + >I unsigned int
4. 2^32에서 2^64사이이면 (>B, 255) + >Q unsigned long long
5. 2^64보다 큰 수는 없다.
Wallet Import Format
1. 0x80 + private key
2. sha256을 두번 적용한 hash를 구한다.
3. hash된 결과의 앞 4bytes를 checksum으로 사용한다.
4. 1의 끝에 checksum을 추가한다.
5. base58로 인코딩한다.
signature 계산
expires time + object type + address version number + stream number + tag + 0x00000001 + public signing key + public encryption key + nonce trials per byte + payload length extra bytes
위의 내용을 private signing key로 sign한 것이 signature이다.
encrypted 계산
0x00000001 + public signing key + public encryption key + nonce trials per byte + payload length extra bytes + signature의 length + signature
위의 내용을 address의 double hash의 앞 32bytes로 암호화 한다.
실제 다른 node에 전달되는 값은 아래와 같다.
payload = POW에 의해 계산된 nonce + expires time + object type + address version number + stream number + tag + encrypted
inventoryhash: payload에 sha512를 두번 적용한 hash의 앞 32bytes
inventoryhash -> object type, stream number, payload, expires time, tag)
2015년 6월 10일 수요일
쉽게 배우는 알고리즘 9장 요약
Chapter 9. 그래프 알고리즘
1. 그래프
그래프: 현상이나 사물을 정점과 간선으로 표현하는 것
정점(Vertex): 대상이나 개체
간선(Edge): 이들간의 관계
사람들간의 친밀도를 나타내는 경우를 그래프로 표시한다면, 정점은 각각의 사람이 되고, 간선은 친밀한 사람들 사이를 선으로 연결한 것이 될 것이다.
간선에 숫자를 표시하여 친밀도의 크기를 표시할 수도 있고, 화살표로 방향을 줄 수도 있다. 방향을 가진 그래프를 유향 그래프(Directed Graph)라고 하고 방향이 없는 그래프를 무향 그래프(Undirected Graph)라고 한다.
n개의 정점의 집합 V와 이들간에 존재하는 간선의 집합 E로 구성된 그래프 G를 보통
G = (V, E)
로 표시한다.
2. 그래프의 표현
2.1 인접행렬을 이용한 방법
그래프 G=(V,E)에서 정점의 총수가 n이라 하자 nXn 행렬을 준비한다. 정점 i와 정점 j간에 간선이 있으면 행렬의 (i,j)원소와 (j,i)원소의 값을 1로 할당한다. 가중치가 있는 경우는 1 대신 가중치를 할당하고 방향이 있는 경우는 방향에 맞게 값을 할당한다.
행렬 표현법은 n^2의 공간이 필요하고 행렬의 공간을 채우는데 n^2에 비례하는 시간이 걸린다. 따라서, 간선의 밀도가 높은 그래프에서는 좋지만 그렇지 않는 경우는 좋지 않다.
2.2 인접리스트를 이용한 방법
각 정점마다 리스트를 만든다. 각 정점에 인접한 정점들을 연결 리스트(linked list)로 매단다.
단순관계 그래프에서 리스트는 <정점번호, 다음 정점의 포인터>로 표시될 수 있고 가중치를 가진 그래프에서 리스트는 <정점번호, 가중치, 다음 정점의 포인터>로 표시될 수 있다.
3. 너비우선탐색(BFS)과 깊이우선탐색(DFS)
3.1 BFS
루트의 자식을 차례로 방문한다. 다음으로 루트 자식의 자식의 정점을 방문한다. 이런식으로 루트에서의 거리 순으로 방문한다.
BFS의 수행시간은 Theta(V+E)이다.
// G: 그래프
// s: 시작정점
BFS(G, s)
{
// s를 제외한 모든 정점을 NO로 표시한다.
for each v in V -{s} {
visited[v] = NO;
}
visited[s] = Yes;
enqueue(Q,s);
while (Q가 비어 있지 않으면) {
u = dequeue(Q);
for each v in L(u) // 정점 u의 인접 리스트
if (visited[v] == NO) {
visited[v] = YES;
enqueue(Q,v);
}
}
}
}
3.2 DFS
루트의 자식 정점을 하나 방문한 다음, 아래로 내려갈 수 있는 곳까지 내려간다. 더이상 내려갈 수가 없으면 위로 되돌아오다가 내려갈 속이 있으면 즉각 내려간다.
DFS의 수행시간은 Theta(V+E)이다.
DFS(G)
{
for each v in V {
visited[v] = NO;
}
for each v in V {
if (visited[v] == NO) {
aDFS(v)
}
}
}
aDFS(v)
{
visited[v] = YES;
for each x in L(v) { // L(v): 정점 v의 인접리스트
if (visited[x] == NO) {
aDFS(x);
}
}
}
4. 최소신장트리(Minimum Spanning Tree)
간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리를 최소신장트리라 한다.
4.1 프림 알고리즘
집합 S를 공집합에서 시작하여 모든 정점을 포함할 때까지 키워 나간다.
d에 대한 자료구조는 최소힙을 사용하면 시간을 개선할 수 있다.
수행시간은 O(E*logV)가 된다.
// G(V,E): 주어진 그래프
// r: 시작 정점
Prim(G, r)
{
S는 공집합
// 시작정점 r의 연결비용은 0으로하고 나머지 정점들의 연결비용은 무한대로 초기화한다.
for each u in V {
d[u] = 무한대
}
d[r] = 0;
while (S != V) {
u = extractMin(V-S, d);
S = S + [u]; // 집합 S에 u를 포함시킨다.
for each v in L(u) { // L(u): u의 인접 정점 집합
if (v in V-S && w(u,v) < d[v]) {
d[v] = w(u,v);
tree[v] = u;
}
}
}
}
extractMin(Q, d[])
{
집합 Q에서 d값이 가장 작은 정점 u를 리턴한다.
}
4.2 크루스칼 알고리즘
싸이클을 만들지 않는 범위에서 최소 비용 간선을 하나씩 더해가면서 최소신장트리를 만든다.
집합의 처리 방법으로 랭크를 이용한 Union과 경로압축을 이용한 Find-Set을 사용하면 시간을 아낄 수 있다.
수행시간은 O(E*logV)가 된다.
Kruskal(G)
{
T는 공집합
단 하나의 정점만으로 이루어진 n개의 집합을 초기화한다.
모든 간선을 가중치의 크기순으로 정렬하여 배열 A[1...E]에 저장한다.
while (T의 간선수 < n - 1) {
A에서 최소비용의 간선(u,v)를 제거한다.
if (정점 u와 v가 다른 집합에 속함) {
T = T + (u,v);
정점 u와 v가 속한 두 집합을 하나로 합친다.;
}
}
}
5. 위상 정렬
싸이클이 없는 유향 그래프 G=(V,E)에서 V의 모든 정점을 정렬하되 다음 성질을 만족해야 한다.
- 간선 (i,j)가 존재하면 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 나열되어야 한다.
topologicalSort(G)
{
for each v in V {
visited[v] = NO;
}
for each v in V {
if (visited[v] == NO) {
DFS-TS(v);
}
}
}
DFS-TS(v)
{
visited[v] = YES;
for each x in L(v) {
if (visited[x] == NO) {
DFS-TS(x);
}
}
연결 리스트 R의 맨 앞에 정점 v를 삽입한다.
}
6. 최단경로
6.1 다익스트라 알고리즘(음의 가중치를 허용하지 않는 경우)
// G=(V,E): 주어진 그래프
// r: 시작으로 삼을 정점
Dijkstra(G, r)
{
S는 공집합
for each u in V {
d[u] = 무한대
}
d[r] = 0;
while (S != V) {
u = extractMin(V-S, d);
S = S + {u};
for each v in L(u) {
if (v in V-S && d[u] + w(u,v) < d[v]) {
d[v] = d[u] + w(u,v);
prev[v] = u;
}
}
}
}
extractMin(Q, d[])
{
집합 Q에서 d값이 가장 작은 정점 u를 리턴한다.
}
6.2 벨만-포드 알고리즘(음의 가중치를 허용하는 경우)
BellmanFord(G, r)
{
for each u in V {
d[u] = 무한대;
}
d[r] = 0;
for (int i=0; i<V; i++) {
for each (u,v) in E {
if (d[u] + w(u,v) < d[v]) {
d[v] = d[u] + w(u,v);
prev[v] = u;
}
}
}
// 음의 싸이클 존재여부 확인
for each (u,v) in E {
if (d[u] + w(u,v) < d[v]) {
output "해없음"
}
}
}
6.3 모든쌍 최단경로 알고리즘
d.k(ij) : 정점 집합 {1,2, ..., k}에 속하는 정점들만을 중간 정점으로 거쳐서 i에서 j에 이르는 최단거리
d.k(ij) = w(ij) if k=0
min(d.k-1(ij), d.k-1(ik) + d.k-1(kj)) if k>=1
FloydWarshall(G)
{
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
d(ij) = w(ij);
}
}
for (int k=1; k<=n; k++) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
d.k(ij) = min(d.k-1(ij), d.k-1(ik) + d.k-1(kj));
}
}
}
}
6.4 싸이클이 없는 그래프의 최단경로
DAG-ShortestPath(G, r)
{
for each u in V {
d[u] = 무한대;
}
d[r] = 0;
G의 정점들을 위상정렬한다.
for each u in V { // 위상정렬 순서대로
for each v in L(u) {
if (d[u] + w(u,v) < d[v]) {
d[v] = d[u] + w(u,v);
prev[v] = u;
}
}
}
}
7. 강연결요소
유향 그래프 G=(V,E)에서 V의 모든 정점쌍 (u,v)에 대해서 경로 u ~> v와 경로 v ~> u가 존재하면 그래프 G는 강하게 연결되었다고 말한다.
그래프에서 강하게 연결된 부분 그래프들을 각각 강연결요소라고 한다.
// f[v]: DFS를 수행하면서 v에 관한 한 더이상 할 일이 없는 상태가 된 시점
stronglyConnectedComponent(G)
{
그래프 G에 대해 DFS(G)를 수행하여 각 정점 v의 완료시간 f[v]를 계산한다.
G의 모든 간선들의 방향을 뒤집어 G(R)을 만든다.
DFS(G(R))을 수행하되 앞에서 구한 f[v]가 가장 큰 정점을 시작점으로 잡는다.
앞에서 만들어진 분리된 트리들 각각을 강연결요소로 리턴한다.
}
1. 그래프
그래프: 현상이나 사물을 정점과 간선으로 표현하는 것
정점(Vertex): 대상이나 개체
간선(Edge): 이들간의 관계
사람들간의 친밀도를 나타내는 경우를 그래프로 표시한다면, 정점은 각각의 사람이 되고, 간선은 친밀한 사람들 사이를 선으로 연결한 것이 될 것이다.
간선에 숫자를 표시하여 친밀도의 크기를 표시할 수도 있고, 화살표로 방향을 줄 수도 있다. 방향을 가진 그래프를 유향 그래프(Directed Graph)라고 하고 방향이 없는 그래프를 무향 그래프(Undirected Graph)라고 한다.
n개의 정점의 집합 V와 이들간에 존재하는 간선의 집합 E로 구성된 그래프 G를 보통
G = (V, E)
로 표시한다.
2. 그래프의 표현
2.1 인접행렬을 이용한 방법
그래프 G=(V,E)에서 정점의 총수가 n이라 하자 nXn 행렬을 준비한다. 정점 i와 정점 j간에 간선이 있으면 행렬의 (i,j)원소와 (j,i)원소의 값을 1로 할당한다. 가중치가 있는 경우는 1 대신 가중치를 할당하고 방향이 있는 경우는 방향에 맞게 값을 할당한다.
행렬 표현법은 n^2의 공간이 필요하고 행렬의 공간을 채우는데 n^2에 비례하는 시간이 걸린다. 따라서, 간선의 밀도가 높은 그래프에서는 좋지만 그렇지 않는 경우는 좋지 않다.
2.2 인접리스트를 이용한 방법
각 정점마다 리스트를 만든다. 각 정점에 인접한 정점들을 연결 리스트(linked list)로 매단다.
단순관계 그래프에서 리스트는 <정점번호, 다음 정점의 포인터>로 표시될 수 있고 가중치를 가진 그래프에서 리스트는 <정점번호, 가중치, 다음 정점의 포인터>로 표시될 수 있다.
3. 너비우선탐색(BFS)과 깊이우선탐색(DFS)
3.1 BFS
루트의 자식을 차례로 방문한다. 다음으로 루트 자식의 자식의 정점을 방문한다. 이런식으로 루트에서의 거리 순으로 방문한다.
BFS의 수행시간은 Theta(V+E)이다.
// G: 그래프
// s: 시작정점
BFS(G, s)
{
// s를 제외한 모든 정점을 NO로 표시한다.
for each v in V -{s} {
visited[v] = NO;
}
visited[s] = Yes;
enqueue(Q,s);
while (Q가 비어 있지 않으면) {
u = dequeue(Q);
for each v in L(u) // 정점 u의 인접 리스트
if (visited[v] == NO) {
visited[v] = YES;
enqueue(Q,v);
}
}
}
}
3.2 DFS
루트의 자식 정점을 하나 방문한 다음, 아래로 내려갈 수 있는 곳까지 내려간다. 더이상 내려갈 수가 없으면 위로 되돌아오다가 내려갈 속이 있으면 즉각 내려간다.
DFS의 수행시간은 Theta(V+E)이다.
DFS(G)
{
for each v in V {
visited[v] = NO;
}
for each v in V {
if (visited[v] == NO) {
aDFS(v)
}
}
}
aDFS(v)
{
visited[v] = YES;
for each x in L(v) { // L(v): 정점 v의 인접리스트
if (visited[x] == NO) {
aDFS(x);
}
}
}
4. 최소신장트리(Minimum Spanning Tree)
간선들이 가중치를 갖는 그래프에서 간선 가중치의 합이 가장 작은 트리를 최소신장트리라 한다.
4.1 프림 알고리즘
집합 S를 공집합에서 시작하여 모든 정점을 포함할 때까지 키워 나간다.
d에 대한 자료구조는 최소힙을 사용하면 시간을 개선할 수 있다.
수행시간은 O(E*logV)가 된다.
// G(V,E): 주어진 그래프
// r: 시작 정점
Prim(G, r)
{
S는 공집합
// 시작정점 r의 연결비용은 0으로하고 나머지 정점들의 연결비용은 무한대로 초기화한다.
for each u in V {
d[u] = 무한대
}
d[r] = 0;
while (S != V) {
u = extractMin(V-S, d);
S = S + [u]; // 집합 S에 u를 포함시킨다.
for each v in L(u) { // L(u): u의 인접 정점 집합
if (v in V-S && w(u,v) < d[v]) {
d[v] = w(u,v);
tree[v] = u;
}
}
}
}
extractMin(Q, d[])
{
집합 Q에서 d값이 가장 작은 정점 u를 리턴한다.
}
4.2 크루스칼 알고리즘
싸이클을 만들지 않는 범위에서 최소 비용 간선을 하나씩 더해가면서 최소신장트리를 만든다.
집합의 처리 방법으로 랭크를 이용한 Union과 경로압축을 이용한 Find-Set을 사용하면 시간을 아낄 수 있다.
수행시간은 O(E*logV)가 된다.
Kruskal(G)
{
T는 공집합
단 하나의 정점만으로 이루어진 n개의 집합을 초기화한다.
모든 간선을 가중치의 크기순으로 정렬하여 배열 A[1...E]에 저장한다.
while (T의 간선수 < n - 1) {
A에서 최소비용의 간선(u,v)를 제거한다.
if (정점 u와 v가 다른 집합에 속함) {
T = T + (u,v);
정점 u와 v가 속한 두 집합을 하나로 합친다.;
}
}
}
5. 위상 정렬
싸이클이 없는 유향 그래프 G=(V,E)에서 V의 모든 정점을 정렬하되 다음 성질을 만족해야 한다.
- 간선 (i,j)가 존재하면 정렬 결과에서 정점 i는 반드시 정점 j보다 앞에 나열되어야 한다.
topologicalSort(G)
{
for each v in V {
visited[v] = NO;
}
for each v in V {
if (visited[v] == NO) {
DFS-TS(v);
}
}
}
DFS-TS(v)
{
visited[v] = YES;
for each x in L(v) {
if (visited[x] == NO) {
DFS-TS(x);
}
}
연결 리스트 R의 맨 앞에 정점 v를 삽입한다.
}
6. 최단경로
6.1 다익스트라 알고리즘(음의 가중치를 허용하지 않는 경우)
// G=(V,E): 주어진 그래프
// r: 시작으로 삼을 정점
Dijkstra(G, r)
{
S는 공집합
for each u in V {
d[u] = 무한대
}
d[r] = 0;
while (S != V) {
u = extractMin(V-S, d);
S = S + {u};
for each v in L(u) {
if (v in V-S && d[u] + w(u,v) < d[v]) {
d[v] = d[u] + w(u,v);
prev[v] = u;
}
}
}
}
extractMin(Q, d[])
{
집합 Q에서 d값이 가장 작은 정점 u를 리턴한다.
}
6.2 벨만-포드 알고리즘(음의 가중치를 허용하는 경우)
BellmanFord(G, r)
{
for each u in V {
d[u] = 무한대;
}
d[r] = 0;
for (int i=0; i<V; i++) {
for each (u,v) in E {
if (d[u] + w(u,v) < d[v]) {
d[v] = d[u] + w(u,v);
prev[v] = u;
}
}
}
// 음의 싸이클 존재여부 확인
for each (u,v) in E {
if (d[u] + w(u,v) < d[v]) {
output "해없음"
}
}
}
6.3 모든쌍 최단경로 알고리즘
d.k(ij) : 정점 집합 {1,2, ..., k}에 속하는 정점들만을 중간 정점으로 거쳐서 i에서 j에 이르는 최단거리
d.k(ij) = w(ij) if k=0
min(d.k-1(ij), d.k-1(ik) + d.k-1(kj)) if k>=1
FloydWarshall(G)
{
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
d(ij) = w(ij);
}
}
for (int k=1; k<=n; k++) {
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) {
d.k(ij) = min(d.k-1(ij), d.k-1(ik) + d.k-1(kj));
}
}
}
}
6.4 싸이클이 없는 그래프의 최단경로
DAG-ShortestPath(G, r)
{
for each u in V {
d[u] = 무한대;
}
d[r] = 0;
G의 정점들을 위상정렬한다.
for each u in V { // 위상정렬 순서대로
for each v in L(u) {
if (d[u] + w(u,v) < d[v]) {
d[v] = d[u] + w(u,v);
prev[v] = u;
}
}
}
}
7. 강연결요소
유향 그래프 G=(V,E)에서 V의 모든 정점쌍 (u,v)에 대해서 경로 u ~> v와 경로 v ~> u가 존재하면 그래프 G는 강하게 연결되었다고 말한다.
그래프에서 강하게 연결된 부분 그래프들을 각각 강연결요소라고 한다.
// f[v]: DFS를 수행하면서 v에 관한 한 더이상 할 일이 없는 상태가 된 시점
stronglyConnectedComponent(G)
{
그래프 G에 대해 DFS(G)를 수행하여 각 정점 v의 완료시간 f[v]를 계산한다.
G의 모든 간선들의 방향을 뒤집어 G(R)을 만든다.
DFS(G(R))을 수행하되 앞에서 구한 f[v]가 가장 큰 정점을 시작점으로 잡는다.
앞에서 만들어진 분리된 트리들 각각을 강연결요소로 리턴한다.
}
쉽게 배우는 알고리즘 8장 요약
Chapter. 8 동적 프로그래밍
1. 어떤 문제를 동적 프로그래밍으로 푸는가
동적 프로그래밍은 큰 문제의 해답에 작은 문제의 해답이 포함되어 있고 이를 재귀호출 알고리즘으로 구현하면 지나친 중복이 발생하는 경우에 이 재귀적 중복을 해결하는 방법을 말한다.
다음의 두 성질을 갖고 있는 문제에 대해 동적 프로그래밍이 적합하다.
a. 최적 부분구조를 이룬다.
b. 재귀적으로 구현했을 때 중복 호출로 심각한 비효율이 발생한다.
2. 행렬 경로 문제
nxn행렬의 죄상단에서 시작해 한 칸씩 이동해 우하단까지 도달한다. 이 과정에서 방문한 칸에 있는 수들을 더한 값이 이 경로의 합이다. 이동상의 규칙은 아래와 같다.
- 오른쪽이나 아래쪽으로만 이동할 수 있다.
- 왼쪽, 위쪽, 대각선 이동은 허용하지 않는다.
c(i,j)를 원소 (i,j)에 이르는 최고점수라하고, m(i,j)는 행렬의 원소(i,j)의 값이라 하면 아래와 같이 문제를 해결할 수 있다.
c(i,j) = m(1,1) if i=j=1
m(1,j) + c(1,j-1) if i=1, j>1
m(i,1) + c(i-1,1) if i>1, j=1
m(i,j) + max(c(i,j-1), c(i-1,j)) if i>1, j>1
3. 조약돌 놓기 문제
3xn 테이블의 각 칸에 숫자가 쓰여 있다. 테이블의 칸들 중 일부에 제한조건을 만족하는 방법으로 조약돌을 놓아 조약돌이 놓인 곳에 있는 수의 합을 최대로 하는 방법을 구하는 문제이다. 제한 조건은 다음과 같다.
- 가로나 세로로 인접한 두 칸에 동시에 조약돌이 놓일 수 없다.
- 각 열에는 하나 이상의 조약돌을 놓는다.
임의의 열에 조약돌을 놓을 수 있는 방법은 총 4가지다 -> 패턴에 대한 내용은 책 확인
이를 기준으로 아래와 같이 문제를 해결할 수 있다.
c(i,p): i열이 패턴p로 놓일 때의 최고 점수
w(ip): i열이 패턴p로 놓일 때 i열에 돌이 놓인 곳의 점수 합
c(i,p) = w(i,p) if i=1
max(c(i-1,q)) + w(i,p) if i>1, q는 p와 양립하는 패턴
4. 행렬 곱셈 순서 문제
n개의 행렬이 주어지고 이들의 곱을 계산하려 한다. 행렬은 결합법칙이 성립하므로 어떤 순서로 두개씩 짝지어 계산해도 결과는 동일하다.
c(i,j): 행렬 A(i), ..., A(j)의 곱 A(i), ... A(j)를 계산하는 최소 비용
A(i): p(i-1)Xp(i) 행렬
c(i,j) = 0 if i=j
min(c(i,k) + c(k+1,j) + p(i-1)p(k)p(j)) if i<j, i<=k<=j-1
5. 최장 공통 부분순서(LCS)
두 문자열 X(m)과 Y(n)에 대해 두 문자열에 공통적으로 존재하는 가장 긴 부분순서를 구한다.
c(i,j)를 문자열 X(i)와 Y(i)의 LCS의 길이라 하면 점화식은 다음과 같다.
c(i,j) = 0 if i=0, j=0
c(i-1,j-1) + 1 if i,j>0 and x(i)=y(j)
max(c(i-1,j),c(i,j-1)) if i,j>0 and x(i)!=y(j)
쉽게 배우는 알고리즘 7장 요약
7장 상호배타적 집합의 처리
1. 연결 리스트를 이용한 집합의 처리
1.1 개요
- 각 원소당 하나의 노드를 만들고 이들을 연결 리스트로 연결한다.
- 각 노드에는 원소를 저장하는 필드와 다음 원소, 대표 원소를 가리키는 두 개의 포인터가 있다.
- 대표 원소는 연결 리스트의 맨 앞에 있는 원소가 되고 tail은 마지막 원소를 가리킨다.
- 아래의 세 연산이 필요하다.
* Make-Set(x): 원소 x로만 이루어진 집합을 만든다. 노드를 하나 만들어 대표 노드는 자신을 가리키도록 하고, 다음 원소를 가리키는 포인터는 NIL로 한다.
* Find-Set(x): 원소 x를 가지고 있는 집합을 알아낸다. 원소 x가 가리키는 대표 노드를 리턴한다.
* Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합친다. 주집합의 tail에 해당하는 노드의 다음 원소 포인터를 부집합의 대표 노드를 가리키도록 바꾸고 부집합의 모든 노드의 대표 원소 포인터는 주집합의 대표 노드를 가리키도록 바꾼다.
1.2 수행시간
- 두 집합을 합칠 때 큰 집합을 그대로 두고 작은 집합을 붙이는 것이 수행시간이 더 빠르다.
- 책 참조
2. 트리를 이용한 집합의 처리
2.1 기본 원리
- 자식 노드가 부모 노드를 가리키도록 한다.
- 두 집합을 합하는 방법: 한 집합의 루트가 다른 집합의 루트를 가리키도록 변경한다.
- 하나의 원소로 이루어진 집합 만들기: 노드를 하나 만들고 이 노드의 부모가 자신이 되도록 포인터를 만든다.
2.2 연산의 효율을 높이는 방법
2.2.1 랭크를 이용한 Union
- 각 노드는 자신을 루트로 하는 서브트리의 높이를 랭크라는 이름으로 저장한다.
- 두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다.
2.2.2 경로 압축
- 기본 원리에서의 Find-Set과 같이 행하되 Find-Set(x)를 수행하는 과정에서 만나는 모든 노드들이 직접 루트를 가리키도록 포인터를 바꾼다.
2.2.3 효율성
책 참조
1. 연결 리스트를 이용한 집합의 처리
1.1 개요
- 각 원소당 하나의 노드를 만들고 이들을 연결 리스트로 연결한다.
- 각 노드에는 원소를 저장하는 필드와 다음 원소, 대표 원소를 가리키는 두 개의 포인터가 있다.
- 대표 원소는 연결 리스트의 맨 앞에 있는 원소가 되고 tail은 마지막 원소를 가리킨다.
- 아래의 세 연산이 필요하다.
* Make-Set(x): 원소 x로만 이루어진 집합을 만든다. 노드를 하나 만들어 대표 노드는 자신을 가리키도록 하고, 다음 원소를 가리키는 포인터는 NIL로 한다.
* Find-Set(x): 원소 x를 가지고 있는 집합을 알아낸다. 원소 x가 가리키는 대표 노드를 리턴한다.
* Union(x, y): 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합친다. 주집합의 tail에 해당하는 노드의 다음 원소 포인터를 부집합의 대표 노드를 가리키도록 바꾸고 부집합의 모든 노드의 대표 원소 포인터는 주집합의 대표 노드를 가리키도록 바꾼다.
1.2 수행시간
- 두 집합을 합칠 때 큰 집합을 그대로 두고 작은 집합을 붙이는 것이 수행시간이 더 빠르다.
- 책 참조
2. 트리를 이용한 집합의 처리
2.1 기본 원리
- 자식 노드가 부모 노드를 가리키도록 한다.
- 두 집합을 합하는 방법: 한 집합의 루트가 다른 집합의 루트를 가리키도록 변경한다.
- 하나의 원소로 이루어진 집합 만들기: 노드를 하나 만들고 이 노드의 부모가 자신이 되도록 포인터를 만든다.
2.2 연산의 효율을 높이는 방법
2.2.1 랭크를 이용한 Union
- 각 노드는 자신을 루트로 하는 서브트리의 높이를 랭크라는 이름으로 저장한다.
- 두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙인다.
2.2.2 경로 압축
- 기본 원리에서의 Find-Set과 같이 행하되 Find-Set(x)를 수행하는 과정에서 만나는 모든 노드들이 직접 루트를 가리키도록 포인터를 바꾼다.
2.2.3 효율성
책 참조
쉽게 배우는 알고리즘 6장 요약
6장 해시 테이블
원소끼리 비교해 자리를 찾는 것이 아니라 자신의 값이 자신의 자리를 바로 결정한다.
1. 해시 테이블
- 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조
- 해시값은 해시 함수에 의해 계산
- 적재율(Load Factor): 해시 테이블에 원소가 차 있는 비율로서 성능에 중요한 영향을 끼침.
2. 해시 함수
다음의 두 가지 성질을 만족해야 함
a. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다.
b. 계산이 간단해야 한다.
2.1 나누기 방법
- 테이블의 크기보다 큰 수를 해시 테이블 크기 범위에 들어오도록 하는 방법
- h(x) = x mod m : m은 해시 테이블의 크기
- m은 2의 멱수(2^p) 에 가깝지 않은 소수를 택하는 것이 좋다. 2의 멱수라면 입력 원소의 하위 p비트에 의해 해시값이 결정되기 때문이다.
2.2 곱하기 방법
- 입력값을 0과 1사이의 소수로 대응시킨 다음 해시 테이블 크기 m을 곱하여 0부터 m-1 사이로 팽창시키는 방법(0<A<1 범위의 상수 A 필요)
- 계산 방법
* x에 A를 곱한 다음 소수부만 취한다.
* 방금 취한 소수부에 m을 곱하여 그 정수부를 취한다.
* h(x) = m(xA mod 1)의 정수부
- Knuth는 잘 작동하는 값으로 (루트5 - 1)/2를 제안
3. 충돌 해결
- 충돌: 해시 테이블 내의 한 주소를 놓고 두 개 이상의 원소가 자리를 다투는 것
3.1 체이닝
- 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트에 매달아서 관리
- 임의의 원소를 연결 리스트에 삽입할 때 해당 리스트의 맨 앞에 삽입하는 것이 좋다.
3.2 개방주소 방법(Open Addressing)
- 충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결하는 방법
- 충돌이 일어나면 다음 해시 함수로 다음 자리를 찾는다. 그래도 차 있으면 자리를 찾을 때까지 계속한다.
3.2.1 선형 조사(Linear Probing)
- 충돌이 일어난 바로 뒷자리를 보는 것
- h(x) = (h(x) + i) mod m
- 특정 영역에 원소가 몰릴 때는 치명적으로 성능이 떨어진다.
3.2.2 이차원 조사(Quadratic Probing)
- 충돌시 바로 뒷자리를 보는 대신에 보폭을 이차함수에 의해 넓혀가면서 본다.
- h(x) = (h(x) + c1*i^2 + c2*i) mod m, i = 0, 1, 2, ...
- 선형 조사에서의 단점인 특정 영역에 원소가 몰려도 그 영역을 빨리 벗어 날 수 있다.
- 여러개의 원소가 동일한 초기 해시 함수값을 갖게 되면 모두 같은 순서로 조사를 할 수 밖에 없으므로 비효율적이 된다.
3.2.3 더블 해싱
- h(x) = (h(x) + i*f(x)) mod m, h(x)와 f(x)는 서로 다른 해시 함수, i = 0, 1, 2, ...
* h(x) = x mod m, f(x) = 1 + (x mod m'), m'은 m보다 조금 작은 소수
- 두 원소의 첫 번째 해시값이 같더라도 두 번째 함수값이 같을 확률은 매우 작으므로 서로 다른 보폭으로 점프를 하게 된다.
- 두 번째 해시 함수 값 f(x)가 해시 테이블 크기 m과 서로 소인값이어야 한다.
* f(x)와 m이 최소공약수 d를 가지면 x의 자리를 찾기 위해 해시 테이블 전체 중에 기껏해야 1/d 밖에 보지 못하게 된다.
* m을 소수로 잡고 f(x)의 값이 항상 m보다 작은 자연수가 되도록 하면 된다.
3.2.4 삭제시 문제점
- 원소(x)를 저장할 때 충돌로 인하여 여러번 해시 함수를 통해 위치를 찾은 경우 기존에 겹쳤던 원소(y)를 삭제하면 나중에 x를 찾을 때 y의 위치가 비어 있으므로 찾지 못하게 되는 문제가 생긴다.
- 따라서, 원래 원소가 있었던 위치라는 것을 표시해 주어야 위치를 찾아 갈 수 있다.
4. 검색 시간 분석
책 참조
원소끼리 비교해 자리를 찾는 것이 아니라 자신의 값이 자신의 자리를 바로 결정한다.
1. 해시 테이블
- 원소가 저장될 자리가 원소의 값에 의해 결정되는 자료구조
- 해시값은 해시 함수에 의해 계산
- 적재율(Load Factor): 해시 테이블에 원소가 차 있는 비율로서 성능에 중요한 영향을 끼침.
2. 해시 함수
다음의 두 가지 성질을 만족해야 함
a. 입력 원소가 해시 테이블 전체에 고루 저장되어야 한다.
b. 계산이 간단해야 한다.
2.1 나누기 방법
- 테이블의 크기보다 큰 수를 해시 테이블 크기 범위에 들어오도록 하는 방법
- h(x) = x mod m : m은 해시 테이블의 크기
- m은 2의 멱수(2^p) 에 가깝지 않은 소수를 택하는 것이 좋다. 2의 멱수라면 입력 원소의 하위 p비트에 의해 해시값이 결정되기 때문이다.
2.2 곱하기 방법
- 입력값을 0과 1사이의 소수로 대응시킨 다음 해시 테이블 크기 m을 곱하여 0부터 m-1 사이로 팽창시키는 방법(0<A<1 범위의 상수 A 필요)
- 계산 방법
* x에 A를 곱한 다음 소수부만 취한다.
* 방금 취한 소수부에 m을 곱하여 그 정수부를 취한다.
* h(x) = m(xA mod 1)의 정수부
- Knuth는 잘 작동하는 값으로 (루트5 - 1)/2를 제안
3. 충돌 해결
- 충돌: 해시 테이블 내의 한 주소를 놓고 두 개 이상의 원소가 자리를 다투는 것
3.1 체이닝
- 같은 주소로 해싱되는 원소를 모두 하나의 연결 리스트에 매달아서 관리
- 임의의 원소를 연결 리스트에 삽입할 때 해당 리스트의 맨 앞에 삽입하는 것이 좋다.
3.2 개방주소 방법(Open Addressing)
- 충돌이 일어나더라도 어떻게든 주어진 테이블 공간에서 해결하는 방법
- 충돌이 일어나면 다음 해시 함수로 다음 자리를 찾는다. 그래도 차 있으면 자리를 찾을 때까지 계속한다.
3.2.1 선형 조사(Linear Probing)
- 충돌이 일어난 바로 뒷자리를 보는 것
- h(x) = (h(x) + i) mod m
- 특정 영역에 원소가 몰릴 때는 치명적으로 성능이 떨어진다.
3.2.2 이차원 조사(Quadratic Probing)
- 충돌시 바로 뒷자리를 보는 대신에 보폭을 이차함수에 의해 넓혀가면서 본다.
- h(x) = (h(x) + c1*i^2 + c2*i) mod m, i = 0, 1, 2, ...
- 선형 조사에서의 단점인 특정 영역에 원소가 몰려도 그 영역을 빨리 벗어 날 수 있다.
- 여러개의 원소가 동일한 초기 해시 함수값을 갖게 되면 모두 같은 순서로 조사를 할 수 밖에 없으므로 비효율적이 된다.
3.2.3 더블 해싱
- h(x) = (h(x) + i*f(x)) mod m, h(x)와 f(x)는 서로 다른 해시 함수, i = 0, 1, 2, ...
* h(x) = x mod m, f(x) = 1 + (x mod m'), m'은 m보다 조금 작은 소수
- 두 원소의 첫 번째 해시값이 같더라도 두 번째 함수값이 같을 확률은 매우 작으므로 서로 다른 보폭으로 점프를 하게 된다.
- 두 번째 해시 함수 값 f(x)가 해시 테이블 크기 m과 서로 소인값이어야 한다.
* f(x)와 m이 최소공약수 d를 가지면 x의 자리를 찾기 위해 해시 테이블 전체 중에 기껏해야 1/d 밖에 보지 못하게 된다.
* m을 소수로 잡고 f(x)의 값이 항상 m보다 작은 자연수가 되도록 하면 된다.
3.2.4 삭제시 문제점
- 원소(x)를 저장할 때 충돌로 인하여 여러번 해시 함수를 통해 위치를 찾은 경우 기존에 겹쳤던 원소(y)를 삭제하면 나중에 x를 찾을 때 y의 위치가 비어 있으므로 찾지 못하게 되는 문제가 생긴다.
- 따라서, 원래 원소가 있었던 위치라는 것을 표시해 주어야 위치를 찾아 갈 수 있다.
4. 검색 시간 분석
책 참조
쉽게 배우는 알고리즘 5장 요약
1. 이진 검색 트리
1.1 특성
a. 이진검색트리의 각 노드는 키값을 하나씩 갖는다. 각 노드의 키값은 모두 달라야 한다.
b. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식 노드를 갖는다.
c. 임의의 노드의 키값은 자신의 왼쪽 자식 노드의 키값보다 크고, 오른쪽 자식 노드의 키값보다 작다.
1.2 검색
루트 노드에서부터 검색을 시작한다. 루트 노드의 값과 x를 비교해 x가 더 작으면 왼쪽 서브트리로 가고, 크면 오른쪽 서브트리로 가서 x를 찾는다. x를 가진 노드가 있으면 해당 노드를 리턴하고, 없으면 NIL을 리턴한다.
1.3 삽입
실패하는 검색을 수행하여 리프 노드로 간 후 그 리프 노드의 자식으로 x를 매단다.
이진검색트리의 모양은 원소들이 어떤 순서로 삽입되었는지에 따라 달라진다. n개의 원소로 이진검색트리를 만들면 최악의 경우라 하더라도 검색시간은 Theta(log n) 이다.
1.4 삭제
다음의 세가지에 따라 다르게 처리해 준다.(r: 삭제하고자 하는 노드)
a. case 1: r이 리프노드인 경우
r을 제거하고 r의 부모 노드가 r을 가리키고 있던 부분은 NIL로 바꾸어준다.
b. case 2: r의 자식 노드가 하나인 경우
r을 제거하고 r의 부모 노드에서 r을 가리키고 있던 포인터를 r의 자식을 가리키도록 바꾸어준다.
c. case 3: r의 자식 노드가 두 개인 경우
트리내에서 r의 자리에 대신 놓아도 괜찮은 원소는 크기 순으로 r의 직전 원소 또는 r의 다음 원소이다. 이 원소를 r의 자리에 옮겨 놓는다. 이렇게 하면 자리를 옮겨간 원소의 자리가 비게 되는데 이 원소는 두개의 원소를 가질 수 없다. 이 경우는 앞의 case 1과 case 2의 경우가 되므로 그에 맞는 삭제작업을 해주면 된다.
2. 레드블랙트리
- 균형잡인 이진검색트리
2.1 특성
a. 루트는 블랙이다.
b. 모든 리프(NIL)는 블랙이다.
c. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.
d. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
리프노드: 이진검색트리의 노드가 가진 두 개의 자식 포인터 중 NIL인 것이 있으면 노드를 하나 만들어 그것을 리프노드라 부른다.
2.2 삽입
a. 이진검색트리의 삽입 알고리즘에 따라 삽입을 한 다음 새 노드(x)의 색상을 레드로 칠한다.
b. x의 부모노드(p)가 블랙이면 삽입은 완료.
c. p가 레드인 경우 p의 부모노드를 p2라 하면 p2는 블랙이고 x의 형제노드도 블랙이다. p의 형제 노드(s)는 레드일수도 있고 블랙일 수도 있다.
- s가 레드인경우
p와 s의 색상을 레드에서 블랙으로 바꾸고 p2의 색상을 블랙에서 레드로 바꾼다. 만약 p2가 루트이면 다시 p2의 색상을 블랙으로 바꾸고 끝낸다. p2가 루트가 아니면 재귀적으로 다시 c부터 확인한다.
- s가 블랙인 경우
x가 p의 오른쪽 자식인 경우와 왼쪽 자식인 경우 나뉜다.
- 오른쪽 자식인 경우
p를 중심으로 왼쪽으로 회전하면 아래의 왼쪽 자식인 경우로 치환된다.
- 왼쪽 자식인 경우
p2를 중심으로 오른쪽으로 회전하고 p와 p2의 색상을 맞바꾼다. -> 문제 해결
왼쪽 회전: p의 오른쪽 자식(x)을 p2의 자식으로 놓고 p를 x의 왼쪽 자식으로 놓는다. -> 원래 x의 왼쪽 자식을 p의 오른쪽 자식으로 놓는다.
오른쪽 회전: p2의 왼쪽 자식(p)을 p2의 부모 노드의 자식으로 놓고 p2를 p의 오른쪽 자식으로 놓는다. -> p의 원래 오른쪽 자식을 p2의 왼쪽 자식으로 놓는다.
새 노드는 항상 맨 아래쪽에 매달리므로 삽입 직후에 새 노드의 아래쪽은 문제가 생길 것이 없다. 따라서 위쪽에 문제가 생기는 지를 확인한다. 이를 위해 새 노드의 부모 노드부터 확인하면서 문제를 해결하고 루트로 올라간다.
2.3 삭제
임의의 노드 d를 삭제할 때 d의 자식이 둘이면 d의 오른쪽 서브트리에서 최소원소(노드 d의 직후원소)를 가진 노드 m의 키를 노드 d로 옮긴 다음 노드 m을 삭제한다.(최소원소 m은 최대 1개의 자식만을 가질 수 있다.) -> 자식이 없거나 1개만을 가진 노드의 삭제에 국한해 설명해도 무방
- 아래와 같은 세가지 경우가 나오게 된다.
a. m이 레드이면 삭제 후 아무런 조치가 필요없다.
b. m이 블랙이고 자식(x)이 레드이면 삭제 후 x의 색상을 블랙으로 바꾸어 버리면 된다.
c. m과 x의 색상이 모두 블랙인 경우 다음과 같이 두가지로 나눌 수 있다.
- p가 레드이고 s가 블랙인 경우
- p가 블랙인 경우
c의 경우를 설명하기 전에 우선 각각의 노드를 다음과 같이 명명한다:
- x의 부모노드 : p
- p의 다른 자식 노드 : s
- s의 자식 노드: l과 r
각각의 경우를 살펴보자.
2.3.1 p가 레드이고 s가 블랙
l과 r의 색상에 따라 세가지로 나뉜다.
a. (l,r) : (블랙, 블랙)
p와 s의 색상을 바꾼다.
b. (l.r) : (레드, 레드) 또는 (블랙, 레드)
p를 중심으로 왼쪽으로 회전 -> p와 s의 색상을 바꾼다. -> r의 색상을 레드에서 블랙으로 바꾼다.
c. (l,r) : (레드, 블랙)
s를 중심으로 오른쪽으로 회전 -> l과 s의 색상을 바꾼다. -> b로 이동
2.3.2 p가 블랙
p가 블랙이면 s는 블랙 또는 레드가 가능하므로 다음과 같은 네가지로 나뉜다.
a. (s,l,r) : (블랙, 블랙, 블랙)
s의 색상을 블랙에서 레드로 바꾼다. -> p를 문제발생노드로 하여 재귀적으로 다시 시작
b. (s,l,r) : (블랙, 레드, 레드) 또는 (블랙, 블랙, 레드)
2.3.1의 b와 같다.
c. (s,l,r) : (블랙, 레드, 블랙)
2.3.1의 c와 같다.
d. (s,l,r) : (레드, 블랙, 블랙)
p를 중심으로 왼쪽으로 회전 -> p와 s의 색상을 바꾼다. -> 2.3.1에서의 경우로 이동
3. B-트리
3.1 특성
a. 루트를 제외한 모든 노드는 최대 k개의 키를, 최소 k의 반이상의 키를 갖는다.
b. 모든 리프 노드는 같은 깊이를 가진다.
3.2 검색
이진검색트리에서의 검색과 같다.
3.3 삽입
a. x를 삽입할 리프 노드 r을 찾는다.
b. 노드 r에 공간의 여유가 있으면 키를 삽입하고 끝낸다.
c. 노드 r에 여유가 없으면 형제 노드를 살펴 공간의 여유가 있으면 형제 노드에 키를 하나 넘겨주면 된다. 이때 키를 바로 넘기면 트리의 성질이 깨지므로 부모 노드에 있는 키를 넘기고 비게된 부모 노드의 자리에 노드 r에 있던 키를 놓는다.
d. 형제 노드에 여유가 없으면 노드를 두 개로 분리한다. 이렇게 되면 부모 노드에 키가 하나 더 필요하게 되므로 분할 할 노드에 있는 키 중 하나를 부모 노드에 넘긴다. 이 때 부모 노드가 여유가 없으면 재귀적으로 다시 분할을 시도한다. 상황에 따라 루트까지 분할이 이루어 질 수도 있다.
3.4 삭제
a. x를 키로 가지고 있는 노드를 찾는다.
b. 이 노드가 리프 노드가 아니면 x의 직후원소 y를 가진 리프 노드 r을 찾아 x와 y를 맞바꾼다.
c. 리프 노드에서 x를 제거한다.
d. x 제거 후 노드에 키가 모자르면 형제 노드를 살펴 키를 내 놓을 수 있는 노드가 있으면 키를 받는다. 이때 실제로는 삽입의 c에서처럼 형제 노드의 키를 바로 받을 수는 없고 형제 노드의 키를 부모 노드로 보내고 부모 노드의 키를 받아온다.
e. 형제 노드가 키를 내 놓을 여유가 없으면 병합을 한다. 병합은 형제 노드의 내용과 부모 노드의 키를 내려받아 행한다. 만약 이렇게 함으로서 부모 노드에 다시 키가 모자르게 되면 재귀적으로 d를 다시 실시한다.
4. KD-트리
4.1 특성
이진검색트리를 확장한 것으로 k개(>=2)의 필드로 이루어지는 키를 사용한다.
레벨 i에서는 필드 i(mod k)만으로 분기를 한다. - 루트노드는 첫번째 필드만 사용해서 분기하고 그 다음 레벨은 두 번째 필드만 사용해 분기를 하고... 이런 식으로 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기를 한다.
4.2 검색
이진검색트리와 같이 하면 된다. 위에서 설명한 분기 방식에 따라 분기하면서 찾는다.
4.3 삽입
이진검색트리와 같이 하면 된다. 검색하듯이 트리를 따라 내려가다 리프 노드를 만나면 거기에서 왼쪽 또는 오른쪽에 달아 준다.
4.4 삭제
노드 r을 삭제한다고 할 때 아래의 세 가지 경우로 나누어 볼 수 있다.
a. 자식이 없는 경우
이진검색트리와 마찬가지로 노드 r만 제거
b. 자식이 하나뿐인 경우
이진검색트리에서는 노드 r의 부도가 바로 노드 r의 자식을 가리키도록 하면 끝나지만 KD-트리에서는 이렇게 하면 분기에 사용하는 필드가 달라지므로 이렇게 하면 안된다. 자식이 둘인 경우와 같은 방법으로 삭제를 해야 한다.
c. 자식이 둘인 경우
오른쪽 서브트리 중 노드 r에서 분기에 사용한 필드의 값이 가장 작은 노드(s)를 찾아 삭제하고 그 노드를 노드 r의 자리로 이동한다. -> 이것은 s를 삭제하는 것과 같은 재귀적 작업이 된다.
최적화: 가장 작은 노드를 찾을 때 모든 서브트리를 찾을 필요는 없다. 같은 필드를 가지고 분기를 하는 레벨인 경우 거기에서의 값에 따라 왼쪽 또는 오른쪽만 찾으면 된다.
5 KDB-트리
5.1 특성
B-트리(각 노드가 키에 의해 분기)를 확장한 것으로서 각 노드가 영역에 의해 분기한다.
다음의 두 종류가 있다.
a. 영역 노드
복수 개의 (영역, 페이지 번호) 쌍으로 구성된다. 모든 내부 노드는 영역 노드다.
b. 키 노드
복수 개의 (키, 페이지 번호) 쌍으로 구성된다. 모든 리프 노드는 키 노드다.
5.2 검색
a. 키 검색: 루트 노드부터 시작해서 해당 키가 포함되는 영역을 따라 리프 노드까지 내려간다.
b. 영역 검색: 루트 노드로부터 시작해 검색 영역과 겹치는 부분이 있는 노드는 모두 방문해 확인한다.
5.3 삽입 및 삭제
B-트리에서와 유사하게 한다.
6. R-트리
- B-트리를 확장
- KDB-트리에서는 노드들이 전체 공간을 나누어 커버하는데 반해 R-트리는 키들을 포함하는 최소 영역만 노드에 있다.
- KDB-트리처럼 두 종류의 노드가 있다.
a. 영역 노드: 복수 개의(영역, 페이지 번호)쌍으로 구성된다. 모든 내부 노드는 영역노드다.
b. 키 노드: 복수 개의(키, 페이지 번호)쌍으로 구성된다. 모든 리프 노드는 키 노드다.
- 다음의 성질을 만족한다.
a. 루트를 제외한 모든 내부 노드는 k/2 ~ k개의 영역을 갖는다.
b. 모든 리프 노드는 같은 깊이를 가진다.
c. 모든 레코드는 리프 노드에서만 가리킨다.
- 한 노드에 있는 영역들이 서로 겹칠 수도 있다.
- 삽입, 삭제는 B-트리에서와 유사하게 일어난다: 책 참조
7. 그리드 파일
- 공간을 서로 배타적인 격자(그리드) 영역으로 나눈 다음 해당 영역에 속하는 레코드들을 모아서 저장함으로서 임의의 레코드에 대한 저장과 검색을 단번에 할 수 있게 한다.
- 책 참조
1.1 특성
a. 이진검색트리의 각 노드는 키값을 하나씩 갖는다. 각 노드의 키값은 모두 달라야 한다.
b. 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 두 개의 자식 노드를 갖는다.
c. 임의의 노드의 키값은 자신의 왼쪽 자식 노드의 키값보다 크고, 오른쪽 자식 노드의 키값보다 작다.
1.2 검색
루트 노드에서부터 검색을 시작한다. 루트 노드의 값과 x를 비교해 x가 더 작으면 왼쪽 서브트리로 가고, 크면 오른쪽 서브트리로 가서 x를 찾는다. x를 가진 노드가 있으면 해당 노드를 리턴하고, 없으면 NIL을 리턴한다.
1.3 삽입
실패하는 검색을 수행하여 리프 노드로 간 후 그 리프 노드의 자식으로 x를 매단다.
이진검색트리의 모양은 원소들이 어떤 순서로 삽입되었는지에 따라 달라진다. n개의 원소로 이진검색트리를 만들면 최악의 경우라 하더라도 검색시간은 Theta(log n) 이다.
1.4 삭제
다음의 세가지에 따라 다르게 처리해 준다.(r: 삭제하고자 하는 노드)
a. case 1: r이 리프노드인 경우
r을 제거하고 r의 부모 노드가 r을 가리키고 있던 부분은 NIL로 바꾸어준다.
b. case 2: r의 자식 노드가 하나인 경우
r을 제거하고 r의 부모 노드에서 r을 가리키고 있던 포인터를 r의 자식을 가리키도록 바꾸어준다.
c. case 3: r의 자식 노드가 두 개인 경우
트리내에서 r의 자리에 대신 놓아도 괜찮은 원소는 크기 순으로 r의 직전 원소 또는 r의 다음 원소이다. 이 원소를 r의 자리에 옮겨 놓는다. 이렇게 하면 자리를 옮겨간 원소의 자리가 비게 되는데 이 원소는 두개의 원소를 가질 수 없다. 이 경우는 앞의 case 1과 case 2의 경우가 되므로 그에 맞는 삭제작업을 해주면 된다.
2. 레드블랙트리
- 균형잡인 이진검색트리
2.1 특성
a. 루트는 블랙이다.
b. 모든 리프(NIL)는 블랙이다.
c. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.
d. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
리프노드: 이진검색트리의 노드가 가진 두 개의 자식 포인터 중 NIL인 것이 있으면 노드를 하나 만들어 그것을 리프노드라 부른다.
2.2 삽입
a. 이진검색트리의 삽입 알고리즘에 따라 삽입을 한 다음 새 노드(x)의 색상을 레드로 칠한다.
b. x의 부모노드(p)가 블랙이면 삽입은 완료.
c. p가 레드인 경우 p의 부모노드를 p2라 하면 p2는 블랙이고 x의 형제노드도 블랙이다. p의 형제 노드(s)는 레드일수도 있고 블랙일 수도 있다.
- s가 레드인경우
p와 s의 색상을 레드에서 블랙으로 바꾸고 p2의 색상을 블랙에서 레드로 바꾼다. 만약 p2가 루트이면 다시 p2의 색상을 블랙으로 바꾸고 끝낸다. p2가 루트가 아니면 재귀적으로 다시 c부터 확인한다.
- s가 블랙인 경우
x가 p의 오른쪽 자식인 경우와 왼쪽 자식인 경우 나뉜다.
- 오른쪽 자식인 경우
p를 중심으로 왼쪽으로 회전하면 아래의 왼쪽 자식인 경우로 치환된다.
- 왼쪽 자식인 경우
p2를 중심으로 오른쪽으로 회전하고 p와 p2의 색상을 맞바꾼다. -> 문제 해결
왼쪽 회전: p의 오른쪽 자식(x)을 p2의 자식으로 놓고 p를 x의 왼쪽 자식으로 놓는다. -> 원래 x의 왼쪽 자식을 p의 오른쪽 자식으로 놓는다.
오른쪽 회전: p2의 왼쪽 자식(p)을 p2의 부모 노드의 자식으로 놓고 p2를 p의 오른쪽 자식으로 놓는다. -> p의 원래 오른쪽 자식을 p2의 왼쪽 자식으로 놓는다.
새 노드는 항상 맨 아래쪽에 매달리므로 삽입 직후에 새 노드의 아래쪽은 문제가 생길 것이 없다. 따라서 위쪽에 문제가 생기는 지를 확인한다. 이를 위해 새 노드의 부모 노드부터 확인하면서 문제를 해결하고 루트로 올라간다.
2.3 삭제
임의의 노드 d를 삭제할 때 d의 자식이 둘이면 d의 오른쪽 서브트리에서 최소원소(노드 d의 직후원소)를 가진 노드 m의 키를 노드 d로 옮긴 다음 노드 m을 삭제한다.(최소원소 m은 최대 1개의 자식만을 가질 수 있다.) -> 자식이 없거나 1개만을 가진 노드의 삭제에 국한해 설명해도 무방
- 아래와 같은 세가지 경우가 나오게 된다.
a. m이 레드이면 삭제 후 아무런 조치가 필요없다.
b. m이 블랙이고 자식(x)이 레드이면 삭제 후 x의 색상을 블랙으로 바꾸어 버리면 된다.
c. m과 x의 색상이 모두 블랙인 경우 다음과 같이 두가지로 나눌 수 있다.
- p가 레드이고 s가 블랙인 경우
- p가 블랙인 경우
c의 경우를 설명하기 전에 우선 각각의 노드를 다음과 같이 명명한다:
- x의 부모노드 : p
- p의 다른 자식 노드 : s
- s의 자식 노드: l과 r
각각의 경우를 살펴보자.
2.3.1 p가 레드이고 s가 블랙
l과 r의 색상에 따라 세가지로 나뉜다.
a. (l,r) : (블랙, 블랙)
p와 s의 색상을 바꾼다.
b. (l.r) : (레드, 레드) 또는 (블랙, 레드)
p를 중심으로 왼쪽으로 회전 -> p와 s의 색상을 바꾼다. -> r의 색상을 레드에서 블랙으로 바꾼다.
c. (l,r) : (레드, 블랙)
s를 중심으로 오른쪽으로 회전 -> l과 s의 색상을 바꾼다. -> b로 이동
2.3.2 p가 블랙
p가 블랙이면 s는 블랙 또는 레드가 가능하므로 다음과 같은 네가지로 나뉜다.
a. (s,l,r) : (블랙, 블랙, 블랙)
s의 색상을 블랙에서 레드로 바꾼다. -> p를 문제발생노드로 하여 재귀적으로 다시 시작
b. (s,l,r) : (블랙, 레드, 레드) 또는 (블랙, 블랙, 레드)
2.3.1의 b와 같다.
c. (s,l,r) : (블랙, 레드, 블랙)
2.3.1의 c와 같다.
d. (s,l,r) : (레드, 블랙, 블랙)
p를 중심으로 왼쪽으로 회전 -> p와 s의 색상을 바꾼다. -> 2.3.1에서의 경우로 이동
3. B-트리
3.1 특성
a. 루트를 제외한 모든 노드는 최대 k개의 키를, 최소 k의 반이상의 키를 갖는다.
b. 모든 리프 노드는 같은 깊이를 가진다.
3.2 검색
이진검색트리에서의 검색과 같다.
3.3 삽입
a. x를 삽입할 리프 노드 r을 찾는다.
b. 노드 r에 공간의 여유가 있으면 키를 삽입하고 끝낸다.
c. 노드 r에 여유가 없으면 형제 노드를 살펴 공간의 여유가 있으면 형제 노드에 키를 하나 넘겨주면 된다. 이때 키를 바로 넘기면 트리의 성질이 깨지므로 부모 노드에 있는 키를 넘기고 비게된 부모 노드의 자리에 노드 r에 있던 키를 놓는다.
d. 형제 노드에 여유가 없으면 노드를 두 개로 분리한다. 이렇게 되면 부모 노드에 키가 하나 더 필요하게 되므로 분할 할 노드에 있는 키 중 하나를 부모 노드에 넘긴다. 이 때 부모 노드가 여유가 없으면 재귀적으로 다시 분할을 시도한다. 상황에 따라 루트까지 분할이 이루어 질 수도 있다.
3.4 삭제
a. x를 키로 가지고 있는 노드를 찾는다.
b. 이 노드가 리프 노드가 아니면 x의 직후원소 y를 가진 리프 노드 r을 찾아 x와 y를 맞바꾼다.
c. 리프 노드에서 x를 제거한다.
d. x 제거 후 노드에 키가 모자르면 형제 노드를 살펴 키를 내 놓을 수 있는 노드가 있으면 키를 받는다. 이때 실제로는 삽입의 c에서처럼 형제 노드의 키를 바로 받을 수는 없고 형제 노드의 키를 부모 노드로 보내고 부모 노드의 키를 받아온다.
e. 형제 노드가 키를 내 놓을 여유가 없으면 병합을 한다. 병합은 형제 노드의 내용과 부모 노드의 키를 내려받아 행한다. 만약 이렇게 함으로서 부모 노드에 다시 키가 모자르게 되면 재귀적으로 d를 다시 실시한다.
4. KD-트리
4.1 특성
이진검색트리를 확장한 것으로 k개(>=2)의 필드로 이루어지는 키를 사용한다.
레벨 i에서는 필드 i(mod k)만으로 분기를 한다. - 루트노드는 첫번째 필드만 사용해서 분기하고 그 다음 레벨은 두 번째 필드만 사용해 분기를 하고... 이런 식으로 동일한 레벨에 있는 노드는 모두 동일한 하나의 필드만 이용해서 분기를 한다.
4.2 검색
이진검색트리와 같이 하면 된다. 위에서 설명한 분기 방식에 따라 분기하면서 찾는다.
4.3 삽입
이진검색트리와 같이 하면 된다. 검색하듯이 트리를 따라 내려가다 리프 노드를 만나면 거기에서 왼쪽 또는 오른쪽에 달아 준다.
4.4 삭제
노드 r을 삭제한다고 할 때 아래의 세 가지 경우로 나누어 볼 수 있다.
a. 자식이 없는 경우
이진검색트리와 마찬가지로 노드 r만 제거
b. 자식이 하나뿐인 경우
이진검색트리에서는 노드 r의 부도가 바로 노드 r의 자식을 가리키도록 하면 끝나지만 KD-트리에서는 이렇게 하면 분기에 사용하는 필드가 달라지므로 이렇게 하면 안된다. 자식이 둘인 경우와 같은 방법으로 삭제를 해야 한다.
c. 자식이 둘인 경우
오른쪽 서브트리 중 노드 r에서 분기에 사용한 필드의 값이 가장 작은 노드(s)를 찾아 삭제하고 그 노드를 노드 r의 자리로 이동한다. -> 이것은 s를 삭제하는 것과 같은 재귀적 작업이 된다.
최적화: 가장 작은 노드를 찾을 때 모든 서브트리를 찾을 필요는 없다. 같은 필드를 가지고 분기를 하는 레벨인 경우 거기에서의 값에 따라 왼쪽 또는 오른쪽만 찾으면 된다.
5 KDB-트리
5.1 특성
B-트리(각 노드가 키에 의해 분기)를 확장한 것으로서 각 노드가 영역에 의해 분기한다.
다음의 두 종류가 있다.
a. 영역 노드
복수 개의 (영역, 페이지 번호) 쌍으로 구성된다. 모든 내부 노드는 영역 노드다.
b. 키 노드
복수 개의 (키, 페이지 번호) 쌍으로 구성된다. 모든 리프 노드는 키 노드다.
5.2 검색
a. 키 검색: 루트 노드부터 시작해서 해당 키가 포함되는 영역을 따라 리프 노드까지 내려간다.
b. 영역 검색: 루트 노드로부터 시작해 검색 영역과 겹치는 부분이 있는 노드는 모두 방문해 확인한다.
5.3 삽입 및 삭제
B-트리에서와 유사하게 한다.
6. R-트리
- B-트리를 확장
- KDB-트리에서는 노드들이 전체 공간을 나누어 커버하는데 반해 R-트리는 키들을 포함하는 최소 영역만 노드에 있다.
- KDB-트리처럼 두 종류의 노드가 있다.
a. 영역 노드: 복수 개의(영역, 페이지 번호)쌍으로 구성된다. 모든 내부 노드는 영역노드다.
b. 키 노드: 복수 개의(키, 페이지 번호)쌍으로 구성된다. 모든 리프 노드는 키 노드다.
- 다음의 성질을 만족한다.
a. 루트를 제외한 모든 내부 노드는 k/2 ~ k개의 영역을 갖는다.
b. 모든 리프 노드는 같은 깊이를 가진다.
c. 모든 레코드는 리프 노드에서만 가리킨다.
- 한 노드에 있는 영역들이 서로 겹칠 수도 있다.
- 삽입, 삭제는 B-트리에서와 유사하게 일어난다: 책 참조
7. 그리드 파일
- 공간을 서로 배타적인 격자(그리드) 영역으로 나눈 다음 해당 영역에 속하는 레코드들을 모아서 저장함으로서 임의의 레코드에 대한 저장과 검색을 단번에 할 수 있게 한다.
- 책 참조
피드 구독하기:
글 (Atom)