School/DataStructure

Data Structure - Graph ( DFS, BFS )

DFS 이는 깊이 우선 탐색이라고도 하며, 루트 노드 ( 혹은 다른 임의의 노드)에서 시작해서 다음 분기로 넘어가기 전에 해당 분기를 deep하게 탐색하는 방법입니다. 미로를 탐색할 때 한 방향으로 갈 수 있을 때까지 계속 가다가 더 이상 갈 수 없게 되면 다시 가장 가까운 갈림길로 돌아와서 이곳부터 다른 방향으로 다시 탐색을 진행하는 방법과 유사합니다. 즉, 넓게(wide)탐색하기 전에 깊게(deep)탐색 하는 것입니다. 사용하는 경우 : 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택합니다. BFS 이는 너비 우선 탐색이라고도 하며, 루트 노드(혹은 다른 임의의 노드)에서 시작해서 인접한 노드를 먼저 탐색하는 방법입니다. 시작 정점으로부터 가까운 정점을 먼저 방문하고 멀리 떨어져 있는 정점을 나..

Data Structure - Tree ( Forests )

Forests forest란 n>=0인 disjoint tree들을 말합니다. 우리는 이러한 forest를 가지고 활용을 할 겁니다. 먼저 다음과 같이 S1 = {0, 6, 7, 8}, S2 = {1, 4, 9}, S3 = {2, 3, 5}이렇게 있다고 해 봅시다. 이 들은 모두 disjoint한 set들입니다. 만약에 Si와 Sj가 disjoint한 집합들이면, Si union Sj가 존재하게 됩니다. 만약 S1과S2를 합치게 되면 아래와 같은 두 그림이 될 수 있습니다. Representation of Sets 우리는 이러한 집합들을 표현할 수 있는 방법을 정의해야 합니다. 우리는 root pointer가 각각의 set name에 해당하는 포인터를 가리키게 해야 합니다. 다음 과 같은 예시를 봅시다...

Data Structure - Tree ( Selection Tree )

Selection Tree 우리는 k개의 연속된 sequence가 있게 됩니다. 이를 우리는 runs라고 합니다. 이들은 모두 하나의 배열로 정렬되어 나올겁니다. 그리고 각각의 runs들은 오름차순으로 정렬되어 있습니다. 그리고 그 안의 값들을 key라고 합니다. 그리고 n을 우리는 이제부터 records의 개수로 정의할 수 있습니다. 그리고 위 runs sequence를 가지고 정렬을 하려면 merging task을 수행해 주어야 합니다. 반복적으로 가장 작은 키를 도출해 내면서 말이죠, 이 때 k - 1번의 비교가 필요하게 됩니다. 그리고 k > 2인 상황에서, 우리는 reduction작업을 통해 winner and loser tree를 구성해 낼 수 있게 됩니다. Winner Trees 우리는 이를..

Data Structure - Tree ( BST )

BST ( Binary Search Tree ) BST의 정의에 대해 간간히 정의하고 가겠습니다. 이는 비어 있을 수도 있습니다. 만약 비어 있지 않다면 다음과 같은 조건을 만족하게 됩니다. 각각의 노드는 하나의 key만을 가지고 있습니다. 그리고 tree안에 있는 모든 key들은 distinct즉 다 다릅니다. 그리고 left subtree 에 있는 모든 키는 root의 key보다 작아야 하고, right subtree에 있는 모든 키는 커야 합니다. 그리고 left와 right subtrees는 둘다 BST입니다. disjoint하다고 표현하죠 다음은 BST의 전형적인 예시입니다. 맨 왼쪽은 BST가 될 수 없는데 딱봐도 아니게 생겼습니다. Insertion 이번에는 트리를 insert하고 이를 pr..