프론트엔드 개발자의 기록 공간

🚩 7576번_토마토 골드5 📖 문제 설명 : N x M 상자 크기에 토마토가 있을 경우, 하루가 지날 때마다 인접 토마토들을 익게 한다. 모든 토마토가 익는 데까지 걸리는 최소 일수 구하기 💡 시간 초과를 벗어나기 위해서는 queue 알고리즘을 구현해서 사용 or index가 증가하는 cursor를 두고, queue.length < queueCursor를 사용 queue 알고리즘을 구현 예시 const fs = require('fs') const [mn, ...input] = fs .readFileSync('/dev/stdin') .toString() .trim() .split('\n') const [m, n] = mn.split(' ').map(Number) const graph = input.map..

백준 BFS 알고리즘 2644번_촌수계산 난이도 : 실버II 문제설명 입출력 문제 풀이 : 주어진 사람의 번호가 서로 몇 촌인지 계산하면 된다. 촌수는 부모가 같으면 형제, 즉 같은 촌수이다. 이를 좀더 생각하면 형제는 촌수를 계산할 필요없고 부모일때만 계산해주면 된다. 즉 최단경로 문제처럼 거리가 같으면 계산을 안하고 거리가 다를때 계산을 해주는 BFS 유형인것을 알 수 있다. BFS를 이용하여 촌수를 계산하면된다. 연결된 노드만 파악하면 되기 때문에 인접그래프 형식으로 풀었다. //실버2 촌수계산 const solution = (p, q) => { //시작 촌수 p삽입 let start = [p]; let cnt = 0; while (start.length !== 0) { cnt += 1; //촌수 ..

백준 그리디 알고리즘 1202번_보석 도둑 난이도 : 골드IV 해결못한 문제 : 시간 초과 or 메모리 초과 문제 설명 입출력 예제 입력2 4 4 1 100 2 200 13 300 10 500 10 10 10 14 => 답 : 1100 문제 풀이 : 최대한 비싼 보석을 챙기는 것이 문제 핵심이다. 그러기 위해서는 제일 비싼 보석을 순차적으로 보석의 무게와 비슷한 가방을 찾아 넣어줘야한다. 만약 1kg짜리 보석을 10kg짜리 가방에 넣으면 비효율적이기 때문에 최대한 비슷한 가방을 찾아서 넣어야한다. 정리하면 다음과 같다. 1. 보석 가격을 기준으로 정렬을 해준다. 2. 가방은 오름차순 정렬을 시행해준다. 3. 가격이 높은 보석을 차례대로 보석 무게와 비슷한 가방을 찾아서 넣어준다(보석 가격 누적계산) *우..

백준 그리디 알고리즘 1715번_카드 정렬하기 난이도 : 골드IV 문제 설명 추가 입출력예시 예제 입력 2 => 5 20 20 20 10 10 예제 출력2 => 180 문제 풀이 : 1. 입력 받은 카드 묶음에서 제일 작은거 두개를 빼낸다. 2. 두개를 덧셈 후 결과값을 누적 카운트 해주고 다시 카트 묶음에 넣어준다. 3.모든 묶음을 위의 과정대로 반복한다. *최소힙 자료구조를 이용한 풀이(통과) //최소힙 자료구조 function MinHeap() { this.heap = [0]; this.insert = (v) => { this.heap.push(v); let p = this.heap.length - 1; while (p > 1 && this.heap[Math.floor(p / 2)] > this.h..

백준 그리디 알고리즘 2847번_게임을 만든 동준이 난이도 : 실버4 문제 설명 추가 입출력 예시 예제 입력2 => 5 9 5 6 2 5 예제 출력 2 => 20 예제 입력3 => 4 10 11 12 7 예제 출력3 => 18 문제 풀이 : 마지막 값이 제일 커야하므로 입력으로 받은 배열을 뒤집어 준다. 그 후 n번까지 앞에값을 기준으로 다음값을 계산해준다. 계산된 차이만큼 연산의 횟수가된다. //실버4 게임을 만든 동준이 const solution = (n, list) => { // 현재 list는 역순 상태 let cnt = 0; //연산 횟수 //1부터 시작 for (let i = 1; i < n; i++) { //이전값보다 현재값이 크거나 같다면 현재값을 감소 시켜야함 if (list[i - 1]..

백준 BFS 알고리즘 7562번_나이트의 이동 난이도 : 실버II 문제 설명 문제 풀이 : 출발위치에서 출발하여 이동할 수 있는 범위를 움직이면서 도착위치까지 최소 횟수를 구하면 된다. 여기서 중요한 포인트는 한 지점에서 갈 수 있는 경로를 전부 탐색한 후, 경로 횟수를 카운트를 어떻게 해줘야하는 것이 관건이다. 여러 방법이 있지만 저는 한 지점에서 갈 수 있는 위치를 스택에 넣고 그 스택의 길이만큼 반복문을 해준 후 반복이 끝났을때 카운트 해줬다. 이렇게 하면 한 단계마다 모든 위치를 탐색 할 수 있게 된다. 그리고 위치를 옮겨가면서 옮겨진 위치가 도착(종료)위치인지 비교하여 맞으면 이동횟수 출력후 종료하고 아니면 방문하지 않은 곳이면 방문처리후 스택에 이동위치를 넣어준다. const BFS = (s_..