알고리즘

백트래킹 모든 경우의 수를 탐색하는 알고리즘 DFS나 BFS를 이용할 수 있다 가지치기(Pruning) : 효율을 위해 탐색하지 않아도 되는 곳을 미리 막는 것 자바스크립트는 재귀 효율이 나쁘게 때문에 DFS를 구현할 경우 스택을 이용하는 것이 좋다 탐색에서 순환(Cycle)이 발생할 수 있다면 BFS를 이용하는 것이 편하다 핵심은 가지치기 !!! 백트래킹 로직을 어떻게 작성할 것인가? 우선 모든 경우의 수를 찾을 수 있도록 코딩 이후 문제에서 특정한 조건을 만족하는 것만 탐색하고 나머지는 탐색하지 않도록 조건문을 작성 즉, 절대로 답이 될 수 없는 문제는 탐색을 종료한다 동적계획법 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식 그리디(Greedy)나 백트래킹처럼 특정 알고리즘이 아닌 문제 해결..

너비 우선 탐색 (BFS) 그래프 탐색 알고리즘으로 같은 깊이에 해당하는 정점부터 탐색하는 알고리즘 BFS의 특징 Queue를 이용하여 구현할 수 있다 시작 지점부터 가까운 정점부터 탐색 V가 정점의 수, E가 간선의 수일 때 BFS의 시간복잡도는 O(V + E)다 깊이 우선 탐색(DFS) 그래프 탐색 알고리즘으로 최대한 깊은 정점부터 탐색하는 알고리즘 DFS의 특징 Stack을 이용하여 구현할 수 있다 시작 정점에서 깊은 것부터 찾는다 V가 정점의 수, E가 간선의 수일 때, DFS의 시간복잡도는 O(V + E)다 그리디 (Greedy) 매 선택에서 지금 이 순간 가장 최적인 답을 선택하는 알고리즘 최적해를 보장해주지 않는다 그리디 알고리즘의 특징 보통 최적해를 구하는 알고리즘보다 빠른 경우가 많다 크..

트리 (Tree) 방향 그래프의 일종으로 하나의 루트에서 하위로 뻗어나가는 구조를 가지고 있다 루트(Root) : 가장 상위에 존재하는 정점 노드(Node) : 각 정점 리프 노드(Leaf Node) : 자식이 없는 노드 레벨(Level) : 루트로부터 몇 번의 깊이 차수(Degree) : 한 정점에서 뻗어나가는 정점의 수 인접 행렬, 인접 리스트로 구현 가능 ex) 부서, 디렉토리 구조 트리의 특징 루트 정점을 제외한 모든 정점은 반드시 하나의 부모 정점을 가진다 정점이 N개인 트리는 반드시 N-1개의 간선을 가진다 루트에서 특정 정점으로 가는 경로는 유일하다 이진 트리 각 정점이 최대 2개의 자식을 가지는 트리를 의미한다 이진 트리의 특징 정점이 N개인 이진 트리는 최악의 경우 높이가 N이 될 수 있..

큐 (Queue) First In First Out(FIFO)라는 개념을 가진 선형 자료구조 Linear Queue(선형 큐) 와 Circular Queue(환형 큐)가 존재 큐의 가장 앞에 있는 원소의 인덱스(위치)는 front로 나타내며, 가장 뒤에 있는 원소의 인덱스(위치)는 rear라고 한다 Linear Queue (선형 큐) Array(배열)로 구현 class Queue { constructor() { this.queue = []; this.front = 0; this.rear = 0; } enqueue(value) { this.queue[this.rear++] = value; } dequeue() { const value = this.queue[this.front]; delete this.qu..