1. 너비 우선 탐색(BFS) 우선 루트의 자식들을 차례로 방문하고, 다음 루트 자식의 자식들을 방문하는 이 과정을 계속 반복하면 된다. 1)먼저 시작 정점을 제외한 모든 정점을 방문하지 않음으로 표시하고 큐에 시작 정점을 넣는다. 2)그뒤 그 큐에 들어있는 정점을 deque해서 인접한 정점을 모두 큐에 넣는다. 3)큐에 들어간 정점들을 방문함 표시를 한다. 4)큐가 빌때까지 반복한다. 마지막 (10)을 보면 트리의 모양을 만들 수 있는데 이를 너비 우선 트리라고 한다. 이를 알고리즘으로 나타내면 아래와 같다. BFS의 특징은 1) 재귀적으로 동작하지 않는다. 2) 큐를 사용한다. 3) 두 노드 사이의 최단 경로 혹은 임의의 경로를 찾고 싶을 때 사용한다. 시간 복잡도는 큐에는 V개의 정점이 한번씩 들어..

1. 그래프의 종류 유향 그래프 (Directed Graph) : 그래프의 방향을 가진다. 무향 그래프 (Undirected Graph) : 간선의 방향이 없다 n개의 정점 집합 V와 이들간의 존재하는 간선의 집합 E로 구성된 그래프 G를 G = (V,E)로 표시한다. 2. 그래프의 표현 1) 인접행렬을 이용 그래프 G = (V,E)에서 정점의 총수가 n이라고 하고 정점 i와 정점 j 사이에 간선이 있으면 그때 1이라고 한다. 위와 같은 무향 그래프에서는 양쪽 방향으로 다 갈 수 있음으로 (i,j)와 (j,i)가 같은 대칭으로 나타나지만 유향은 아닐 수 있다. 행렬표현법의 장점은 간선의 존재여부를 즉각 알 수 있다는 것이지만 n*n 행렬을 채워야됨으로 n^2에 비례하는 공간이 필요하고 행렬의 모든 원소를..

집합의 처리를 위해서는 다음 3가지의 연산이 필요하다. 1) Make-Set(x) : 원소 x로만 구성된 집합을 만든다. 2) Find-Set(x) : 원소 x를 가진 집합을 알아낸다. 3) Union(x, y) : 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합친다. 1. 연결리스트 이용 링크드 리스트를 이용하면 하나의 원소로 이루어진 집합은 아래와 같다.(Make-Set으로 만든 결과) 이로 이루어진 두집합을 합치는 과정은 아래와 같다. {a,b,c}집합의 대표 원소를 {d,e,f,g,h}로 바꾸어준다. 이때 작은 집합을 큰집합 뒤에 붙이는 것이 비용적으로 이득이다. 이를 Weighted Union이라고 한다. 수행시간을 비교해보면 Make-Set이나 Find-Set은 상수시간만 든다. Fi..

1. 해시 테이블? 검색트리는 원소가 저장될 자리를 이미 트리에 존재하는 값들과 비교하면서 리프까지 내려가서 자리가 결정된다. 이방법은 평균적으로 Θ(logn)의 시간이 걸리게 된다. 하지만 우리가 아는 배열에 값을 넣는 것은 Θ(n)의 시간이 걸린다. 이 배열을 이용하는 것이 해시 테이블이다. 우선 해시 테이블에 값을 저장하려면 해당 원소의 해시 값을 계산해야 한다. 해시값은 함수로 계산하게 되는데 해시 테이블이 m개의 원소를 저장할 수 있다면 함수는 m-1까지의 값을 return한다. 예를들어 17개의 원소를 저장할 수 있는 해시 테이블이 있고 해시를 계산하는 함수가 x mod 18이라고 하자. 우리가 25를 저장하려고 하면 25 mod 18 = 7임으로 hash[7]에 값이 저장되는 것이다. 해시 ..

1. 특징 B-트리는 다른 이진 트리나 레드 블랙 트리와 달리 한 노드안에 여러개의 키값을 가진다. 이를 다진 검색 트리라고 한다. 위에 처럼 각각의 키값 사이에는 서브트리의 주소가 들어가게 된다. B-트리는 다음 2가지의 성질을 만족하게 된다. 1) 루트를 제외한 모든 노드는 |k/2|~k개의 키를 가진다. 2) 모든 리프노드는 같은 깊이를 가진다. 즉 각 노드는 루트를 제외하면 채울 수 있는 최대 허용량의 반 이상의 키를 채워야하는 것이다. 2. B-트리에서 검색 B-트리에서의 검색은 이진 검색 트리와 같지만 차이점은 한 노드에 여러개의 키가 있다는 것이다. 그래서 찾고자하는 key값이 x라면 key_i-1< x < key_i 를 만족하는 두개의 키값을 찾은 뒤에 그에 해당하는 자식 노드로 내려가야 ..

