본문 바로가기

🧠 알고리즘31

[MST][백준] 1197 최소 스패닝 트리 JS 풀이 💡 접근법 1. 모든 간선들을 비용순으로 오름차순으로 정렬 2. 비용이 작은 간선부터 선택해서 노드들을 같은 그래프로 합쳐줌. 만약 두 노드가 같은 그래프에 포함되어 있다면 넘어감. 3. 트리의 간선의 개수가 정점의 개수-1이면 반복문 break const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt'; // 입력값이 첫 번째 줄에는 입력 값의 길이(n), n개의 줄에 걸쳐서 한 줄에 하나의 입력값이 주어질 때 const [n, ...input] = require('fs') .readFileSync(filePath) .toString() .trim() .split('\n'); function solution(V, E, Lis.. 2023. 12. 28.

MST 크루스칼 알고리즘 설명 크루스칼 알고리즘은 최소 신장 트리를 찾기 위한 알고리즘입니다. 신장 트리란? : 무방향 그래프의 부분 그래프 중 모든 정점을 포함하는 트리 최소 신장 트리란? : 간선의 합이 최소인 신장 트리 Union & Find 알고리즘 : 두 정점이 같은 그래프에 속하는지 판별하는 알고리즘 https://blog.naver.com/ndb796/221230967614 크루스칼 알고리즘 1. 간선의 크기대로 오름차순 정렬하고 제일 낮은 비용의 간선을 선택 2. 현재 선택한 간선이 정점 u,v를 연결하는 간선이라고 할 때 1. 만약 u와 v가 같은 그룹이라면 아무 것도 하지 않고 넘어간다 2.만약 u와 v가 다른 그룹이라면 같은 그룹으로 만들고 현재 선택한 간선을 최소 신장 트리에 추가한다(union&find 알고리즘.. 2023. 12. 28.

[백준] 7569 토마토 js 풀이 💡 접근법 며칠이 지나면 토마토들이 모두 익는지, 그 최소 일수를 구하는 프로그램을 작성하라 최소 일수를 구해야 하고, 익은 토마토 인접 토마토부터 순차적으로 익으니까 => BFS 1. 익은 토마토를 모두 큐에 넣어준다 2. 익은 토마토와 인접하고 아직 익지 않은 토마토는 큐에 넣어준다 2-1. 박스 위아래 확인 2-2. 같은 박스에서 상하좌우 확인 3. 큐가 빌 때까지 반복 class Node { constructor(val) { this.val = val; this.next = null; } } class Queue { constructor() { this.start = null; this.end = null; this.size = 0; } enqueue(val) { const newNode = ne.. 2023. 12. 28.

[백준] 4179 불! js 풀이 💡 접근방식 - 가장 빨리 탈출 할 수 있는 시간 - 불은 인접 영역으로 이동 -> BFS!! 1. 불이 번지는 시간을 먼저 bfs로 구하고 2. 지훈이가 이동하는 시간이 불이 번지는 시간보다 짦으면 이동 가능 class Node { constructor(value) { this.value = value; this.next = null; } } class Queue { constructor() { this.first = null; this.last = null; this.size = 0; } enqueue(val) { const newNode = new Node(val); if (!this.first) { this.first = newNode; this.last = newNode; } else { thi.. 2023. 12. 27.

[BFS][백준] 7576 토마토 js 풀이 우선 시간초과로 찾아오신 분!!! queue를 직접 구현하지 않고 배열 메소드 shift 쓰시면 시간 초과납니다 ㅠㅠ 💡접근방법 - 최소 일수를 구하는 것 - 인접 토마토들이 먼저 익는 것 -> BFS다!! 1. 창고 안에 익어 있는 토마토들을 찾아서 큐에 넣고 2. 익어 있는 토마토의 인접 토마토들이 익도록 BFS로 탐색 class Node { constructor(value) { this.value = value; this.next = null; } } class Queue { constructor() { this.first = null; this.last = null; this.size = 0; } enqueue(val) { var newNode = new Node(val); if (!this.fi.. 2023. 12. 27.

백준 JS 입력값 템플릿(VSCode 스니펫으로 쉽게 사용하기) 백준을 사용하다보면 입력값을 받는 게 너무 귀찮았는데 vscode에서 스니펫을 만들어서 사용하니까 너무 편하더라구요 짜잔 bjt만 입력하면 자동으로 입력값 템플릿이 완성됩니다! 방법 1. 하단 톱니바퀴를 누르면 user snippets란 메뉴가 나옵니다 2. 클릭해주시면 원하는 언어를 선택하실 수 있습니다. 저 같은 경우는 js를 선택했어요 3. json 형식으로 스니펫을 넣고 저장해줍니다 4. 이제 bjt만 입력하면 자동완성됩니다! 코드는 주석처리되어 있으니 필요한 걸로 사용하시면 됩니다 json에 들어갈 값 "Baekjoon JS Template": { "prefix": "bjt", "body": [ "const filePath = process.platform === 'linux' ? '/dev/s.. 2023. 12. 27.

이전 1 2 3 4 5 6 다음

티스토리툴바