혼자 정리

지금 있는 자리에서 가능하다면 계속 깊게 파고 내려가는 것이 DFS 정점 $v$가 아직 탐색하지 않은 간선을 남겨두고 있다면 남은 간선을 전부 탐색해야 한다. $v$의 모든 간선을 탐색한 후에는 "backtrack"해서 다른 간선을 탐색하러 이동한다. 이 과정을 소스 정점에서 도달 가능한 모든 정점을 확인할 때까지 반복한다. 만약 탐색하지 못한 정점이 남아있다면 DFS는 그 중 하나를 골라서 새로운 소스로 삼고 과정을 다시 반복한다. BFS와 마찬가지로 이미 발견한 정점 $u$의 인접 리스트를 탐색하는 과정에서 정점 $v$를 발견하면 $v$의 직전 노드 속성인 $v. \pi$를 $u$로 기록한다. BFS의 predecessor 서브그래프가 트리를 형성하는 것과 다르게 DFS의 predecessor 서브그..

x = L.head while x ≠ NIL and x.key ≠ ㅏ x = x.next return x 연결 리스트는 객체를 선형 순서로 배열한 자료 구조이다. 배열과 달리 연결 리스트는 각 객체의 포인터를 통해 결정된다. 'doubly linked list' $L$은 'key'와 포인터 변수인 'next'와 'prev'를 특성(attribute)으로 갖는 객체들을 원소로 갖는다. 'singly linked list'인 경우 'prev'포인터가 존재하지 않는다. 리스트의 요소 $x$에 대해 $x.prev$는 $x$ 직전 원소를 가리키고 $x.next$는 $x$ 다음 요소를 가리킨다. $x.prev = NIL$인 경우 $x$는 직후의 요소가 없으므로 마지막 요소이다. 이를 'tail'로 부른다. $L.h..

스택과 큐는 제거 행위로 집합에서 제거될 원소가 미리 명시된 동적 집합의 일종이다. 스택은 후입선출(last-in, first-out; LIFO). 큐는 선입선출(first-in, first-out; FIFO). 구현에 다양한 방법이 있지만 여기서는 배열을 통한 구현을 다룬다. Stacks 스택의 'Insert' 행위는 'Push'라 부르고 'Delete'행위는 'Pop'이라 부른다. 최대 $n$개의 원소를 가진 스택을 배열 $S[1 \cdots n]$으로 구현할 수 있다. '$S.top$'은 가장 최근에 삽입된 원소의 배열에서의 인덱스를 나타내느 $S$의 속성(attribute)이다. 즉, 스택은 원소 $S[1 \cdots S.top]$을 가지고 있고, $S[1]$은 스택 최하단에, $S[S.top]$..

그래프를 $G= (V, E)$라 하면 $V$는 정점(vertice)의 집합, $E$는 간선(Edge)의 집합을 의미한다. $|V|$는 정점의 갯수, $|E|$는 간선의 갯수를 의미. 점근적 표기에서 $V$는 $|V|$를 의미하고, $E$는 $|E|$를 의미한다. 즉, $O(VE)$는 $O(|V||E|)$의 의미로 사용된다. 또한, 수도 코드에서는 그래프 $G$의 정점 집합을 $G.V$로, 간선 집합은 $G.E$로 표기한다. 즉, 수도 코드에서는 정점과 간선을 그래프의 속성으로 본다. undirected graph : 간선에 방향이 없는 그래프를 의미. $u,v \in V$를 잇는 간선을 $(u,v)$와 $(v, u)$로 나타낼 수 있다면 두 표현이 같은 간선을 나타낸다.(간선 하나는 정점의 집합으로 이루..

특정 기간 내에 어떤 자산을 매수/매도를 해서 가장 높은 수익률을 내는 문제를 생각해 보자. 가장 낮은 가격이 등장한 뒤에 가장 높은 가격이 등장하면, 두 가격을 찾아서 매수/매도를 하면 되지만 일반적으로 그렇지 않다. A brute-force solution 기간의 범위가 n개로 쪼개져있다고 했을 때 단순하게 모든 매수/매도 선택지에 대해 최대 수익률을 구하기 위해서는 $\binom{n}{2}$번의 연산을 해야 하고, 이는 $\Theta(n^2)$의 시간이 필요함을 의미한다. 이는 최악의 경우도 아니고 최선의 경우에도 모든 것을 찾는 것이므로 $\Omega(n^2)$의 시간으로 볼 수 있다. A transformation 문제를 더 효율적으로 풀기 위해 우선 각 날짜의 '가격' 즉, 수준 변수 대신 날..