1. 특징 앞에서의 이진 검색 트리는 평균은 Θ(logn)이지만 균형이 깨진다면 Θ(n)의 시간이 소요된다. 이를 극복하기 위해 레드 블랙트리를 사용한다. 레드 블랙 트리는 이진 검색트리의 노드에 레드 또는 블랙의 색을 칠하는데 그 조건은 아래와 같다. 1) 루트는 블랙이다. 2) 모든 리프(NIL)는 블랙이다 3) 노드가 레드이면 그 노드의 자식은 반드시 블랙이다. 4) 루트 노드에서 임의의 리프노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다. 위의 예시는 아래와 같다. 맨 마지막 리프는 모두 NIL 노드로 다루는데 보통은 모든 리프에 각각 다른 NIL 노드를 달기 버거우니 그냥 하나의 NIL노드를 만들고 모든 리프를 이 노드에 연결시키는 방법을 사용한다. 2. 삽입 레드 블랙 트리에서 삽입..

1. 레코드, 키의 정의 및 검색 트리 레코드는 개체에 대한 모든 정보를 포함한다. 예를들어 사람의 레코드이면 주민번호, 이름, 집주소등이 있다. 여기서 정보를 나타내는 부분을 필드라고 한다. 검색트리는 이런 레코드를 저장하고 검색하는 것이다. 이러한 레코드를 전부다 저장할 수 있지만 보통은 대표레코드인 키를 두어서 이를 이용한다. 예를들어 사람의 레코드에서 키가 될 수 있는 것은 겹칠 수가 없는 주민번호가 있다. 이러한 검색트리는 이진트리와 다진트리로 나누어진다. 이진트리는 한 노드에서 최대 두개의 자식노드를 가지고 다진 트리는 2개이상을 가질 수 있는 것을 의미한다. 2. 이진 검색 트리 이진 검색트리의 특징은 아래와 같다. 1. 이진 검색 트리의 각 노드는 키 값을 하나씩 가진다. 각 노드의 키 값..

t1. 평균 선형 시간 선택 알고리즘 i번째 원소를 찾는 알고리즘은 앞에서 퀵소트의 파티션을 이용한다. 아래는 그 과정을 나타낸 그림이다. 파티션을 하면 기준원소가 몇번째에 있는지는 확실히 알 수 있다. 이를 이용해서 i번째 원소를 찾는 것이다. 이에 대한 알고리즘은 아래와 같다. 아래는 직접 구현해본 코드이다. def partition(A, p, r): standard = A[r] part_1 = p for part_3 in range(p, r): if A[part_3] k: return quickselect(data, start, partition_-1, k) elif partition_ < k: return quickselect(data, partition_+1, end, k) 이 알고리즘의 최악의..

앞에서의 알고리즘들은 원소 두개를 비교함으로서 정렬을 하는 비교정렬이고 이 비교정렬은 Θ(nlogn)을 넘지 못한다는 것이 알려져 있다. 이제 보일 알고리즘은 특수한 경우에서 이 한계를 극복할 수 있는 알고리즘이다. 1. 기수 정렬(Radix Sort) 기수 정렬은 입력이 모두 k 자릿수이하인 특수한 경우에 사용할 수 있다. 알고리즘은 아래와 같다. 그림을 보면 이해가 더 쉬운데 위와 같이 1번째 자리부터 그 한자리 수만 비교하여 정렬을 하는 것이다. 만일 같은 수일경우에는 순서를 유지하여 안정성을 유지한다. 이때 중요한 것이 만일 정렬을 할때 앞에서 나온 퀵정렬, 병합정렬등을 사용하게 되면 Θ(nlogn)이 나와서 다른 방법과 다를게 없게 된다. 따라서 미리 0~9의 자리가 들어갈 공간을 마련하여 그곳..

1. 병합 정렬(merge sort) 이 알고리즘은 입력을 반으로 나누고 나눈 앞부분과 뒷부분을 따로 정렬을 한다. 그다음에 그 정렬된 배열을 다시 합치는 방식이다. 알고리즘은 아래와 같다. 아래는 구현 과정이다. merge부분은 비교적 간단한데 정렬된 A[p...q], A[q+1...r]을 하나씩 비교하며 작은 것을 새로운 배열인 temp에 넣고 나중에 temp에 들어있는 내용을 A 배열로 다시 옮기면 된다. 직접 구현한 코드는 아래와 같다. def mergesort(A, p, r): if p