분류 전체보기
[JS] 등산코스 정하기
푸는데 꽤나 애를 먹었던 문제였다. 문제 푸는 방법 자체는 접근을 잘했었다. 1. 문제는 코스를 왔다갔다 하는것이지만 사실 게이트 -> 봉우리까지만 체크를 하면된다. 2. 다익스트라 알고리즘을 활용해서 가중치의 합계가 아닌, 가중치가 가장 적게 나오는 값을 체크해주면 된다. 3. 만약 새 노드로 들어갔는데 내가 들어간 노드의 가중치보다 노드에서 뻗어나가는 가중치가 많다면 뻗어나가는 가중치를 사용해야 한다. 3으로 Node에 들어갔는데 해당 Node에 나가는 길의 가중치가 4,5만 있다면 각 길의 가중치는 4,5가 된다. 4. 각 게이트는 들어갈 수 없는 Node로 설정한다. 5. 산봉오리는 들어가면 나갈 수 없는 Node로 설정한다. 6. 다익스트라 알고리즘이기 때문에 최소 Heap을 활용한 우선순위큐를..
[JS] 카운트 다운
문제 자체는 dp를 활용해서 해결할만한 문제였다. 우선 다트는 1~20까지 점수가 있는 판이란 점을 생각하자. dp를 만드는데 [Infinity,0]으로 각 칸을 dp[n] 이라면 dp[n][0]은 n이라는 점수를 만들기 위해 필요한 다트의 횟수, dp[n][1]은 싱글이나 불을 던진 횟수를 저장하면 될 것이라고 생각했다. 이런방식으로 dp를 구성하면 n이라는 점수를 만들기 위해서 이전 dp에서 2개만 합하면 된다! 또한 n이 점수이므로 dp[n]을 만들기 위해 dp[i]를 사용했다면 자연스럽게 더해줄 점수는 dp[n-i]가 된다. 이렇게 dp들을 검사하며 1. 다트를 던지는 횟수가 적은경우 2. 다트를 던지는 횟수가 같다면 싱글이나 불 다트를 던진 횟수가 많은경우 위 두 조건중 하나에 충족하면 dp를 ..
![[JS] 고고학 최고의 발견](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FcxWybl%2Fbtsy4h7Gd0p%2FbOEDHmpr8BmlTLAIf50goK%2Fimg.png)
[JS] 고고학 최고의 발견
문제만 놓고 보면 완전탐색 문제같아 보인다. 실제로 모든 케이스를 검사한다고 생각한다면... 들어올수 있는칸이 64칸이므로 4 ^ 64 즉 절대로 시간안에 풀 수 없는 경우의 수가 나온다. 문제를 약간 생각해본다면 위 경우의 수를 획기적으로 줄일 수 있다. 만약에 퍼즐의 맨 윗칸이 고정되어 있다고 생각해보자. 01030213 해결할 수 없다면 false 반환 -> 해결할 수 있다면 돌린 횟수를 반환 3. 첫줄을 dfs를 활용해서 4가지 케이스씩 4^n의 케이스를 돌려가면서 확인 4. 나온 값들 중 가장 작은 값을 반환 function solution(clockHands) { const len = clockHands.length const dc = [0,1,0,-1,0] const dr = [0,0,1,0..
[JS] 2차원 동전 뒤집기
동전뒤집기 문제에서 생각할 점은 어느 칸이던 같은 줄을 2번이상 뒤집는건 의미가 없다는 것이다. 즉 , 가로 1~10 세로 1~10 까지 있다고 가정한다면 가로 3번째 라인을 1번뒤집나 3번뒤집나 5번 뒤집나 해당 라인의 결과는 같게 된다. 따라서 모든 라인의 줄을 최대 1번까지만 뒤집을 수 있다고 생각할 수 있다. 그다음으로 생각해야 할점은 순서가 상관이 없다는 것이다. 가로 3번 -> 세로2번 -> 가로 6번 이런식으로 뒤집나 세로 2번 -> 가로 6번 -> 가로3번 이런식으로 뒤집나 결과가 같게 나온다. 즉 위 문제는 2^10으로 나오는 완전탐색을 할 필요가 없다! 10번의 경우만 체크하면 된다. 1. 우선 문제를 조금 간략화 하기 위해서 beginning과 target 배열을 비교해서 같으면 fa..
[JS] 부대복귀
각 그래프의 간선의 길이가 1이므로 처음에는 단순히 bfs로 구하면 되는거 아니야? 라는 생각을 하게 되었다. function solution(n, roads, sources, destination) { const graph = [...Array(n + 1)].map((_) => []); for (const [a, b] of roads) { graph[a].push(b); graph[b].push(a); } const getDist = (start, end) => { const visited = Array(n + 1).fill(false); const que = [[start, 0]]; let idx = 0; while (que[idx]) { const [node, dist] = que[idx++]; v..