FrontEnd
[JS] 양과 늑대
첫 단추를 많이 헤매서 푸는데 어려운 문제였다. 처음에는 재귀를 활용해서 트리를 한번만 순회하는 구조로 풀어보려고 했다. 재귀의 반환 값을 배열로 두고, 배열의 n번째를 n개의 양을 투입하였을때 얻을 수 있는 양의 개수.. 로 두고 문제를 해결하려고 했다. 해당 방법으로는 트리를 한번만 순회할순 있었지만 내가 그 양을 얻을때 필요한 늑대의 개수를 생각할수가 없었다. 문제의 힌트는 트리의 크기가 17개로 제한된다는 점에서 사실 있었다. 트리의 크기가 17개밖에 안되게 제한된다는건 사실 완전탐색으로 풀어보라는 의미가 컸다... dfs의 인자로 현재 탐색할 node,양의개수,늑대의개수,현재 내가 탐색할 수 있는 노드의 수를 설정한다. 위 방법대로 해결하면 dfs로 탐색하는 방법 중에 단순히 노드를 한번씩 방문..
[JS] 파괴되지 않은 건물
https://school.programmers.co.kr/learn/courses/30/lessons/92344 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제 자체는 매우 심플하지만 시간초과를 해결하기 위해서 독특한 방법이 필요한 문제였다. 스스로 고민을 좀 해보았지만 방법이 떠오르지 않아서 카카오에서 제공하는 공식 해설을 보고 방법을 이해한 후 구현만 직접 해보며 해결하였다. 문제의 핵심은 누적합을 이용하는 것이다! 예를 들어서 [ 1 , 3, 5, 2, 5 ] 이렇게 5개의 수가 있는 1차원 배열을 생각해보자. 해당 수에서 index가 1~3 ..
![[JS] 사라지는 발판](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FckIXer%2FbtszyNFAvNp%2FRSUYRFEGY4JAvTK7MuKVK0%2Fimg.png)
[JS] 사라지는 발판
https://school.programmers.co.kr/learn/courses/30/lessons/92345 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 문제의 조건 케이스가 5*5 케이스이고 생각해야 할 부분이 많아서 완전탐색을 이용해야 한다고 생각을 했다. 따라서 처음에 완전탐색으로 모든 게임의 경우의 수를 구하는것까지는 성공했고 테스트 케이스들의 시간초과 또한 나지 않는 것을 확인하였다. 그런데 문제가 있었다. 어떻게 정답을 이끌어내지?! ㅋㅋㅋㅋㅋ 최대값을 정답으로 하자니 최선의 수가 아니게 되고 최소값을 정답으로 해도 최선의 수가 아니게 ..
[JS] 코딩테스트 공부
처음에 문제를 보자마자 dp..? 라는 생각이 드는 문제였다. dp[i][j]로 2차원 배열을 둔 후, i를 코딩력 , j를 알고력을 나타내게 하였다. 이어서 배열을 채워나갔는데 내가 문제를 해결한 과정은 아래와 같다. 1. 필요한 최대 알고력,코딩력 확인 (이하 알고력 => alp 코딩력 cop) 2. dp 크기를 maxCop , maxAlp 만큼 잡아서 만듬 3. 배열을 처음 초기화 할때 만들 수 있는 가장 최대의 값들로 초기화한다. 4. 배열을 순회할 때 alp,cop부터 순회한다 maxAlp) maxAlp = alp_req if (cop_req > maxCop) maxCop = cop_req } const dp = [...Array(maxCop+1)].map((_,c) => [...Array(ma..
[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를 ..