크루스칼 알고리즘크루스칼 알고리즘은 그래프 내의 모든 정점들을 가장 적은 비용으로 모두 연결하기 위해 사용하는 알고리즘이다. 또 다른 말로는 최소 신장 트리를 구하는 알고리즘이다.신장 트리란?그래프 내의 모든 정점을 포함하는 트리로써, 최소의 간선으로 모든 정점이 연결되어 있는 순환성이 없는 부분 그래프이다. 알고리즘 원리그래프에서 간선을 하나씩 추가하며 최소 신장 트리를 만드는 알고리즘이며, 간선을 추가할 때는 그리디 알고리즘을 이용해 비용이 최소인 간선을 선택한다. 연결된 정점들의 부모를 기록하며 최소 간선을 선택하며 동작한다. 동작 과정간선의 비용을 기준으로 오름차순 정렬을 해준다.낮은 비용의 간선순으로 순회하며 최소 신장 트리를 만든다.이때 주의할 점은 트리에 순환성이 생기지 않도록 간선을 생성하..
cs
힙 Heap 정의 힙은 완전 이진 트리 자료구조 이다. 힙에서는 항상 루트 노드를 제거한다. 종류 최소힙 (min heap) 루트 노드가 가장 작은 값을 가진다. 가장 작은 데이터가 우선적으로 제거된다. 최대힙 (max heap) 루트 노드가 가장 큰 값을 갖는다. 값이 가장 큰 데이터가 우선적으로 제거된다. 완전 이진 트리란? 루트 노드 부터 시작하며 왼쪽 자식 노드, 오른쪽 자식 노드 순서로 데이터가 차례대로 삽입되는 트리를 의미한다. 힙에 새로운 원소가 삽입될 때 새로운 원소가 삽입되었을 때 O(log N)의 시간 복잡도로 힙 성질을 유지할 수 있다. 삽입시에 부모 노드와 크기를 비교하여 자리를 바꾼다. (최소힙은 부모노드 보다 작으면 up, 최대힙은 크면 up) 비교결과가 false 혹은 노드 도..
알고리즘의 해시 해시에는 해시(Hash), 해시 함수(Hash Function), 해싱(Hashing), 해시 테이블(Hash Table) 이렇게 4가지로 나뉘어 진다. 각 요소들에 대해 알아보자. 해시(Hash) 해시는 검색과 저장을 빠르게 하는 자료구조이다. 데이터를 저장할 때는 Key-Value 형태로 데이터가 저장되고,Key값이 배열의 인덱스로 저장되기 때문에 검색과 저장이 빠르게 일어난다. 해시 함수(Hash Function)와 해싱(Hashing) 해시 함수는 Key값을 고정된 길이의 Hash로 변환하는 기능을 한다. 해시 함수에서 Key값을 hash로 변환하는 과정을 해싱(hashing)이라 한다. 해싱 과정을 통해 해시 값(hash value)또는 해시 코드(hash code)로 변경하며,..
이분 탐색 알고리즘(Binary Search Algorithm) 정의 이미 정렬된 배열에서 탐색 범위를 두 부분 리스트로 나눠 절반씩 좁혀가며 필요한 부분에서만 탐색하도록 제한하여 원하는 값을 찾는 알고리즘이다. 동작 이진 탐색은 정렬된 배열이 필요하며, Left, Right, Mid의 변수가 필요하게 된다. Left는 왼쪽 끝 인덱스, Right는 오른쪽 끝 인덱스, Mid는 (Left + Right)/2 로 구할 수 있다. const binarySearch = (arr, targetValue) => { let left = 0; let right = arr.length - 1; while (left targetValue) { right = mid - 1; } else if (arr[mid] < targ..
동적 계획법의 배경 피보나치 수열 동적 계획법의 등장 배경에는 피보나치 수열이 있다. 피보나치 수열은 제2항까지는 1, 3항부터는 앞의 두 항을 더한 수로 저의 된다. 제 0항은 생략되기도 한다. (0), 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89... 프로그래밍에서 피보나치 수열은 보통 재귀를 통해 표현이 가능하다. 피보나치 수열을 함수로 구현해 보자. const fibo = (n) => { if (n { if (n { if (n { fiboData[0] = 0; fiboData[1] = 1; for (let i = 2; i
큐 (Queue) 선입선출 FIFO(First In First Out)의 자료구조이다. 데이터가 들어오는 위치는 가장 뒤에 있고, 나가는 위치는 가장 앞에 있어서, 선입선출의 구조를 갖게된다. 즉, 먼저 들어온 데이터가 먼저 제거된다. 큐의 동작 1️⃣ Enqueue : 큐에 데이터를 추가한다. 큐가 꽉 차있을 때 Overfolw condition이 된다. 2️⃣ Dequeue : 큐에서 데이터를 제거한다. 데이터는 들어온 순서대로 빠져나온다. 큐가 비어져 있을 때는 Underflow condition이 된다. 3️⃣ Front : 큐의 앞부분의 데이터를 가진다. 4️⃣ Rear : 큐의 뒷부분의 데이터를 가진다. 큐의 종류 큐를 구현하기에 front(머리)와 rear(꼬리) 두가지 지표를 추적해야 한다..
