Algorithm/이론
-
그래프의 탐색 - BFS, DFSAlgorithm/이론 2023. 1. 11. 17:03
1. 너비 우선 탐색(BFS) 1) 개념 너비 우선 탐색(BFS, Breadth-First Search)란 루트 노드 부터 시작해 인접한 노드를 우선적으로 탐색하는 방법이다. 이름 그대로 넓게 탐색하는 방법이며, 두 노드 사이의 최단 경로를 구하는 문제를 해결하는데 효과적이다. BFS의 구현과 이해는 Queue와 그래프에 대한 이해를 바탕으로 한다. 이에 대한 내용은 아래 글을 참고하면 된다. [ 선형 자료구조 ] 스택(Stack) & 큐(Queue) 1. Stack 1) 개념 스택은 LIFO(last-in-first-out), 즉, 후입선출 원칙을 따르는 선형 자료구조이다. 따라서 데이터의 출입은 한 방향에서만 이루어지고, 이름에 걸맞게 쌓아가는 구조를 가진다. 데이터에 ojhallae.tistory...
-
소수의 개수 파악 - 에라토스테네스의 체Algorithm/이론 2023. 1. 1. 19:27
에라토스테네스의 체는 특정 수가 주어졌을 때 2부터 특정 수까지의 범위 중 소수의 개수를 파악하는 방법이다. 알고리즘의 순서는 아래와 같다. 2 부터 구하고자 하는 구간의 모든 수를 나열한다. 첫번째 수인 2 자기 자신을 제외하고 자신의 배수를 모두 지운다. 남은 수들 중 다음수에 대하여 단계 2를 반복한다. 이를 자바스크립트 코드로 구현하면 아래와 같다. function solution(n) { // 1. 2부터 n까지의 모든수를 배열에 저장 let arr = new Array(n - 1).fill(2).map((ele, idx) => ele += idx); for (let i = 0; i < arr.length; i++) { // 2. 모든 수에 대해 순회 // 3. 인덱스의 수가 0일 경우(지워진 ..