DKU/알고리즘 및 실습

Amortized Runtime Analysis: 분할 상환 런타임 분석 알고리즘 A는 아래와 같은 규칙적인 런타임 패턴을 보인다고 하자.각 루프에서는 $\Theta(1)$의 시간이 걸린다.마지막 루프에서는 $\Theta(n)$의 시간이 걸린다.그렇다면 알고리즘 A의 전체 런타임은 얼마일까? $\Theta(n)$이다.마지막 루프에서 발생하는 시간 $\Theta(n)$이 이전 모든 루프에 고르게 분배된다고 가정하면, 각 루프의 평균적인 시간은 여전히 $\Theta(n)$이 된다. 이러한 방식의 런타임 분석을 분할 상환 분석이라 부른다. 하지만, 알고리즘 B는 알고리즘 A와 다소 다르다.대부분의 루프는 $\Theta(1)$의 시간이 걸린다.가끔 드물게 $\Theta(n)$의 시간이 걸리는 루프가 발생한다.이..

레드-블랙 트리는 이진 탐색 트리에 1비트 속성을 추가한 구조로, 각 노드는 빨강 또는 검정색으로 색칠된다. 모든 리프 노드는 NIL이며, 검정색으로 칠해져 있다.이를 레드-블랙 트리 T의 모든 리프에 대해 single sentinel 노드 nil[T] 라고 한다.color[nil[T]]는 항상 검은색이며, 루트 노드의 부모도 nil[T]다. 레드-블랙 트리는 이진 탐색 트리의 모든 속성을 상속받고, nil[T]에 저장된 키 값은 중요하지 않으므로 무시한다.Properties of red-black trees 레드-블랙 트리는 트리의 균형을 유지하기 위해 다음 다섯 가지 속성을 만족한다.모든 노드는 빨강 또는 검정이다.트리의 루트 노드는 항상 검정색이다.모든 리프 노드(센티널 nil[T])는 항상 검정색..

탐색 트리란, 동적 집합 연산을 지원하는 자료구조이다. 딕셔너리와 우선순위 큐로 사용 가능하다.기본 연산은 트리의 높이에 비례하는 시간이 소요된다.노드가 n개인 완전 이진 트리인 경우: $O(\log n)$노드가 n개인 선형 체인의 경우: $O(n)$탐색 트리의 유형에는 이진 탐색 트리, 레드-블랙 트리, B-트리 등이 있다Binary Search Trees트리 높이를 h라 할 때, 많은 동적 집합 연산을 $O(h)$시간 안에 수행할 수 있다.이진 트리는 각 노드가 객체로 구성된 linked list 자료 구조로 표현된다.root[T]는 트리 T의 루트를 가리키며, 각 노드는 다음과 같은 필드를 포함한다.keyleft: 왼쪽 자식right: 오른쪽 자식p: 부모, p[root[T]] = NIL저장된 ke..

Manufacturing Problem공장에서 생산 공정을 최적화하기 위한 문제다.공장의 생산 라인 사이에서 가장 빠른 경로를 찾아, 제품이 공정을 완료하는데 걸리는 시간을 최소화시키는 것이다. 사진에는 두 개의 부품 조립 라인이 있고, n개의 스테이션을 가지고 있다.라인 i에 있는 j번째 스테이션은 $S_{i, j}$로 표기되고, 이 스테이션에서의 조립 시간을 $a_{i, j}$로 표기한다. 이제 하나의 부품이 공장에 들어와 라인 i에 도착하며, $e_i$의 시간을 갖는다.부품이 j번째 스테이션을 통과하고, 다른 라인의 j+1 번째 스테이션으로 향한다. 같은 라인에서의 스테이션을 이동할 때는 비용이 따로 들지 않지만, 다른 라인으로 향할 때는 $t_{i, j}$만큼의 시간이 든다.n번째 스테이션에서 나..

최적의 값을 찾기 위해서는 실행시간이 오래걸린다.하지만 실행시간을 줄이면, 최적의 값을 찾을 수 없게 된다. 대신 근사치(Approximation)를 찾는다.근사치를 찾는 기법에는 Greedy Algorithm과 Dynamic Programming이 있다.Greedy 알고리즘은 선택을 해야 할 때, 현재 순간에서 가장 좋아보이는 선택을 한다.즉, 지역적으로 최적(locally optimal)인 선택을 하여 전역적으로 최적(globally optimal)인 해를 구하고자한다. (Greedy-choice property)탐욕 알고리즘이 항상 최적의 해를 보장하는 것은 아니지만, 특정 문제에서는 최적 해를 최단 경로 알고리즘보다 더 빨리 구할 수 있다.  탐욕 알고리즘의 가장 대표적인 알고리즘이 MST이다.M..

