기록보관소

벨만-포드 알고리즘 벨만-포드 알고리즘은 가중치를 가지는 방향그래프의 최단거리를 구하는 데 사용되는 알고리즘입니다. 특징으로 음의 가중치를 가지는 경우에도 사용할 수 있습니다. 또한 출발점에서 도달가능한 음의 순환의 존재 여부를 확인할 수도 있습니다. 음의 순환이 존재하면 최단거리는 구할 수 없습니다. 모든 최단경로는 순환을 가지지 않으며 따라서 한 정점을 두 번 이상 방문하지 않습니다. 그래프에 정점이 V개 있다면 최단 경로는 최대 V-1개의 간선을 가질 수 있습니다. 최단거리 계산에는 출발점에서 도착점까지의 경로를 순서대로 완화함으로써 최단거리 값을 구할 수 있다는 정리가 이용됩니다. 그래프의 모든 간선을 V-1번 완화(노드의 추정최단거리 값을 갱신하는 행위)하면 한 출발점에서의 모든 다른 노드까지로..

리스트에서 정렬된 원소 중 특정 원소를 logn 시간 내에 찾는 알고리즘이다. 혹은 특정 원소가 리스트에 없음을 확인하는 알고리즘이다. 리스트의 중간값과 찾고자 하는 값을 비교하고 만약 찾고자 하는 값이 더 크면 리스트의 하한을 중간보다 1만큼 높은 값으로 바꾸고, 더 작으면 리스트의 상한을 중간보다 1만큼 낮은 값으로 바꾼다. 탐색하는 범위를 절반씩 줄여나가면서 결국에는 원하는 값을 리스트에서 찾거나 찾지 못하게 된다. 절반씩 범위를 줄여나가므로 lgN만큼의 시간이 소요된다.

두 양의 정수 a, b에 대해서 a를 b로 나눈 나머지로 다시 b를 나누는 과정을 반복했을 때 마지막에 나머지가 0일 때 나누는 수가 a, b의 최대 공약수가 된다는 정리이다. 증명 a와 b를 동시에 나누는 약수는 b로 a를 나누었을 때 나오는 나머지와 b를 동시에 나눈다. a는 b의 배수와 나머지의 합으로 표현되는 데 b는 공통인 약수로 나누어지기 때문에 나머지 또한 공통인 약수로 나누어져야만 a가 나누어질 수 있다. 따라서 공통인 약수는 b와 나머지 사이에서도 공통이 된다. 또한 최대 공약수 또한 같아진다. 만약 최대 공약수가 다르다고 가정하면 나머지와 b사이의 최대공약수는 a와 b를 동시에 나눌 수 있기 때문에 모순이 생기게 된다. 이러한 최대공약수가 공통인 특성을 이용하여 반복적으로 수식을 계산함..

원소를 삽입할 때 Enqueue, 원소를 제거할 때 Dequeue를 한다. 큐는 FIFO(first in, first out, 선입선출)의 특성을 같는다. 큐는 머리(head)와 꼬리(tail)을 갖는 데, 원소는 꼬리로 삽입되고 머리에서 제거된다. tail은 원소가 삽입될 위치를 가리키며 head는 삭제될 원소를 가리킨다. 따라서 head=tail이면 큐는 비어있으며, 이때 원소를 삭제하려고 하면 underflow가 발생한다. head=tail+1 또는 head=1일 때 tail이 배열의 마지막 원소를 가리키는 상태이면 큐가 가득찬 상태이며, 이때 원소를 삽입하려고 하면 overflow가 발생한다. 수행시간 Enqueue와 Dequeue에는 O(1)만큼의 시간이 걸린다.

가장 최근에 삽입된 원소부터 삭제되는 동적 집합 자료 구조(후입선출, LIFO, Last in First out) 원소를 삽입하는 연산은 push, 원소를 추출하는 연산을 pop이라고 한다. 스택의 top은 가장 최근에 삽입된 원소를 가리킨다. top = 0 이면 스택을 비어있다는 것이며 이때 pop을 실행하면 스택 부족(underflow) 오류가 발생한다. 반대로 스택이 가득찬 상태에서 원소를 삽입하면 스택 포화(overflow) 오류가 발생한다. push, pop의 수행시간 모두 O(1)의 수행시간이 걸린다.

