FrontEnd
![[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..
![[JS,Python] 등대](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FzTl5L%2FbtsyR9QBGTe%2FoKuP5SS9gkhtXjwfgK7EAK%2Fimg.png)
[JS,Python] 등대
시간이 매우매우매우매우 걸렸던 문제였다. (내잘못인가 아닌가..) 먼저 필자가 문제에 접근한 방식은 아래와 같다. 1. 그래프가 최소신장트리 이므로 한점을 부모 노드로 잡고 아래로 내려가는 구조로 바꾸는 것이 가능하다. 2. 이때 자식 노드 중에 더이상 자식이 없는 뿌리노드가 포함되어 있다면 해당 부모 노드는 무조건 불이 켜져있어야 한다. 3. 자식노드 중에 뿌리가 없는 노드가 있다면 해당 노드에 불이 켜져있는 경우와 꺼져있는 경우를 비교해줘야 한다. - 이 경우 dfs탐색을 통해서 하다보면 검사한 노드를 또 검사하는 일이 계속 생기게 된다. 4. 따라서 2차원 dp[n][2] 만큼을 생성해서 노드 n이 켜져있는지 꺼져있는데 2가지 경우를 담아서 계산을 한다. - 예를 들어서 3번 노드에 불이 켜져있는지..
[JS] 숫자 타자 대회
예전에 이와 비슷한 문제를 봤던거 같은데 이번에는 조금 다르게 푼 것 같다. 문제를 보면 결국 왼손,오른손을 한번씩 움직이면서 모든 경우의 수를 구하는 방법이 있다. 해당 경우 케이스가 100,000 이므로 2^100,000개가 나와서 무조건 통과할 수 없을 것이라고 생각했다. 따라서 dp를 활용해서 중복되는 값을 지우면 된다고 생각했다. 중복되었다고 생각할 수 있는 값을 무엇으로 둘지 계속 고민하다가 왼손과 오른손이 곂치는 경우가 있다면 이는 중복된다고 생각할 수 있다 생각했다. 만약 왼손이 3 오른손이 *을 누르고 있는 경우가 중복된다면 그 이전까지의 값이 적은 값이 무조건 최종적으로 적은값이 나오기 때문이다. 따라서 dp를 12 * 12 사이즈로 잡고, dp[i][j]에서 i를 왼손이 누르고 있는 ..
[JS] 억억단을 외우자
먼저 n이란 수가 억억단에서 나오는 횟수는 n의 약수의 개수이다. 따라서 처음에는 n의 약수 개수를 구하는 알고리즘을 활용해서 해결해보려고 했다. const getDivisorCnt = (n) => { let ret = 0; for (let i = 0; i { let cnt = getDivisorCnt(n); let ret = n; for (let i = n; i cnt) { cnt = tmp; ret = i; } } return ret; }); return ret; } 하지만 문제 케이스가 5,000,000 까지로 매우 크기때문에 위와같이 일일히 구하는건 어려웠다. 따라서 시간을 줄일 수 있는 2가지 방법을 생각해봤다. 1. 에라토스테네스의 체를 활용해서 1~5,000,000 까지의 약수의 개수를 모두..