CS

힙 Heap 정의 힙은 완전 이진 트리 자료구조 이다. 힙에서는 항상 루트 노드를 제거한다. 종류 최소힙 (min heap) 루트 노드가 가장 작은 값을 가진다. 가장 작은 데이터가 우선적으로 제거된다. 최대힙 (max heap) 루트 노드가 가장 큰 값을 갖는다. 값이 가장 큰 데이터가 우선적으로 제거된다. 완전 이진 트리란? 루트 노드 부터 시작하며 왼쪽 자식 노드, 오른쪽 자식 노드 순서로 데이터가 차례대로 삽입되는 트리를 의미한다. 힙에 새로운 원소가 삽입될 때 새로운 원소가 삽입되었을 때 O(log N)의 시간 복잡도로 힙 성질을 유지할 수 있다. 삽입시에 부모 노드와 크기를 비교하여 자리를 바꾼다. (최소힙은 부모노드 보다 작으면 up, 최대힙은 크면 up) 비교결과가 false 혹은 노드 도..

1. 정의 우선 DFS와 BFS의 정의부터 간략하게 다시 알고 가도록 하자. DFS 깊이 우선 탐색이라는 이름에 맞게 탐색할 노드를 깊이를 우선으로 탐색하는 알고리즘이다. DFS의 구현은 Stack 또는 재귀적인 특징을 이용해 구현한다. BFS 너비 우선 탐색은 넓게 바로 아래 하위 노드를 모두 넓게 탐색한 뒤 그 아래의 노드들을 탐색하는 알고리즘이다. 큐를 이용해 탐색을 관리한다. 2. 구분 방법 그렇다면, 실제 코테나 문제를 해결할 때 무엇을 언제 사용해야하나? 우선 그 문제를 분석해봐야한다. 그래프 탐색에서 모든 정점을 방문하는가? DFS와 BFS 둘 다 가능하다. 경로의 특징을 저장 혹은 조합, 순열을 구해야 하는 문제인가? 고로타면 DFS를 이용하는게 유리하다. 최단 경로, 최단 거리를 구해야 ..

슬라이딩 윈도우(Sliding Window) 알고리즘 고정된 윈도우(특정 범위를 나타내는 말)의 내부 요소값을 이용하여 문제를 풀이하는 알고리즘 위의 사진에서는 윈도우의 범위가 5이다. 첫번째는 1, 3, 2, 6, -1 이 윈도우 내에 있고 두번째에는 3, 2, 6, -1, 4 가 윈도우 내에 존재한다. 첫번째에서 두번째로 넘어갈 때, 맨 앞에 위치한 1은 윈도우 내에서 제거되고, 1을 제외한 3, 2, 6, -1 은 재사용되며 그 뒤로 새로운 요소인 4가 추가가 된다. 슬라이딩 윈도우 알고리즘는 재사용이 중요하다고 생각한다. 고정된 범위를 가지고 움직이는 윈도우 내에 있는 요소들을 움직이는 만큼 앞에 있는 요소를 제거하고 나머지 값은 재사용하며 그 뒤에 새로운 값들을 배정해 사용한다. 시간복잡도 : ..

알고리즘의 해시 해시에는 해시(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