그래프를 깊이 검색하는 알고리즘이다. 최근에 발견되었으나 아직 조사되지 않은 간선을 가진 정점에서 나오는 간선을 조사하고, 그 간선들의 조사가 끝나면 그 정점이 유래한 정점으로 되돌아가 해당 정점에서 나오는 간선을 조사한다. 출발점으로부터 도달가능한 모든 정점을 발견할 때까지 검색이 계속되며, 발견되지 않은 정점이 있다면 다른 출발점을 선택하고 검색을 반복한다. 너비 우선 검색과 달리 출발점이 여러 개가 있는 것으로 생각하지만 이는 알고리즘의 응용할 때 필요가 반영된 결과이다. 검색을 하면서 새로운 원소를 발견하면 그 원소에는 직전원소를 기록하며, 이를 통해 직전원소 부분 그래프를 형성할 수 있다. 너비 우선 검색과 달리 출발점이 여러 개가 될 수 있기 때문에 깊이 우선 트리의 개수 또한 여러 개가 될 ..

BFS는 간단한 검색 알고리즘으로 많은 그래프 알고리즘의 원형이 되는 알고리즘이다. 발견된 정점과 발견되지 않은 정점 사이의 경계선을 균일하게 확장시켜나간다는 사실에서 너비 우선 검색이라는 이름이 유래하게 되었다. 즉, 거리가 k인 정점을 모두 탐색한 후에 k+1의 거리를 갖는 정점을 탐색한다는 뜻이기도 한다. 특징적인 부분으로 이 알고리즘은 그래프 내의 하나의 출발점에서 도달이 가능한 모든 정점을 체계적으로 검색하는 알고리즘이다. (검색이란 그래프 내의 정점을 방문하기 위해 간선을 규칙에 맞춰 따라가는 행위이다.) 또한, 출발점에서 도달이 가능한 모든 정점을 포함하는 너비 우선 트리를 만들며, 이때 각 정점까지의 단순 경로는 출발점에서 특정 정점까지의 거리를 의미한다. (거리란 정점과 정점 사이의 최소..

인접 리스트, 인접 행렬로 그래프를 표현할 수 있습니다. 이 두 방식은 방향, 무방향 그래프 모두에 적용할 수 있습니다. 대개 간선의 개수가 적으면 인접 리스트로 표현하며, 간선의 개수가 많은 경우 인접 행렬로 표현합니다. 보통 두 정점을 연결하는 간선이 있는지 빠르게 확인할 때는 인접 행렬을 사용합니다. 인접 리스트 표현법(adjacency-list representation)에서는 V개의 리스트로 그래프의 간선을 표현합니다. 각각의 리스트는 그래프 내의 하나의 정점에 대해 연결된 다른 정점들을 포함합니다. 무방향 그래프의 경우, (u,v)에 대해 u의 리스트와 v의 리스트 각각에 서로의 정점을 저장하고, 방향 그래프의 경우, u의 리스트에 대해 v 정점을 저장합니다. 따라서 무방향 그래프의 경우 리스..

정렬에서는 최악의 경우의 수행시간이 중요하다. 그런데 각 원소를 비교하며 정렬하는 비교정렬의 경우(ex) 병합정렬, 퀵 정렬, 힙정렬 etc) 최악의 경우의 Ω(nlgn) 비교가 필요한다고 한다. 입력에 대해 순서를 결정하기 위해 필요한 비교를 트리로 나타낸 것을 결정트리라고 한다. 어떠한 입력에 대해서도 정렬된 순열을 출력하기 위해서는 입력에 대해 가능한 모든 순열을 만드는 결정트리가 존재해야 한다. 이때 결정트리의 루트와 리프 사이의 가장 긴 거리가 비교 횟수가 가장 많은 최악의 경우이며 이 값은 트리의 높이에 해당한다. n개의 입력에 대해 가능한 순열은 n!이며 이때 트리의 높이는 lg(n!) = Ω(nlg(n)) 이다. 따라서 최악의 경우는 하한은 nlg(n)이다. 즉, 비교 정렬의 경우 아무리 ..

계수정렬은 n개의 입력원소가 있고 각각의 원소가 0부터 k 사이에 있는 정수이며. k=O(n) 일 때 Θ(n) 시간에 수행되는 정렬이다. 계수 정렬은 각 입력 원소 x에 대해 x보다 작은 원소의 개수를 센다. 이 수는 출력 배열에서 원소 x의 위치를 정하는 데 사용된다. 예를 들어, x보다 작은 원소가 5개라면 x는 출력 배열에서 6번째 자리가 된다. 값이 같은 원소가 여러 개 있는 경우에는 모두 같은 자리에 둘 수 없으므로 방법을 약간 고쳐야 한다. 같거나 작은 원소의 개수를 구하여야 하며, 안정성을 유지하기 위해 입력 원소를 뒤에서부터 확인하여 출력배열의 적절한 위치에 넣어야 한다. 계수정렬의 코드에서는 입력 배열과 출력배열, 같거나 작은 원소의 개수를 저장하기 위한 임시 배열이 필요하다. 입력 원소..