해시 테이블은 딕셔너리를 구현하는데 효과적이다.해시 테이블에서 요소를 검색하는 기대 시간은 O(1)이지만, 최악의 경우 검색 시간은 O(n)이 될 수 있다. 해시 테이블은 가능한 모든 키에 대해 하나의 배열 위치를 할당하는 것이 불가능하거나 비효율적일 때 사용한다.실제 저장되는 키의 개수가 가능한 키의 개수에 비해 작을 때 사용한다. Direct-Address Tables, Hash Tables직접 주소 테이블은 동적 집합(Dynamic set)을 유지 관리 해야한다. 각 요소는 key를 가지며, 두 요소가 동일한 키를 가지지 않는다고 가정한다. Dynamic Set은 원소를 입력, 삭제, 검색할 수 있는 컴퓨터 상에 구현된 집합이다. 학생 30여명의 인적사항 기록을 위한 두가지 형태의 ID(출석번호와 ..

지도에서 두 지점 간의 가장 짧은 경로를 찾는 방법은 다음과 같다.그래프에 방향과 가중치가 표현되어있다고 했을 때, 경로 p는 시작점에서 끝점으로 이어지는 정점의 순서가 된다.w(p)는 경로 p에 포함된 간선들의 가중치 합이 된다. 이 w(p)가 최소일 때, 가장 짧은 경로라고 한다. 그래프에서 노드v에서 노드 u로 갈 수 없는 경우에는, 무한대로 표현한다. 최단 경로는 여러 개가 존재할 수 있으며, 한 노드에서 다른 모든 노드로 가는 최단 경로들은 트리 형태로 구성된다.가중치는 경로를 따라 누적되며, 우리가 최소화해야하는 값으로 해석된다.  최단 경로 문제에는 몇가지 유형이 존재한다.Single-source (단일 출발점): 주어진 출발점 s에서 그래프의 모든 정점 v까지의 최단 경로를 찾는 문제Sin..

주어진 마을에 여러 집과 이를 연결하는 도로가 있다. 각 도로는 두 개의 집을 연결하며, 도로를 수리하는데 비용 w(u, v)이 소요된다. 목표는 최소 비용으로 필요한 도로만 수리하여 모든 집이 서로 연결되도록 하는 것이다. 이 문제는 MST를 구하는 알고리즘으로 해결할 수 있다.수리할 도로 집합 T⊆E를 찾으며, 이때 T는 모든 정점을 연결하면서 최소 비용을 만족하는 스패닝 트리가 되어야한다. 최소 비용 스패닝 트리(Minimum Spainning Tree)란, 주어진 그래프의 모든 정점을 연결하는 모든 스패닝 트리 중에서 가중치의 합이 최소가 되는 트리를 의미한다. 위 그림에서 두껍게 칠해진 선들의 집합을 MST라고 한다. 모든 노드들을 연결하고 있으며, 도합 37이라는 최소 비용을 가지고 있다.간선..

Strongly Connected Components: 강한 연결 성분, SCC주어진 방향 그래프 G = (V, E)에서, SCC는 그래프 G의 최대 정점 집합 C⊆⊆V로, 모든 정점 u, v ∈ C에 대해 u에서 v로의 경로와 v에서 u로의 경로가 모두 존재하는 집합이다. 말이 좀 어렵게 느껴질 수 있는데 그림으로 설명해보자면,정점들을 묶어놓은 것이 부분 집합 C이고, 이 C내의 모든 정점들은 역방향이든 정방향이든 경로가 모두 존재한다는 것이다.타임스탬프 14를 가진 정점과 13을 가진 정점을 보자. 14에서 13으로 향하는 경로도 존재하고, 13에서 14로 향하는 경로도 존재하는 것을 볼 수 있다.경로가 존재하는 정점이 따로 없다면, 타임스탬프 10을 가진 정점처럼 혼자 묶인다. 알고리즘은 $G^T$..

그래프 알고리즘을 배우기에 앞서, 그래프란 무엇일까? 그래프는 $G = (V, E)$는 정점 집합 V와 간선 집합 E로 이루어져 있으며, 방향성이 있을 수도 있고 없을 수도 있다.알고리즘에서 사용하는 그래프 표현 방법에는 두가지가 존재한다.인접 리스트(Adjacency list): 각 정점에 연결된 이웃 정점들을 리스트 형태로 저장한다.인접 행렬(Adgacency matrix): 정점 간의 연결을 행렬 형태로 표현하여, 특정 정점 쌍 간의 연결 여부를 나타낸다.알고리즘의 실행 시간은 보통 정점의 수 |V|와 간선의 수 |E|로 표현된다.점근 표기법을 사용할 때는, 집합의 크기를 나타내는 기호는 생략할 수 있다. $O(V + E)$로 간단히 표현할 수 있다는 의미이다.인접 리스트: Adjacency lis..