문제https://www.acmicpc.net/problem/1926 풀이이 문제는 BFS 알고리즘을 이용해 그래프 탐색을 진행해야 한다. 그림은 연결되어 있기 때문에 연결된 노드를 탐색하며 방문했음을 기록해야합니다. 코드const input = require('fs') .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt') .toString().trim().split('\n').map(e => e.split(' ').map(Number));const [y, x] = input.shift();const map = input;const check = Array.from({ length: y }, () ..
분류 전체보기
크루스칼 알고리즘크루스칼 알고리즘은 그래프 내의 모든 정점들을 가장 적은 비용으로 모두 연결하기 위해 사용하는 알고리즘이다. 또 다른 말로는 최소 신장 트리를 구하는 알고리즘이다.신장 트리란?그래프 내의 모든 정점을 포함하는 트리로써, 최소의 간선으로 모든 정점이 연결되어 있는 순환성이 없는 부분 그래프이다. 알고리즘 원리그래프에서 간선을 하나씩 추가하며 최소 신장 트리를 만드는 알고리즘이며, 간선을 추가할 때는 그리디 알고리즘을 이용해 비용이 최소인 간선을 선택한다. 연결된 정점들의 부모를 기록하며 최소 간선을 선택하며 동작한다. 동작 과정간선의 비용을 기준으로 오름차순 정렬을 해준다.낮은 비용의 간선순으로 순회하며 최소 신장 트리를 만든다.이때 주의할 점은 트리에 순환성이 생기지 않도록 간선을 생성하..
문제https://school.programmers.co.kr/learn/courses/30/lessons/42861# 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 해당 문제는 크루스칼 알고리즘을 이용해 최단 신장 트리를 구하며 풀이하는 문제이다.크루스칼 알고리즘을 이 문제를 통해 처음 알게되었는데, BFS 그래프 탐색인데 cost를 오름차순으로 정렬해 부모를 비교해 처리하는 알고리즘이라 생각한다. 코드const find = (parent, x) => { if (parent[x] === x) { return x; } return parent[x]..
디스트럭처링 할당(구조 분해 할당)은 구조화된 배열과 같은 이터러블 또는 객체를 1개 이상의 변수에 개별적으로 할당하는 것을 말한다. 배열 디스트럭처링 할당// ES5var arr = [1, 2, 3];var one = arr[0];var two = arr[1];var three = arr[2];console.log(one, two, three); // 1 2 3 구조 분해 할당의 대상은 이터러블이어야 하며, 할당 기준은 배열의 인덱스다.const arr = [1, 2, 3];// ES6 배열 디스트럭처링 할당// 변수 one, two, three를 선언하고 배열 arr을 디스트럭처링하여 할당한다.// 이때 할당 기준은 배열의 인덱스다.const [one, two, three] = arr;cons..
문제https://school.programmers.co.kr/learn/courses/30/lessons/ 풀이해당 문제는 BFS를 이용한 다익스트라다 문제이며, 처음 문제를 풀때는 주어지는 sources별로 마지막 도착지인 destination까지의 거리를 측정했었다. 하지만 이렇게 풀게 되면 시간 초과가 발생한다.function solution(n, roads, sources, destination) { const answer = []; const road = Array.from({length: n + 1}, () => []); const level = Array.from({length: n + 1}, () => Infinity); for(let i = 0; i fal..
Tree의 개념트리는 노드들의 구조가 계층적 구조를 갖는 비선형 자료구조이며, 노드와 노드를 연결하는 간선으로 구성된다. 트리 자료구조는 나무(Tree)를 거꾸로 매단 모양과 유사하다. 트리는 하나의 루트 노드를 갖으며 루트 노드는 0개 이상의 자식 노드를 갖는다. 그 자식 노드 또한 0개 이상의 자식 노드를 갖으며 이는 반복적으로 정의된다. 트리 구조의 기본 용어노드(Node)트리를 구성하는 기본 요소이며, 노드에는 키 또는 값과 하위 노드에 대한 포인터를 갖고있다. 간선(Edge)노드와 노드 간의 연결선 루트 노드(Root Node)트리 구조에서 부모가 없는 최상위 노드 부모 노드(Parent Node)자식 노드를 갖는 노드 자식 노드(Child Node)부모 노드의 하위 노드 형제 노드(Sibl..
