본문 바로가기

🧠 알고리즘/유형별 대표문제5

[다익스트라][백준] 117799 최소비용 구하기2 JS 문제링크 한 노드에서 다른 노드까지의 최소 비용을 구하는 것이기 때문에 다익스트라! 다익스트라 : 한 정점에서 다른 모든 정점까지의 최소 비용을 구하는 알고리즘 다익스트라는 우선순위큐를 사용하는데 JS에는 우선순위큐 라이브러리가 없기 때문에 직접 구현 접근 방법 1. 버스 정보 인접리스트, 각 노드까지의 최소 비용을 저장할 배열(minArr), 이전에 방문한 노드를 저장할 배열(pre)을 만든다. 2. 우선순위 큐에 시작 노드를 넣어준다 3. 큐가 빌 때까지 노드를 꺼내서 minArr와 pre배열을 업데이트 한다 3번에서 배열들을 업데이트 할 때 1. minArr에 있는 값이 우선순위 큐에서 꺼낸 값보다 작을 경우, 꺼낸 값은 최소 비용이 아님으로 continue; 2. minArr에 있는 값보다 우선순.. 2024. 1. 10.

[위상정렬][백준] 2252 JS 풀이 위상정렬 : 방향 그래프에서 노드들간 선행 순서를 위배하지 않고 정렬하는 알고리즘 구현법 1. 맨 처음 모든 간선을 읽으며 indegree 테이블을 채운다 2. indegree가 0인 정점들을 모두 큐에 넣는다 3. 큐에서 정점을 꺼내어 위상 정렬 결과에 추가한다 4. 해당 정점으로부터 연결된 모든 정점의 indegree 값을 1 감소시킨다. 이 때 indegree가 0이 되었다면 그 정점을 큐에 추가한다 5. 큐가 빌 때까지 3,4번 과정을 반복한다 좀 더 자세한 설명이 필요하다면 출처: 바킹독 블로그 https://blog.encrypted.gg/1020 위상 정렬 문제에 적용하기 문제 N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 .. 2023. 12. 28.

[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.

[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.

이전 1 다음

티스토리툴바