본문 바로가기

알고리즘/풀이 힌트39

[알고리즘] 최단 경로 알고리즘 - JavaScript 최단 경로 알고리즘? 그래프에서 특정 정점에서 목적지까지 최단 경로를 구하는 알고리즘이다. 대표적인 최단 경로 알고리즘은 다음과 같다. DFS 다익스트라 벨만-포드 플로이드 와샬 목적에 따라 알고리즘을 선택할 수 있다. BFS, DFS 그래프의 간선 가중치가 모두 같을 때 적합하다. 2차원 배열로 구성된 지도에서 최단 거리를 찾아야 한다면 BFS, DFS로 푸는 경우가 많다. 다익스트라 알고리즘 그래프의 간선 가중치가 각각 다른 경우 적합하다. 우선 큐를 이용해서 만들 수 있으며, 시간 복잡도는 V가 정점의 수, E가 간선의 수라면 O(E log V) 이다. 작동 방법 1. 시작점을 제외한 모든 정점의 거리를 무한으로 설정한다. 시작은 0 2. 시작점을 선택한다. 3. 선택한 정점에서 갈 수 있는 정점의.. 2022. 9. 21.
[알고리즘] 그리디 - JavaScript 그리디? 매 선택에서 지금 순간 가장 최적인 답을 선택하는 알고리즘이다. A에서 F로 이동할 때 전체 코스트로만 본다면 D로 가는 것이 더 빠르다. 하지만 그리디를 적용한다면 A 의 시점으로만 봤을 때는 B로 가는 것이 더 빠르기 때문에 B로 이동하게 된다. 이처럼 현재 시점의 최적의 답은 선택하지만 이것이 최적의 결과를 보장하지는 않는다. 그리디의 특징 보통 최적의 결과를 구하는 알고리즘보다 빠른 경우가 많다. 크루스칼, 다익스트라 알고리즘 등에 사용된다. 직관적인 문제를 풀 때 적합하다. 사용되는 방식 동전 반환 문제로, 큰 단위인 지폐, 동전 순으로 거스름돈을 만들 때 사용한다. 1860원을 먼저 가장 큰 단위인 1000원짜리 지폐로, 그 후 500원, 100원, 50원, 10원 순으로 구하면 빠르.. 2022. 9. 19.
[알고리즘] 배열끼리 비교해서 배열의 포함 관계 확인하기 0. 들어가며 프로그래머스 후보키를 풀다가 배열이 다른 배열에 포함되는지 확인해야하는 상황이 발생했다. 생각보다 자주 사용되서 정리를 해보았다. 1. 사용 방식 [ 1, 2, 10, 30, 40 ]이란 배열이 있을 때, [ 2, 10, 30 ] 이란 배열이 포함되는지 확인할 때 사용한다. 2. 코드 구현 const answer = [ 1, 2, 10, 30, 40 ]; const key = [ 2, 10, 30 ]; let check = true; const set = new Set([...key, ...answer]); if (set.size === answer.length) { check = false; } key와 answer을 포함하는 set을 사용해서 구현하였다. set은 내부에 속성이 중복이 .. 2022. 9. 12.
[알고리즘] 최소 신장 트리 ( Kruskal ) - JavaScript 최소 신장 트리? 신장 트리란 그래프 내에 모든 정점을 포함하는 최소 연결 그래프이다. 최소 신장 트리가 되려면 아래 조건을 만족해야한다. - 최소한의 간선으로 모든 정점이 연결되어야 한다. - 모든 신장 트리 중 가중치의 값이 최소여야 한다. - Cycle이 발생해서는 안된다. 최소 신장 트리를 구현하기 위한 대표적인 알고리즘이 크루스칼 알고리즘이다. 크루스칼 알고리즘? 그리디 개념을 이용해서 구현할 수 있다. 모든 그래프를 부분 집합으로 분리하고 가중치가 낮은 간선을 선택해 연결한다. 이때 Cycle이 발생하지 않도록 주의한다. => Cycle을 판단하기 위해서 Union-Find 알고리즘을 이용한다. Union-Find 알고리즘? 공통 원소가 없는 두 집합을 구하기 위한 알고리즘이다. 서로 다른 두.. 2022. 8. 29.
[알고리즘] 재귀 함수를 이용한 순열, 조합 순열? 모든 경우의 수를 계산하는 알고리즘이다. ( 순서 고려 O ) [ 1, 3, 5 ] 가 주어졌다면 1 3 5 1 5 3 3 1 5 3 5 1 5 1 3 5 3 1 처럼 모든 경우의 수를 구하는 방법이다. function permutations(arr, n) { if (n === 1) return arr.map((v) => [v]); let result = []; arr.forEach((fixed, idx, arr) => { const rest = arr.filter((_, index) => index !== idx); const perms = permutations(rest, n - 1); const combine = perms.map((v) => [fixed, ...v]); result.push.. 2022. 8. 27.
[알고리즘] 재귀 함수를 이용한 트리 순회 알고리즘 재귀 함수를 이용하는 트리 순회는 전위 순회, 중위 순회, 후위 순회가 있다. 전위 순회 루트 노드를 방문하고, 왼쪽 서브 트리를 전위 순회한 뒤 오른쪽 서브 트리를 전위 순회하는 방식이다. 1 / \ / \ 2 3 / \ / \ 4 5 6 7 트리가 있다면 1. 루트 노드 [ 1 ] 을 방문한다. 2. [ 2 ]를 방문한다. 3. [ 2 ]의 왼쪽 서브 트리로 이동한다. 4. [ 4 ]를 방문한다. 5. [ 4 ]의 왼쪽, 오른쪽 서브 트리가 없으므로 올라간다. 6. [ 2 ]의 오른쪽 서브 트리로 이동한다. ... 방식으로 [ 1, 2, 4, 5, 3, 6, 7 ] 순서대로 순회한다. preorder(tree) { 방문(tree.root); preorder(tree.left); preorder(tre.. 2022. 8. 26.
[알고리즘] 재귀함수 - JavaScript 재귀함수? 자기 자신을 호출하는 함수이다. 이때 호출은 Call Stack에 쌓여서 스택 자료구조와 유사하게 동작한다. 함수형 프로그래밍에선 루프 구현을 재귀로 하는 경우가 많다. 자바스크립트에서의 재귀함수 콜 스택에 제한이 있다. 자바스크립트 엔진마다 다르지만 크롬의 경우 약 1만개이다. 성능이 그렇게 좋지는 않다. 재귀함수를 사용하는 경우 피보나치 수열 앞 두 항의 합이 뒤 항의 값이 되는 수열 function fibonacci(x) { if(x 2022. 8. 25.
[알고리즘] 소수 구하기 - JavaScript 소수 ? 1 또는 자기 자신만을 약수로 가지는 수를 의미한다. 소수를 구하는 방법 2부터 N - 1까지 루프를 돌며 나눠보기 소수를 구할 때 가장 먼저 생각할 수 있는 방법으로 O(n) 시간 복잡도를 가진다. function is_prime(num) { for (let i = 2; i < num; i += 1) { if(num % i === 0) { return false; } } return true } 다른 소수 구하는 방법에 비해 느린편에 속한다. 제곱근으로 확인하기 어떤 소수라도 N의 제곱근보다 큰 수로 나눠지지 않는다는 공식을 이용한다. 시간 복잡도는 O(sqrt(n)) 으로 훨씬 빠른 방법이다. function is_prime(num) { for (let i = 2; i * i < num; i.. 2022. 8. 23.
[알고리즘] 이진 탐색 - JavaScript 이진 탐색? 정렬 되어 있는 요소들을 반씩 제외하면서 찾는 알고리즘 O(log n)만큼의 시간 복잡도가 걸린다. 이진 탐색의 특징 반드시 정렬이 되어 있어야 사용이 가능하다. 배열 혹은 이진 트리를 사용하여 구현할 수 있다. O(log n) 시간 복잡도로 상당히 빠르다. JavaScript에서 사용하기 const arr = [1, 1, 2, 5, 10, 100, 300, 5000, 120000]; function binarySearch(array, findValue) { let left = 0; let right = array.length -1; let mid = Math.floor((left + right) / 2); while (left 2022. 8. 17.
반응형

티스토리툴바