FrontEnd/프로그래머스
[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) 이런 경우까지 다 고려해야 하며 그중에서 중복되는 값들이 생길 수 있어 계산하기 매우 번거로워진다. 따라서 유니크 타일이란 개념을 도입하면 이를 조금 쉽게 생각할 수 있다. 유니크 타일이란 ..
![[JS] 상담원 인원](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fb6SwZz%2FbtsxsRbYhyx%2FySfKhPvhgusbPbWlzuIFJ0%2Fimg.png)
[JS] 상담원 인원
문제를 처음 딱 읽고 보니 완전탐색이 떠올랐다. 어차피 유형이 최대 5개이니 합이 n이 나오는 5개의 수 조합을 찾으면 되는 문제였다. 몇번 공부했었던 combination을 구하는 로직을 조금 비틀어서 위 수식을 구한 이후에는 시나리오들을 돌려보며 time들을 구하면 되는 문제이다. 어떻게 풀까 하다가 객체를 통해서 문제를 해결하기로 했다. 상담자 객체를 하나 만들어서 상담이 종료되는 시각과 타입이 들어온다. 문제에서 상담원들은 시간순서대로 들어오기 때문에 1. 상담받을수 있는 상담가 중에서 종료 시간이 가장 최근인 상담가를 선택 종료시간이 현재보다 과거라면 지금당장 상담을 받을 수 있기에 상담가의 종료시간을 현재시간 + 상담기간으로 설정 종료시간이 현재보다 미래라면 지금당장 상담 받을 수 없기에 상담..
![[JS] 에어컨](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2Fy0xPJ%2FbtswUYb7UPn%2FKhNFvLBNr8mkBcJFmmck2k%2Fimg.png)
[JS] 에어컨
쉽지 않은 문제였다... dp로 풀면 뭔가 될꺼 같은데 1시간정도 넘게 고민을 해도 뭔가나올듯 말듯 했다. 그러다가 힌트만 참고하잔 생각으로 질문게시판을을 봤는데 dp를 2차원으로 쓴다는 말만 보고 아이디어를 얻고 혼자 생각해보았다. 오랜만에 난이도있는 dp문제를 접해서인지 dp를 2차원으로 둘 생각을 못했다!! 최대 1000초의 시간이 주어지고 온도도 50도 안으로 오니 가능했었던 문제였다. 만약 첫번째 예시를 통해서 dp를 채우면 아래와 같이 나와야 한다. N은 편의상 INF중에서 N만 쓴것으로 무한대를 의미한다! 손님이 없다면 모든 경우의 수를 보고 있다면 희망온도 안에서만 경우의 수를 따지면 된다. 이때 생각해야할 것이있다. 1. 에어컨을 1도 올리는 경우 2. 에어컨을 1도 내리는 경우 3. 에..
[JS] 게임 맵 최단거리
BFS의 교과서(?) 적인 문제였던 것 같다. dx,dy 배열로 상하좌우 로 갈 방향을 정해주고 visited로 방문했던 곳인지 아닌지를 체크해준다. 큐 구조를 활용해서 BFS를 구현하였다. (케이스가 크지않아 실제 큐 구조로 문제를 해결하지는 않았다) ny,nx가 갈 수 있는 범위이면서 방문한 적이 없고 map에서 갈 수 있는 곳이라면 큐에 다음 목적지를 넣어주었다. function solution(maps) { const dx = [1,0,-1,0] const dy = [0,1,0,-1] const m = maps.length const n = maps[0].length const visited = [...Array(m)].map(v => Array(n).fill(false)) const que = ..
[JS] 124 나라
사실 3진법 문제이다. 단 0이 없어서 조금 많이 애를 먹었다. 우리가 진수를 변환할때처럼 3으로 나눠가며 나머지를 역순으로 더해주면 된다. 단, 123이 아닌 124가 나오도록 바꿔주면 된다. function solution(n) { let ret = ""; while(n > 0){ if(n % 3 === 0){ ret = "4" + ret n = ~~(n / 3) - 1; }else{ ret = (n % 3) + ret; n = ~~(n / 3); } } return ret }