CS/Data Structure & Algorithm (14) 썸네일형 리스트형 JS 트리 & 우선순위 큐 트리: 가계도와 같이 계층적인 구조를 표현할 때 사용할 수 있는 자료구조 루트 노드: 부모가 없는 최상위 노드 단말 노드: 자식이 없는 노드 트리는 부모와 자식 관계가 성립한다. 깊이: 루트 노드에서의 길이 (*길이: 출발 노드에서 목적지 노드까지 거쳐야 하는 간선의 수) 트리의 높이: 루트 노드에서 가장 깊은 노드까지의 길이 이진 트리 : 최대 2개의 자식을 가질 수 있는 트리 우선순위 큐: 우선 순위에 따라서 데이터를 추출하는 자료구조 컴퓨터 운영체제, 온라인 게임 매칭 등에서 활용 일반적으로 힙을 이용하여 구현 자료구조 추출되는 데이터 스택 가장 나중에 삽입된 데이터 큐 가장 먼저 삽입된 데이터 우선순위 큐 가장 우선순위가 높은 데이터 우선순위 큐 구현 방법 우선순위 큐 구현 방식 삽입 시간 삭제 .. JS 백트래킹 일반적으로 그래프/트리의 모든 원소를 완전 탐색하기 위한 목적으로 사용할 수 있다. *DFS와의 차이점 1) DFS는 일반적으로 완전 탐색 목적으로, 재귀 함수를 이용해 구현한다. 2) 백트래킹도 재귀 함수를 이용해 구현하는 것이 일반적이지만, 단순히 완전 탐색이 아니라 조건에 따라 유망한 노드로 이동한다. 백트래킹은 기본적으로 가능한 노드에 대하여 계속해서 재귀적으로 함수를 호출한다. 백트래킹은 모든 경우의 수를 탐색하기에 적합하다. JS 이진탐색 순차 탐색: 리스트 안에 있는 특정 데이터를 찾기 위해 앞에서부터 하나씩 확인 시간 복잡도: O(N) 이진 탐색: 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색 시간 복잡도: O(logN) 이진 탐색을 수행할 때는 시작점(Left)와 끝점(Right)을 기준으로 탐색 범위를 명시한다. -> Mid는 자동 생성 활용 상황: 1. 매우 넓은(억 단위 이상) 탐색 범위에서 최적의 해를 찾아야 하는 경우 2. 데이터를 정렬한 뒤에 다수의 쿼리를 날려야 하는 경우 코드 구현 *재귀 function binarySearch(arr, target, start, end){ if (start>end) return -1; //데이터가 존재하지 않는다 let mid = parseInt((start+end.. JS DFS/BFS 알고리즘 탐색이란 많은 양의 데이터 중 원하는 데이터를 찾는 과정. 대표적인 그래프 탐색 알고리즘->DFS/BFS DFS 2차원 배열로 그래프를 표현 인접 리스트로 표현 스택 자료구조 활용 그래프 혹은 트리에서 모든 노드를 한 번씩 탐색하기 위한 기본적인 방법(완전 탐색) 동작 방식: 1. 시작 노드를 스택에 넣고 방문처리 2. 스택에 마지막으로 들어온 노드에 방문하지 않은 인접 노드가 있는지 확인 2-1 방문x 인접 노드 있다면, 방문하지 않은 인접 노드를 스택에 삽입하고 방문처리 2-2 방문x 인접 노드 없다면, 현재 노드를 스택에서 추출 3. 2번 과정을 반복할 수 없을 때까지 반복 구현 특징: 1. 스택 혹은 재귀 함수를 이용한다. -> 재귀 함수는 내붖적으로 스택과 동일한 동작 원리를 가지므로, 구현의 .. JS 정렬 알고리즘 - 선택 정렬 : 매 단계 중 처리되지 않은 가장 적은 원소를 선택해서 앞으로 보내는 정렬 방법 매 단계에서 가장 작은 것을 선택하는 데에 약 N번의 연산이 필요. 이러한 연산을 N번 하므로 시간 복잡도는 N*N 시간복잡도 : O(N^2) 동작 방식: 1. 각 단계에서 가장 작은 원소 선택 2. 현재까지 처리되지 않은 원소들 중 가장 앞의 원소와 위치를 교체 function selectionSort(arr){ for (let i=0 ; iarr.length ; j++){ if (arr[minIndex] > arr[j]){ minIndex = j; } } // swap let temp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = temp; } } - 버블 정렬 .. JS 자료구조 JS에서 스택을 구현하는 방법- 배열 자료형 push() 메서드: 마지막 위치에 원소 삽입. 시간 복잡도 O(1) pop() 메서드: 마지막 위치에서 원소 추출, 시간 복잡도 O(1) 연결리스트로 스택 구현하기 -스택을 연결 리스트로 구현하면, 삽입과 삭제에 있어서 O(1) 보장. -head를 가리키는 하나의 포인터만 가진다. *head: 남아있는 원소 중 가장 마지막에 들어 온 데이터를 가리키는 포인터 연결리스트로 큐 구현하기 -큐를 연결 리스트로 구현하면, 삽입과 삭제에 있어서 O(1) 보장. - head와 tail 두 개의 포인터를 가진다. JS에서는 Dictionary 자료형을 이용하여 큐를 구현하면 간단. - 트리용어 정리 루트노드(root node): 부모가 없는 최상위 노드 단말노드(leaf.. 이전 1 2 다음