FrontEnd
[JS] 미로 탈출 명령어
처음에는 일반 미로 문제 풀듯이 dfs를 사용해서 풀어보았다. 결국 사전순이란게 미로의 길을 먼저찾는 우선순위를 정해줬다고 생각했다. function solution(n, m, x, y, r, c, k) { const map = [...Array(n + 1)].map((_) => Array(m + 1).fill(".")); map[r][c] = "E"; const dy = [-1, 0, 0, 1]; const dx = [0, 1, -1, 0]; const dOrder = "urld"; const stk = [[x, y, ""]]; while (stk.length) { const [cy, cx, order] = stk.pop(); if (order.length === k) { if (map[cy][cx] ..
[JS] 표 병합
표 병합을 주제로 한 구현문제였다. 딱 문제를 보자마자 떠오른 생각이 union-find 를 활용하자였다. 따라서 병합된 표를 구현하기 위해서 union-find 알고리즘을 응용하였다. 2차원 배열의 unionfind를 통해 셀을 구현하고 문제에서 주어진 명령어들을 구현하였다. 1. merge union-find 알고리즘에서 union 단계를 수행한다. 더 작은 수를 가진 쪽이 부모가 되게 했다. 2. update 단순히 cell의 내용을 바꿔주면 된다. 이후 명령어 처리가 편하도록 인자의 개수가 2개,3개에 따라 다른 함수가 호출되도록 구현하였다. 3. unMerge r,c 로 들어온 셀의 부모 요소를 가지고 있는 모든 셀을 초기화해준다. 이때 초기화를 해주면서 탐색하면 연결고리가 끊어지는 경우가 있어..
[JS] 표현 가능한 이진트리
처음에 문제를 조금 헷갈려서 어려운 문제였다. 사실 문제 자체를 해결하는 로직자체는 어렵지 않다. 1. 수를 이진수로 바꿔서 트리형식으로 펼치기 2. 이진트리가 될 수 있게 더미노드를 추가하기 3. 더미노드가 추가된 이진트리가 올바른 트리인지 확인하기 1번에서 조금 헤맸다. 만약 더미노드를 추가한다면 0을 앞뒤로 넣는다는건데 어떻게 얼마나 넣어야하는지 헷갈렸다. 두가지를 보자. 1. 더미노드를 활용해서 포화이진트리를 만들어야 한다. 2. 수가 변하면 안된다. 1번은 스스로 잘 생각해냈다. 포화이진트리가 되려면 2**n-1개의 크기 즉 트리의 크기가 1,3,7,15,31,63 ... 식의 배열을 따라야 한다. 처음 이해가 안되었던 점은 그렇다면 0을 어디에 붙이냐였다. 2번 부분에서 이를 확인할 수 있었다..
[JS] 인사고과
원호의 등수를 알고 싶다면 원호보다 인사고과를 잘 받은 사람들의 수를 세면 된다. 우선 두수의 합이 원호보다 큰 사람들을 가려낸 후, 그 사람들 사이에서 인사고과를 받을 수 없는 사람들을 제외하면 된다. 이게 가능한 이유는 자신보다 합이 적은 사람에 의해서는 인사고과를 받을 수 없기 때문이다. a + b > c+ d 라면 a>c && b>d 일수 없기 때문 function solution(scores) { const ary = [] const [wanhoA,wanhoB] = scores[0] for (let i=0; i wanhoA+wanhoB) ary.push([a,b]) if (a> wanhoA &..
[JS] 연속 펄스 부분 수열의 합
문제 자체는 부분수열의 합을 구하는 방법을 알면 해결할 수 있는 문제이다. 1 , -1 , 1 , -1 ... -1 , 1 , - 1 , 1 ... 해당되는 펄스를 각각 곱한 2개의 수열을 만들어주면 된다. 이어서 dp를 활용해서 부분수열의 합중 가장 큰 값을 가지면 된다. 아래 예시를 보며 생각해보자. 2 3 -6 1 3 -1 2 4 dp[n] 을 n번째에 올 수 있는 가장 최대치의 부분수열의 합이라 생각하고 maxDp[n]을 n번를 무조건 포함한 가장 최대치의 부분수열의 합이라 생각하자. 결국 dp[n] = Math.max(dp[n-1] , maxDp[n]) 이 되게된다. n번째 값이 들어왔을때 이를 포함한 부분수열의 합이 더큰가 아닌가만 확인하면 되는 문제로 바뀐 것이다. maxDp[n]은 아래와 ..
![[JS] 아방가르드 타일링](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FlRzF8%2FbtsxtXKaPBE%2FArLNMu13Z7aDmDPgwnR7Q0%2Fimg.png)
[JS] 아방가르드 타일링
이전 3*n 타일링을 이해했다면?! 이해할만한 문제였다. 가장 중요한 포인트는 이것이다. 세로줄이 한개씩 늘어날때마다 얼만큼의 경우의 수를 찾아야 하는지를 알아야 한다. 편의상 f(1)을 1개를 만들 수 있는 경우의 수라고 생각해보자. f(1) = 1 f(2) = 3 f(3) = 10 우리가 생각할 때 f(4)를 만드는 경우, f(1) * f(3) f(2) * f(2) f(3) * f(1) 위 값들을 다 더하면 된다.. 라고 생각해도 될까? 정답은 아니다 위처럼 나눈다면 f(1) * f(1) * f(1) * f(1) 이런 경우까지 다 고려해야 하며 그중에서 중복되는 값들이 생길 수 있어 계산하기 매우 번거로워진다. 따라서 유니크 타일이란 개념을 도입하면 이를 조금 쉽게 생각할 수 있다. 유니크 타일이란 ..