이것 저것 뚝딱거리는 사람 이것 저것 뚝딱거리는 사람

플로이드-워셜(Floyd-Warshall) 알고리즘 그래프의 모든 노드 간 최단 거리를 구하는 알고리즘이다. 시간 복잡도는 $O(n^3)$이므로 모든 최단 경로가 필요하지만 노드의 수가 적을 때 사용할 수 있다. 아이디어 한 노드(k)가 다른 두 노드(a, b)의 중간지점이라 생각한다면, a에서 b로 가는 경로는 $a-k-b$ 이다. (k가 a혹은 b라면 경로는 a-b가 된다.) $a-k-b$를 모두 조사한다면 a-b간 최단 경로를 알 수 있다. 아래와 같은 그래프를 가정하면 2를 중간 노드로 둘 경우, 2-2-3, 2-2-5, 3-2-5의 세 가지 경로의 값을 알 수 있다. 이 값들 중에서 3-2-5의 경우 3-5로 가는 경로보다 값이 작으므로 업데이트 해준다. 코드 for k in range(1, n..

이진 탐색 (이분 탐색, Binary Search) 이진 탐색 트리와 같이 정렬된 리스트에서 탐색 범위를 두 부분으로 나누어 특정 값을 찾는 방식 앞이나 뒤에서부터 순서대로 원하는 값을 찾는 순차 탐색보다 훨씬 빠르다. 순차 탐색은 $O(N)$의 시간 복잡도를 가지나, 이진 탐색은 $O(logN)$의 속도를 가진다. 빠르기 때문에 효율성을 따져서 무언가를 찾는 문제에서 생각해 볼법하다. 알고리즘 우선 정렬된 리스트에서 최소값의 인덱스를 left, 최대값의 인덱스를 right로 둔다. left와 right를 통해 mid를 만들어준다. mid와 찾는 값$x$ 비교 mid가 더 큰 경우 left = mid+1, mid가 더 작은 경우 right = mid-1 2, 3, 4번을 left>right가 될 때까지 ..

해시 이번에는 해시, 해시테이블에 대해서 알아보자 이전에 배웠던 자료형들은 값을 여러가지 형태로 저장할 수 있었다. 그러나 원하는 자료형을 찾기란 쉽지않다. 예를들어 리스트에서 원하는 값을 찾기 위해서는 앞에서부터 순서대로 순회해야하며, 힙의 경우에서도 최소값, 최대값을 찾을 수 있을 뿐, 원하는 값을 찾을 수는 없다. 그래서 이번에 배울 자료형인 해시는 색인이 쉽게 만들어 졌다. 해시의 원리 해시는 값과, 이 값을 찾기위한 key를 사용한다. 파이썬의 딕셔너리와 비슷하다고 생각할 수 있는데, 딕셔너리도 해시로 이루어져있다. 가장 먼저 키를 해시함수에 입력한다. 해시함수는 키를 입력받아서 숫자로된 인덱스를 결과로 내는 함수이다. 해시함수의 출력으로 인덱스가 나오면 리스트와 비슷한 자료형 테이블의 인덱스 ..

그래프 트리와 같이 노드와 간선으로 연결된 형태를 그래프라고 한다. 싸이클이 형성될 수 있기 때문에 계층적 자료구조라기 보다는 전체를 나타내는 형태로 생각할 수 있다. 따라서 부모-자식 관계나 루트노드 같은 성질이 없다. 위 그림에서 A-B-E-C-A의 사이클이 있다. 그래프에는 여러가지 특징이 있다. 먼저, 방향이 있는 그래프와 방향이 없는 그래프로 나눌 수 있다. 위에서 그린 그래프는 방향이 없는 그래프이고, 방향이 있는 그래프는 다음과 같다. 방향이 있을 때는 해당 방향으로만 진행할 수 있다는 특징이 있다. 다음으로는 모든 노드가 연결되어있지 않아도 된다는 것이다. 이를 비연결그래프, disjoint 그래프라 한다. 반면 모든 노드가 서로 연결되어있는 그래프는 완전그래프라 한다. 간선에 가중치를 둘..

Heap 최대값, 혹은 최소값을 빠르게 찾기 위한 자료구조이며, 일반적으로 완전이진트리를 활용하여 구현하고, 우선순위 큐에 사용한다. 우선순위 큐란 FIFO구조의 일반적인 큐가 아니라, 각 데이터에 우선순위가 있어서, 우선순위가 높은 데이터가 먼저 POP되는 자료형태이다. 예를 들어 운영체제에서 프로그램들을 스케쥴링 할 때, FIFO방식으로 프로세스를 처리한다면, 처리시간이 긴 프로세스를 처리하는 동안 처리시간이 짧은 프로세스는 대기시간이 길어지게 되고, 이는 비효율적이다. 따라서 처리시간이 짧은 프로세스에 높은 우선순위를 두어 이를 먼저 처리하고, 처리시간이 긴 프로세스를 나중에 처리하려고 할 때 우선순위 큐를 사용할 수 있다. Heap의 구조 힙은 두가지로 나뉜다. 루트노드가 가장 작은 값인 Min ..

이진 탐색 트리 앞으로 글을 쓰겠지만 선형 자료 구조에서는 원하는 값을 탖는 방법이 여러가지가 있다. 가장 먼저 생각할 수 있는 것은 앞 혹은 뒤에서부터 하나씩 살펴보는 선형탐색이다. 그렇다면 트리형 자료구조에서는 원하는 값을 어떻게 찾을 수 있을까? 가장 기초적인 방법이 바로 이진탐색 트리이다. (물론 모두 살펴볼 수도 있을 것이다.) 먼저 그림부터 보자. 루트 노드에 값 K가 담겨있다고 생각하자. 그렇다면 이 루트 노드의 왼쪽에 있는 서브 트리에는 K보다 작은 값이, 오른쪽에는 K보다 큰 값만이 들어있는 트리를 생각할 수 있고, 이 모든 서브트리에도 같은 생각이 적용된다면 원하는 값을 찾기가 쉬울 것이다. 이를 이진 탐색 트리라 한다. 실제 값을 넣어서 확인해보자 위 트리에서 13을 찾고 싶다고 생각..

트리 단순 선형 자료구조에서는 계층을 나타내기가 어렵다. 따라서 계층적 자료구조를 만들기 위해서 트리를 생각했다. 값을 가지는 노드와, 노드 사이를 잇는 간선으로 이루어져 있으며, 부모 - 자식 관계를 가진다. 트리를 그림으로 나타내면 위와 같다. 여기서 A - B, C, D의 관계를 부모 - 자식 관계라 하며, 마찬가지로 B - E, F의 관계도 부모 - 자식 관계이다. 가장 위에 있는 노드인 A를 루트(Root)노드라 하고, 자식이 없는 노드들(E, F, C, G)를 리프(Leaf)노드라 한다. 위의 트리는 3개의 층으로 되어있는데, 이를 높이가 3인 트리라고 한다. 트리는 서브트리로 나눌 수 있다. 이렇게 나누면 B와 D는 각각의 서브트리에서 루트노드가 된다. 트리의 자식이 연결되어 싸이클이 생기면..

LinkedList 대표적으로 C같은 경우 선형 자료구조인 Array가 있다. 그러나 이 배열의 경우는 시작부터 크기를 지정해주어야하고, 새로운 요소를 추가하거나, 배열 안의 요소를 제거할 때 비용(시간)이 많이 든다. 이를 개선하기 위해서 구조체를 만드는데, 이 구조체에는 하나의 요소 값과, 다음 구조체의 정보를 가진다. 이 구조체를 연결하여 만드는 리스트가 바로 LinkedList이다. LinkedList를 사용함으로써 크기가 유동적인 자료형을 만들 수 있고, 삽입, 제거에 시간이 적게 든다. 특히 값을 탐색하다가 데이터를 추가, 제거하기에 용이하다. 단점으로는 index가 없어 값을 앞에서부터 탐색해야 한다. -> 탐색에 시간이 많이 소요된다. 종류로는 단순(Single), 양방향(Double)이 ..