자료구조 (16) 썸네일형 리스트형 자료구조 - Sorting Sorting sorting은 array에 저장되어 있는 원소들을 값이 커지는 순서 혹은 값이 작아지는 순서로 재배열하는 것을 의미한다. sorting에는 각각의 원소를 비교하여 해당 원소보다 큰지 작은 지를 확인해야 하기 때문에 relational operator가 잘 정의돼야 한다. 아래의 정렬 방법들을 살펴볼 때 오름차순과 내림차순은 단순히 정렬하는 순서를 바꾸면 동일함으로 모든 경우 오름차순으로 정렬함을 가정하겠다. Selection Sort 가장 기본적인 정렬 방법으로 정렬되지 않은 array에서 가장 작은 값을 찾은 뒤 해당하는 값을 정렬되어 있는 배열의 뒤로 붙이는 방법이다. 만약 N개의 배열을 selection sort를 사용하여 정렬한다면 $\sum\limits_{i = 1}^{N - 1.. 자료구조 - DFS & BFS (Graph Searching) Graph Searching 그래프에서 두 노드 사이에 path를 찾기 위해서는 두 노드사이의 edge들을 찾아서 연결되는지 확인을 해야 하는데 이러한 동작을 하는 방식으로 대표적으로 DFS와 BFS가 있다. DFS DFS는 깊이 우선 방식으로 모든 노드들을 다 방문할 때 현재 노드에서 edge를 통해 갈 수 있는 모든 노드들을 stack에 저장을 한다. 그리고 stack에 pop을 하여 pop이 된 위치에서 갈 수 있는 모든 노드들을 바로 stack에 append 해준다. 만약 이전에 방문했던 노드가 있다면 해당 노드는 다시 방문할 필요가 없으므로 이전에 방문을 하였는지 따로 확인할 수 있는 mark가 필요하다. 이렇게 stack의 모든 노드들이 없어지거나 원하는 노드에 방문할 때까지 반복을 하여 만약.. 자료구조 - 그래프 그래프 그래프는 vertex들의 집합으로 각각의 vertex를 연결하는 edge가 존재하여 vertex 간의 관계를 표현한다. 그래프는 G = (V, E) 형태로 표현되는데 여기서 V는 vertex들의 집합으로 유한하고 비어있지 않고, E는 edge들의 집합을 의미한다. edge가 있을 때 vertex간의 방향이 존재할 수도 있고 존재하지 않을 수도 있다. 만약 vertex간의 방향이 존재하지 않는다면 undirected graph라고 하고 연결되어 있는 순서가 중요하지 않게 된다. 반면 vertex간의 방향이 존재한다면 directed graph라고 하고 연결되는 순서가 중요해져서 만약 1번 vertex와 3번 vertex가 있을 때 1 -> 3으로만 edge가 존재할 경우 3에서 1로는 이동할 수가 .. 자료구조 - 우선순위 큐(Priority Queue) 우선순위 큐 우선순위 큐는 ADT로 언제든지 가장 우선순위가 높은 요소에 접근이 가능한 큐를 의미한다. 우선순위 큐는 기본적으로 큐이기 때문에 데이터를 삽입하고 삭제할 수 있는 Enqueue와 Dequeue가 존재한다. 이때 Enqueue는 기존의 queue와 동일하게 그냥 삽입하면되지만 Dequeue의 경우 가장 먼저 입력된 값이 아닌 우선순위가 높은 예를들면 가장 큰 값이 출력되야 한다. 우선순위 큐는 우선순위가 높은 값을 가장 가져올 수만 있으면 되기 때문에 Unsorted List, Sorted List , Linked List, Binary Search Tree, Heap 등 어떠한 과정으로도 만들 수 있다. 하지만 Unsorted List는 Dequeue를 하는 과정에서 모든 요소들을 확인해야.. 자료구조 - Heap Heap Heap은 이진트리에서 리프 노드를 제외하고 빠져있는 부분이 없는 complete binary tree 모양을 가지고, 모든 노드의 자식 노드는 자기 자신의 값보다 작은 값을 가지고 있는 순서 조건을 만족하는 트리이다. 일반적으로 Heap은 자식 노드들이 항상 부모 노드보다 작기 때문에 루트에 가장 큰 원소가 들어가 max-heap이라고 한다. 하지만 반대로 부모 노드가 항상 작게도 Heap을 구현할 수 있는데 이러한 경우는 min-heap이라고 한다. Heap은 complete binary tree이기 때문에 중간에 비어있는 노드가 있으면 안돼서 일반적인 tree처럼 Linked List로 구현하는 것보다 array로 구현하는 것이 더 쉽다. 일반적으로 array로 tree를 구현했을 때 단점.. 자료구조 - 트리 트리라는 것은 노드들이 나무처럼 연결되어 있는 계층적인 자료구조이다. 트리에서 가장 위의 노드를 루트노드라고 하고, 제일 밑의 노드를 리프 노드라고 한다. 그리고 A노드와 B노드가 서로 연결되어 있을 때 상위에 있는 노드를 부모 노드라고 하고, 하위에 있는 노드를 자식 노드라고 한다. 트리에서 부모는 반드시 하나이고 child는 여러 개여도 된다. 이때 자식의 수가 많아야 2개이면 binary tree라고 한다. 트리에서 루트에서 다른 노드까지의 연결된 길을 path라고 하는데 트리는 다른 노드와의 path가 유일해야 한다. 부모를 포함해서 자신보다 위에 있는 노드를 ancestor라고 하고, 자식을 포함해서 자신보다 아래에 있는 노드를 descendant라고 한다. 루트노드를 depth(level)가 .. 자료구조 - Recursion(재귀) 재귀라는 것은 메서드를 호출할 때 호출 하는 것과 호출당하는 것이 동일한 것을 의미한다. 이때 직접적으로 호출되지 않더라도 호출을 계속하다 보니 다시 호출되는 경우도 재귀의 한 종류로 Indirect recursion이라고 한다. 예를 들어 f라는 함수에서 g를 호출하고 g에서 h를 호출한 다음 h에서 f를 호출하는 경우를 Indirect recursion의 한 종류로 볼 수 있다. 컴퓨터 언어에 따라 recursion을 사용할 수 없는 언어도 있는데 대표적으로 Fortran이 있다. 이러한 경우는 모든 재귀는 루프를 통해 표현할 수 있다는 점을 이용해서 for나 while문으로 루프를 사용해야 한다. 재귀는 일반적으로 효율성이 떨어진다. 그 이유를 살펴보면 재귀는 기본적으로 실행하면 함수를 호출 했을 .. 자료구조 - Linked List(Circular, Doubly Linked list) Sorted List에서 가장 마지막에 값을 추가하거나 삭제를 해야할 때 매번 N번의 연산을 통해서 마지막 노드를 접근할 수 있다. 이러한 과정은 효율적이지 못하므로 마지막 값을 따로 접근할 수 있는 방법이 있으면 좋다. 따라서 원형 연결 리스트를 통해서 마지막 노드의 다음 노드로 가장 첫 번째 노드를 지정해 줘서 리스트의 ListData가 가장 마지막 노드를 포인팅하고 있으면 된다. 또한 Linked List로 삽입과 삭제를 구현할 때 다음 노드의 값에 따라 삽입 또는 삭제의 여부가 결정되기 때문에 구현하는 과정에서 다음 다음 노드의 값을 확인하던지 이전 노드를 가리키고 있는 포인터를 사용하였었다. Circular Linked List를 python으로 구현하면 다음과 같다. class Circular.. 이전 1 2 다음
