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]가 가장 큰 정점을 시작점으로 잡는다.
앞에서 만들어진 분리된 트리들 각각을 강연결요소로 리턴한다.
}
2015년 6월 10일 수요일
쉽게 배우는 알고리즘 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. 그리드 파일
- 공간을 서로 배타적인 격자(그리드) 영역으로 나눈 다음 해당 영역에 속하는 레코드들을 모아서 저장함으로서 임의의 레코드에 대한 저장과 검색을 단번에 할 수 있게 한다.
- 책 참조
쉽게 배우는 알고리즘 3장 요약
3장 정렬
1. 선택정렬
배열에서 가장 큰 원소를 찾아 이 원소와 배열의 맨 끝자리에 있는 원소와 자리를 바꾼다. 이렇게 하면 가장 큰 수가 배열의 제일 마지막에 오게 되고 이 원소는 자리를 찾은 셈이 된다. 이제 나머지 원소를 가지고 앞에서 사용한 방법을 반복하면 된다.
2. 버블 정렬
선택정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복한다. 다만 제일 큰 원소를 오른쪽으로 옮기는 방법이 다르다. 왼쪽부터 이웃한 수를 비교하면서 순서가 제대로 되어 있지 않으면 하나하나 바꾸어 나간다.
3. 삽입 정렬
이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1개짜리 배열을 만드는 과정을 반복한다.
배열이 거의 정렬되어 있는 상태로 입력되는 경우에는 가장 매력적인 알고리즘이 된다.
4. 병합정렬
입력을 반으로 나눈다. 이렇게 반으로 나눈 전반부와 후반부를 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서 정렬된 배열을 얻는다.
5. 퀵정렬
배열에서 기준원소를 하나 고른다.(랜덤 또는 맨뒤) 이 기준원소를 중심으로 작거나 같은수는 왼쪽으로 큰수는 오른쪽으로 재배치한다. 이렇게 분할된 왼쪽부분과 오른쪽 부분을 따로 정렬한다.
기준 원소 고르기: 맨 앞 vs 맨 뒤 vs 랜덤
6. 힙정렬
(최소힙)
- 먼저 주어진 배열을 힙으로 만든다. 그런 다음, 힙에서 가장 작은 값을 차례로 하나씩 제거하면서 힙의 크기를 줄여나간다(원소 제거후 힙의 성질을 만족하도록 수선하는 과정이 필요). 정렬순서는 힙에서 원소들이 제거된 순서대로이다.
- 힙: 이진트리로서 맨 아래 층을 제외하고는 완전히 채워져 있고 맨 아래층은 왼쪽부터 꽉 채워져 있다.
힙의 모든 노드는 다음의 힙성질을 만족한다. - 각 노드의 값은 자신의 자식의 값보다 작다.
- 힙으로 만드는 방법
* 링크나 포인터 같은 것을 쓰지 않고도 배열을 써서 간단하게 구현할 수 있음.
* 원소를 배열에 넣는다 -> 배열의 중간(n/2, 자식이 있는 제일 마지막 원소)에서 부터 힙의 성질을 만족하도록 수선 시작 -> 두 자식 중 작은 값과 비교하여 자식이 작으면 값을 교환 -> 이와 같은 식으로 루트까지 수선한다.
7. 기수정렬
처음에는 가장 낮은 자리수만 가지고 모든 수를 배열한다. 그 다음에는 두번째로 낮은 자리수만 가지고 모든 수를 배열한다. 이렇게 가장 높은 자리수까지를 반복한다. 이때 안정성을 유지하면서 정렬한다.
입력이 모두 k 이하의 자리수를 가진 자연수인 특수한 경우에 사용
8. 계수정렬
배열의 원소를 훑어보고 1부터 k까지의 자연수가 각각 몇번 나타나는지를 센다. 이 정보가 있으면 배열의 각 원소가 몇 번째에 놓이면 되는지를 계산해낼 수 있다.
9. 위의 정렬들에 대한 Haskell 구현
https://github.com/spriteye/learn-algorithm/blob/master/haskell/Sort.hs
1. 선택정렬
배열에서 가장 큰 원소를 찾아 이 원소와 배열의 맨 끝자리에 있는 원소와 자리를 바꾼다. 이렇게 하면 가장 큰 수가 배열의 제일 마지막에 오게 되고 이 원소는 자리를 찾은 셈이 된다. 이제 나머지 원소를 가지고 앞에서 사용한 방법을 반복하면 된다.
2. 버블 정렬
선택정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복한다. 다만 제일 큰 원소를 오른쪽으로 옮기는 방법이 다르다. 왼쪽부터 이웃한 수를 비교하면서 순서가 제대로 되어 있지 않으면 하나하나 바꾸어 나간다.
3. 삽입 정렬
이미 정렬되어 있는 i개짜리 배열에 하나의 원소를 더 더하여 정렬된 i+1개짜리 배열을 만드는 과정을 반복한다.
배열이 거의 정렬되어 있는 상태로 입력되는 경우에는 가장 매력적인 알고리즘이 된다.
4. 병합정렬
입력을 반으로 나눈다. 이렇게 반으로 나눈 전반부와 후반부를 독립적으로 정렬한다. 마지막으로 정렬된 두 부분을 합쳐서 정렬된 배열을 얻는다.
5. 퀵정렬
배열에서 기준원소를 하나 고른다.(랜덤 또는 맨뒤) 이 기준원소를 중심으로 작거나 같은수는 왼쪽으로 큰수는 오른쪽으로 재배치한다. 이렇게 분할된 왼쪽부분과 오른쪽 부분을 따로 정렬한다.
기준 원소 고르기: 맨 앞 vs 맨 뒤 vs 랜덤
6. 힙정렬
(최소힙)
- 먼저 주어진 배열을 힙으로 만든다. 그런 다음, 힙에서 가장 작은 값을 차례로 하나씩 제거하면서 힙의 크기를 줄여나간다(원소 제거후 힙의 성질을 만족하도록 수선하는 과정이 필요). 정렬순서는 힙에서 원소들이 제거된 순서대로이다.
- 힙: 이진트리로서 맨 아래 층을 제외하고는 완전히 채워져 있고 맨 아래층은 왼쪽부터 꽉 채워져 있다.
힙의 모든 노드는 다음의 힙성질을 만족한다. - 각 노드의 값은 자신의 자식의 값보다 작다.
- 힙으로 만드는 방법
* 링크나 포인터 같은 것을 쓰지 않고도 배열을 써서 간단하게 구현할 수 있음.
* 원소를 배열에 넣는다 -> 배열의 중간(n/2, 자식이 있는 제일 마지막 원소)에서 부터 힙의 성질을 만족하도록 수선 시작 -> 두 자식 중 작은 값과 비교하여 자식이 작으면 값을 교환 -> 이와 같은 식으로 루트까지 수선한다.
7. 기수정렬
처음에는 가장 낮은 자리수만 가지고 모든 수를 배열한다. 그 다음에는 두번째로 낮은 자리수만 가지고 모든 수를 배열한다. 이렇게 가장 높은 자리수까지를 반복한다. 이때 안정성을 유지하면서 정렬한다.
입력이 모두 k 이하의 자리수를 가진 자연수인 특수한 경우에 사용
8. 계수정렬
배열의 원소를 훑어보고 1부터 k까지의 자연수가 각각 몇번 나타나는지를 센다. 이 정보가 있으면 배열의 각 원소가 몇 번째에 놓이면 되는지를 계산해낼 수 있다.
9. 위의 정렬들에 대한 Haskell 구현
https://github.com/spriteye/learn-algorithm/blob/master/haskell/Sort.hs
쉽게 배우는 알고리즘 2장 요약
2장. 점화식과 점근적 복잡도 분석
1. 점화식의 이해
점화식: 어떤 함수를 자신보다 더 작은 변수에 대한 함수와의 관계로 표현하는 방법
-> 등차수열, factorial, 피보나치 수열
예)
재귀적 관계를 이용해 알고리즘의 수행시간을 점화식으로 표현할 수 있다.
병합정렬의 경우 "T(n) = 2T(n/2) + 후처리시간"으로 표현할 수 있다.
2. 점화식의 점근적 분석 방법
a. 반복 대치
T(n)을 T(n-1)로 대치하고 T(n-1)을 T(n-2)로 대치하고 계속해서 T(n-2), T(n-3), ..., T(1)까지 반복해서 대치해가는 것과 같은 방식을 사용해 점근적 복잡도를 구한다.
b. 추정후 증명
식의 모양을 보고 점근적 복잡도를 추정한 다음 그것이 옮음을 귀납적으로 증명하는 방법
c. 마스터 정리
a>=1, b>1에 대해 T(n) = aT(n/b) + f(n)인 점화식에서 n^(log a over b) = h(n)이라 할 때 T(n)의 점근적 복잡도는 아래와 같다.
- 어떤 양의 상수 e에 대하여 f(n)/h(n) = O(1/(n^e))이면, T(n) = Theta(h(n))이다.
- 어떤 양의 상수 e에 대하여 f(n)/h(n) = Omega(n^e)이고, 어떤 상수 c(<1)와 충분히 큰 모든 n에 대해 af(n/b) <= cf(n)이면 T(n) = Theta(f(n))이다.
- f(n)/h(n) = Theta(1)이면 T(n) = Theta(h(n)log n)이다.
쉽게 배우는 알고리즘 1장 요약
1장. 알고리즘 설계와 분석의 기초
1. 몇가지 기초 사항들
알고리즘: 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것
알고리즘은 명확(이해하기 쉬움)하고 효율적(입력의 크기가 충분히 클때)이어야 한다.
입력이 충분히 큰 경우에 대한 분석: 점근적 분석(Asymptotic Analysis)
알고리즘은 대부분 소요시간이 관심의 대상이 된다 -> 최악의 경우와 평균적인 경우
알고리즘의 수행시간은 입력의 크기에 대해 시간이 어떤 비율로 소요되는지를 표현한다.
자기호출(재귀, recursion): 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 간명하게 접근하는 방식
2. 점근적 표기
a. Theta 표기법
알고리즘의 소요시간이 입력의 크기 n에 대해 Theta(n^2)이라면 대략 n^2에 비례하는 시간이 소요됨
b. Oh 표기법
알고리즘의 소요시간이 입력의 크기 n에 대해 Oh(n^2)라면 기껏해야 n^2에 비례하는 시간이 소요됨
c. Omega 표기법
알고리즘의 소요시간이 입력의 크기 n에 대해 Omega(n^2)이라면 적어도 n^2에 비례하는 시간이 소요됨
3. 점근적 표기의 엄밀한 정의
a. Oh 표기법
Oh(g(n)) = {f(n)|모든 n >= n0에 대하여 f(n) <= cg(n)인 양의 상수 c와 n0가 존재한다.}
엄밀한 상한 또는 여유있는 상한
b. Omega 표기법
Omega(g(n)) = {f(n)|모든 n>=n0에 대하여 cg(n)<=f(n)인 양의 상수 c와 n0가 존재한다.}
엄밀한 하한 또는 여유있는 하한
c. Theta 표기법
Oh(g(n))과 Omega(g(n))이 동시에 성립하는 모든 함수의 집합
d. Little Oh 표기법
o(g(n)) = {f(n)|n이 충분히 크면 모든 c>0에 대하여 f(n)<cg(n)이다}
함수의 증가율이 점근적 의미에서 어느 한계보다 더 작다는 것을 표현하고자 할 때 사용
e. Little Omega 표기법
w(g(n)) = {f(n)|n이 충분히 크면 모든 c>0에 대하여 cg(n)<f(n)이다}
함수의 증가율이 점근적 의미에서 어느 한계보다 더 크다는 것을 표현하고자 할 때 사용
1. 몇가지 기초 사항들
알고리즘: 어떤 작업을 수행하기 위해 입력을 받아 원하는 출력을 만들어내는 과정을 기술한 것
알고리즘은 명확(이해하기 쉬움)하고 효율적(입력의 크기가 충분히 클때)이어야 한다.
입력이 충분히 큰 경우에 대한 분석: 점근적 분석(Asymptotic Analysis)
알고리즘은 대부분 소요시간이 관심의 대상이 된다 -> 최악의 경우와 평균적인 경우
알고리즘의 수행시간은 입력의 크기에 대해 시간이 어떤 비율로 소요되는지를 표현한다.
자기호출(재귀, recursion): 어떤 문제를 해결하는 과정에서 자신과 똑같지만 크기가 다른 문제를 발견하고 이들의 관계를 파악함으로써 문제 해결에 간명하게 접근하는 방식
2. 점근적 표기
a. Theta 표기법
알고리즘의 소요시간이 입력의 크기 n에 대해 Theta(n^2)이라면 대략 n^2에 비례하는 시간이 소요됨
b. Oh 표기법
알고리즘의 소요시간이 입력의 크기 n에 대해 Oh(n^2)라면 기껏해야 n^2에 비례하는 시간이 소요됨
c. Omega 표기법
알고리즘의 소요시간이 입력의 크기 n에 대해 Omega(n^2)이라면 적어도 n^2에 비례하는 시간이 소요됨
3. 점근적 표기의 엄밀한 정의
a. Oh 표기법
Oh(g(n)) = {f(n)|모든 n >= n0에 대하여 f(n) <= cg(n)인 양의 상수 c와 n0가 존재한다.}
엄밀한 상한 또는 여유있는 상한
b. Omega 표기법
Omega(g(n)) = {f(n)|모든 n>=n0에 대하여 cg(n)<=f(n)인 양의 상수 c와 n0가 존재한다.}
엄밀한 하한 또는 여유있는 하한
c. Theta 표기법
Oh(g(n))과 Omega(g(n))이 동시에 성립하는 모든 함수의 집합
d. Little Oh 표기법
o(g(n)) = {f(n)|n이 충분히 크면 모든 c>0에 대하여 f(n)<cg(n)이다}
함수의 증가율이 점근적 의미에서 어느 한계보다 더 작다는 것을 표현하고자 할 때 사용
e. Little Omega 표기법
w(g(n)) = {f(n)|n이 충분히 크면 모든 c>0에 대하여 cg(n)<f(n)이다}
함수의 증가율이 점근적 의미에서 어느 한계보다 더 크다는 것을 표현하고자 할 때 사용
2015년 1월 13일 화요일
Countdown Problem
Programming in Haskell의 Chapter. 11 Countdown Problem의 요약
- Countdown Problem
여러 개의 수들과 목표로 하는 결과값이 주어지면, 주어진 여러 개의 수들로부터 원하는 숫자를 골라 덧셈, 뺄셈, 곱셈, 나눗셈 및 괄호를 써서 식을 만들어, 그 만들어진 식의 계산 결과가 목표로 하는 결과값과 같도록 하는 문제(주어진 숫자들은 많아야 한 번씩만 식에 나타나야 하며, 계산 중간값을 포함한 계산에 쓰이는 모든 수들은 반드시 양의 정수여야 한다.).
예를 들어, 1,3,7,10,25,50로부터 765를 결과값으로 계산하기를 생각해보자. (1 + 50) * (5 - 10) 가 가능한 식의 하나가 될 것이다.
- 문제 풀이
네가지 수치 연산을 나타내는 타입을 다음과 같이 정의한다.
data Op = Add | Sub | Mul | Div
연산을 수행하는 함수 apply를 다음과 같이 정의한다.
apply :: Op -> Int -> Int -> Int
apply Add x y = x + y
apply Sub x y = x - y
apply Mul x y = x * y
apply Div x y = x `div` y
apply를 적용하기 전에 그 결과가 양의 정수인지 알아보는 함수 valid를 다음과 같이 정의한다.
valid :: Op -> Int -> Int -> Bool
valid (Add x y) = x <= y
valid (Sub x y) = x > y
valid (Mul x y) = x /= 1 && y /=1 && x <= y
valid (Div x y) = y /= 1 && x `mod` y == 0
덧셈의 경우 (Add 3 2)와 (Add 2 3)은 결과가 같기 때문에 하나만 계산하면 되고, 곱셈의 경우 x나 y가 1인 경우나 나눗셈의 경우 y가 1인 경우는 1인 값이 없는 경우와 같다. 따라서 이러한 경우는 더이상 계산하지 않고 유효하지 않은 값으로 처리한다.
이제 수식을 나타내는 타입을 아래와 같이 정의한다.
data Expr = Val Int | App Op Expr Expr
이 타입을 써서 식이 주어졌을 때 식의 결과 값을 돌려주는 eval 함수를 정의한다.
eval :: Expr -> [Int]
eval (Val n) = [n | n > 0]
eval (App o l r) = [apply o l r | x <- eval l, y <- eval r, valid o x y]
성공하면 한원소 리스트를 값으로 돌려주고, 실패의 경우는 빈 리스트를 값으로 돌려준다.
이제 가능한 모든 식을 통해 결과를 찾는 함수를 정의해보자.
solutions :: [Int] -> Int -> [Expr]
solutions ns n = [e | ns <- choices ns, (e, m) <- results ns, m == n]
이 식의 구현은 다음과 같이 생각할 수 있다. 양의 정수가 주어지면 이것으로 0개 이상의 수를 취하여 만들 수 있는 모든 부분 집합을 생성한다(choices). 이 부분 집합에 가능한 모든 계산 식을 적용한다(results ns). 이 계산 식의 값이 결과 값과 같으면 이 계산 식은 답이 된다.
그럼 먼저 choices를 정의해 보자.
이 함수는 주어진 리스트의 부분 집합을 만들고 이를 순서를 바꾸어 가능한 모든 수를 만들어 내면 된다. 부분 집합을 만드는 함수를 subs라 하고 부분 집합의 순서를 바꾸는 함수를 perms라 하면 choices는 아래와 같이 정의 된다.
choices :: [a] -> [[a]]
choices xs = concat (map perms (subs xs))
subs [] = [[]]
subs (x:xs) = yss ++ map (x:) yss
where yss = subs xs
perms :: [a] -> [[a]]
perms [] = [[]]
perms (x:xs) = concat (map (interleave x) (perms xs))
interleave :: a -> [a] -> [[a]]
interleave x [] = [[x]]
interleave x (y:ys) = (x:y:ys) : map (y:) (interleave x ys)
식을 생성하는 과정 중에 결과 값이 양의 정수가 아닐 수가 있다. 이 경우에는 바로 유효하지 않은 식으로 처리하면 된다. 이것을 위해 제대로 된 값을 가지는 식과 그 값을 순서쌍으로 묶은 아래의 타입을 정의하자.
type Result = (Expr, Int)
results :: [Int] -> [Result]
results [] = []
results [n] = [(Val n, n) | n > 0]
results ns = [res | (ls, rs) <- split ns, lx <- results ls, ry <- results rs, res <- combine lx ry]
-- 하나의 리스트를 두 개의 비어 있지 않은 리스트로 나눈다.
split :: [a] -> [([a], [a])]
split [] = []
split [_] = []
split (x:xs) = ([x], xs) : [(x:ls, rs) | (ls, rs) <- split xs]
- 주어진 두 식의 가능한 모든 연산을 적용하여 유효한 식을 돌려준다.
combine :: Result -> Result -> [Result]
combine (l,x) (r,y) = [(App o l r, apply o x y) | o <- ops, valid o x y]
ops :: [Op]
ops = [Add, Sub, Mul, Div]
- Countdown Problem
여러 개의 수들과 목표로 하는 결과값이 주어지면, 주어진 여러 개의 수들로부터 원하는 숫자를 골라 덧셈, 뺄셈, 곱셈, 나눗셈 및 괄호를 써서 식을 만들어, 그 만들어진 식의 계산 결과가 목표로 하는 결과값과 같도록 하는 문제(주어진 숫자들은 많아야 한 번씩만 식에 나타나야 하며, 계산 중간값을 포함한 계산에 쓰이는 모든 수들은 반드시 양의 정수여야 한다.).
예를 들어, 1,3,7,10,25,50로부터 765를 결과값으로 계산하기를 생각해보자. (1 + 50) * (5 - 10) 가 가능한 식의 하나가 될 것이다.
- 문제 풀이
네가지 수치 연산을 나타내는 타입을 다음과 같이 정의한다.
data Op = Add | Sub | Mul | Div
연산을 수행하는 함수 apply를 다음과 같이 정의한다.
apply :: Op -> Int -> Int -> Int
apply Add x y = x + y
apply Sub x y = x - y
apply Mul x y = x * y
apply Div x y = x `div` y
apply를 적용하기 전에 그 결과가 양의 정수인지 알아보는 함수 valid를 다음과 같이 정의한다.
valid :: Op -> Int -> Int -> Bool
valid (Add x y) = x <= y
valid (Sub x y) = x > y
valid (Mul x y) = x /= 1 && y /=1 && x <= y
valid (Div x y) = y /= 1 && x `mod` y == 0
덧셈의 경우 (Add 3 2)와 (Add 2 3)은 결과가 같기 때문에 하나만 계산하면 되고, 곱셈의 경우 x나 y가 1인 경우나 나눗셈의 경우 y가 1인 경우는 1인 값이 없는 경우와 같다. 따라서 이러한 경우는 더이상 계산하지 않고 유효하지 않은 값으로 처리한다.
이제 수식을 나타내는 타입을 아래와 같이 정의한다.
data Expr = Val Int | App Op Expr Expr
이 타입을 써서 식이 주어졌을 때 식의 결과 값을 돌려주는 eval 함수를 정의한다.
eval :: Expr -> [Int]
eval (Val n) = [n | n > 0]
eval (App o l r) = [apply o l r | x <- eval l, y <- eval r, valid o x y]
성공하면 한원소 리스트를 값으로 돌려주고, 실패의 경우는 빈 리스트를 값으로 돌려준다.
이제 가능한 모든 식을 통해 결과를 찾는 함수를 정의해보자.
solutions :: [Int] -> Int -> [Expr]
solutions ns n = [e | ns <- choices ns, (e, m) <- results ns, m == n]
이 식의 구현은 다음과 같이 생각할 수 있다. 양의 정수가 주어지면 이것으로 0개 이상의 수를 취하여 만들 수 있는 모든 부분 집합을 생성한다(choices). 이 부분 집합에 가능한 모든 계산 식을 적용한다(results ns). 이 계산 식의 값이 결과 값과 같으면 이 계산 식은 답이 된다.
그럼 먼저 choices를 정의해 보자.
이 함수는 주어진 리스트의 부분 집합을 만들고 이를 순서를 바꾸어 가능한 모든 수를 만들어 내면 된다. 부분 집합을 만드는 함수를 subs라 하고 부분 집합의 순서를 바꾸는 함수를 perms라 하면 choices는 아래와 같이 정의 된다.
choices :: [a] -> [[a]]
choices xs = concat (map perms (subs xs))
subs [] = [[]]
subs (x:xs) = yss ++ map (x:) yss
where yss = subs xs
perms :: [a] -> [[a]]
perms [] = [[]]
perms (x:xs) = concat (map (interleave x) (perms xs))
interleave :: a -> [a] -> [[a]]
interleave x [] = [[x]]
interleave x (y:ys) = (x:y:ys) : map (y:) (interleave x ys)
식을 생성하는 과정 중에 결과 값이 양의 정수가 아닐 수가 있다. 이 경우에는 바로 유효하지 않은 식으로 처리하면 된다. 이것을 위해 제대로 된 값을 가지는 식과 그 값을 순서쌍으로 묶은 아래의 타입을 정의하자.
type Result = (Expr, Int)
results :: [Int] -> [Result]
results [] = []
results [n] = [(Val n, n) | n > 0]
results ns = [res | (ls, rs) <- split ns, lx <- results ls, ry <- results rs, res <- combine lx ry]
-- 하나의 리스트를 두 개의 비어 있지 않은 리스트로 나눈다.
split :: [a] -> [([a], [a])]
split [] = []
split [_] = []
split (x:xs) = ([x], xs) : [(x:ls, rs) | (ls, rs) <- split xs]
- 주어진 두 식의 가능한 모든 연산을 적용하여 유효한 식을 돌려준다.
combine :: Result -> Result -> [Result]
combine (l,x) (r,y) = [(App o l r, apply o x y) | o <- ops, valid o x y]
ops :: [Op]
ops = [Add, Sub, Mul, Div]
2015년 1월 7일 수요일
Water Pouring Problem
Coursera의 Functional Programming in Scala에서 설명한
the Water Pouring Problem의 코드 설명
/**
* the Water Pouring Problem
* 정해진 용량의 컵에 물을 따라서 원하는 용량의 물을 가지고 있는 glass 만들기.
* 예를 들어 4와 7의 용량을 가질 수 있는 두개의 컵을 가지고
* 6의 용량을 가지도록 하는 방법은?
*/
class Pouring(capacity: Vector[Int]) {
// States
type State = Vector[Int]
val initialState = capacity map (x => 0)
// Moves
// State를 변경한다.
trait Move {
def change(state: State): State
}
// 컵을 비운다.
case class Empty(glass: Int) extends Move {
def change(state: State) = state updated (glass, 0)
}
// 컵을 채운다.
case class Fill(glass: Int) extends Move {
def change(state: State) = state updated (glass, capacity(glass))
}
// 다른 컵에 따른다.
case class Pour(from: Int, to: Int) extends Move {
def change(state: State) = {
val amount = state(from) min (capacity(to) - state(to)) // 넘치지 않도록 하기위한 양
state updated (from, state(from) - amount) updated (to, state(to) + amount)
}
}
val glasses = 0 until capacity.length
// 옮겨갈 수 있는 상태들
// 예를 들어 아래와 같이 할 경우
// val problem = new Pouring(Vector(4, 7))
// problem.moves
// 결과는 아래와 같이 된다.
// Vector(Empty(0), Empty(1), Fill(0), Fill(1), Pour(0,1), Pour(1,0))
val moves =
(for (g <- glasses) yield Empty(g)) ++
(for (g <- glasses) yield Fill(g)) ++
(for (from <- glasses; to <- glasses if from != to) yield Pour(from, to))
// Paths: sequences of moves
// history: 최신 move가 앞에 오는 list.
class Path(history: List[Move], val endState: State) {
def extend(move: Move) = new Path(move :: history, move change endState)
// move를 순서대로 보여준 후 --> state 변경에 따른 마지막 state 출력
override def toString = (history.reverse mkString " ") + " --> " + endState
}
val initialPath = new Path(Nil, initialState)
// explored를 통해 이미 방문한 state는 제거한다.
def from(paths: Set[Path], explored: Set[State]): Stream[Set[Path]] =
if (paths.isEmpty) Stream.empty
else {
val more = for {
path <- paths
next <- moves map path.extend
if !(explored contains next.endState)
} yield next
paths #:: from(more, explored ++ (more map (_.endState)))
}
val pathSets = from(Set(initialPath), Set(initialState))
// 예를들어
// val problem = new Pouring(Vector(4, 7))
// problem.solution(6)
// 결과는
// Fill(1) Pour(1,0) Empty(0) Pour(1,0) Fill(1) Pour(1,0) --> Vector(4, 6)
// state의 변화를 적어보면
// (0, 7) -> (4, 3) -> (0, 3) -> (3, 0) -> (3, 7) -> (4, 6)
def solution(target: Int): Stream[Path] =
for {
pathSet <- pathSets
path <- pathSet
if path.endState contains target
} yield path
}
the Water Pouring Problem의 코드 설명
/**
* the Water Pouring Problem
* 정해진 용량의 컵에 물을 따라서 원하는 용량의 물을 가지고 있는 glass 만들기.
* 예를 들어 4와 7의 용량을 가질 수 있는 두개의 컵을 가지고
* 6의 용량을 가지도록 하는 방법은?
*/
class Pouring(capacity: Vector[Int]) {
// States
type State = Vector[Int]
val initialState = capacity map (x => 0)
// Moves
// State를 변경한다.
trait Move {
def change(state: State): State
}
// 컵을 비운다.
case class Empty(glass: Int) extends Move {
def change(state: State) = state updated (glass, 0)
}
// 컵을 채운다.
case class Fill(glass: Int) extends Move {
def change(state: State) = state updated (glass, capacity(glass))
}
// 다른 컵에 따른다.
case class Pour(from: Int, to: Int) extends Move {
def change(state: State) = {
val amount = state(from) min (capacity(to) - state(to)) // 넘치지 않도록 하기위한 양
state updated (from, state(from) - amount) updated (to, state(to) + amount)
}
}
val glasses = 0 until capacity.length
// 옮겨갈 수 있는 상태들
// 예를 들어 아래와 같이 할 경우
// val problem = new Pouring(Vector(4, 7))
// problem.moves
// 결과는 아래와 같이 된다.
// Vector(Empty(0), Empty(1), Fill(0), Fill(1), Pour(0,1), Pour(1,0))
val moves =
(for (g <- glasses) yield Empty(g)) ++
(for (g <- glasses) yield Fill(g)) ++
(for (from <- glasses; to <- glasses if from != to) yield Pour(from, to))
// Paths: sequences of moves
// history: 최신 move가 앞에 오는 list.
class Path(history: List[Move], val endState: State) {
def extend(move: Move) = new Path(move :: history, move change endState)
// move를 순서대로 보여준 후 --> state 변경에 따른 마지막 state 출력
override def toString = (history.reverse mkString " ") + " --> " + endState
}
val initialPath = new Path(Nil, initialState)
// explored를 통해 이미 방문한 state는 제거한다.
def from(paths: Set[Path], explored: Set[State]): Stream[Set[Path]] =
if (paths.isEmpty) Stream.empty
else {
val more = for {
path <- paths
next <- moves map path.extend
if !(explored contains next.endState)
} yield next
paths #:: from(more, explored ++ (more map (_.endState)))
}
val pathSets = from(Set(initialPath), Set(initialState))
// 예를들어
// val problem = new Pouring(Vector(4, 7))
// problem.solution(6)
// 결과는
// Fill(1) Pour(1,0) Empty(0) Pour(1,0) Fill(1) Pour(1,0) --> Vector(4, 6)
// state의 변화를 적어보면
// (0, 7) -> (4, 3) -> (0, 3) -> (3, 0) -> (3, 7) -> (4, 6)
def solution(target: Int): Stream[Path] =
for {
pathSet <- pathSets
path <- pathSet
if path.endState contains target
} yield path
}
2014년 3월 11일 화요일
음악을 랜덤으로 들을 수 있게 하기 by spotify
How to shuffle songs?
http://labs.spotify.com/2014/02/28/how-to-shuffle-songs/
요약:
random이란? 정말로 랜덤하게 음악을 섞어서 보여주는것
Fisher-Yates shuffle
그러나 실 사용자들은 랜덤을 그렇게 받아들이지 않는다. 예를 들어 같은 가수의 음악이 연속으로 들린다면 사용자들은 랜덤이 아니라고 여긴다.
사용자가 랜덤이라고 느낄 수 있도록 알고리즘을 수정할 필요가 있다.
Martin Fiedler 라는 사람의 The art of shuffling music 라는 블로그 내용이 있다. 앞에서 말한 문제를 해결해주는 알고리즘이지만 너무 복잡하다.
이에 따라 여기에 Floyd-Steinberg dithering 같은 알고리즘을 써서 같은 종류로 구분되는(예를 들면 같은 작곡가 또는 같은 가수) 음악을 흐트려 놓는 수정을 가하였다.
http://labs.spotify.com/2014/02/28/how-to-shuffle-songs/
요약:
random이란? 정말로 랜덤하게 음악을 섞어서 보여주는것
Fisher-Yates shuffle
그러나 실 사용자들은 랜덤을 그렇게 받아들이지 않는다. 예를 들어 같은 가수의 음악이 연속으로 들린다면 사용자들은 랜덤이 아니라고 여긴다.
사용자가 랜덤이라고 느낄 수 있도록 알고리즘을 수정할 필요가 있다.
Martin Fiedler 라는 사람의 The art of shuffling music 라는 블로그 내용이 있다. 앞에서 말한 문제를 해결해주는 알고리즘이지만 너무 복잡하다.
이에 따라 여기에 Floyd-Steinberg dithering 같은 알고리즘을 써서 같은 종류로 구분되는(예를 들면 같은 작곡가 또는 같은 가수) 음악을 흐트려 놓는 수정을 가하였다.
피드 구독하기:
글 (Atom)