FrontEnd/프로그래머스
[JS] 금과 은 운반하기
상당히 어려운 문제였다. 프로그래머스 3단계쯤 들어와서부터는 절반쯤은 스스로 해결을 하지 못하는 것 같다.. (ㅜ) 이번 문제도 카카오에서 제공한 해설을 읽고 해결하였다! 문제에서 제공하는 무지막지한 테스트케이스에서 알 수 있듯이 일반적인 방식으로 문제를 접근하면 풀 수 없다. (완전탐색,DP등) 문제의 핵심은 이분탐색에 있었다. gold = 특정 시간 t 동안 얻을 수 있는 최대 골드 수 silver = 특정 시간 t 동안 얻을 수 있는 최대 실버 수 add = 특정 시간 t 동안 골드와 실버를 한번에 얻을 수 있는 최대 수 라고 두었을때 a + b = a && silver >= b && add >= a + b) { end = mid - 1; ret = Math.min(mid, ret); }else {..
![[JS] 아이템 줍기](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FrEc3r%2FbtszLkxr9pI%2FOsKSCKSbQkeNDBWf9EfV2K%2Fimg.png)
[JS] 아이템 줍기
https://school.programmers.co.kr/learn/courses/30/lessons/87694 프로그래머스 코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요. programmers.co.kr 처음에 문제접근을 잘못해서 두번 해결한 문제였다. 처음에는 도화지위에 네모 모양의 성벽을 쌓은 이후, 밖에서 물을 부으면 성벽을 기준으로 바깥쪽만 물의 영역이 되는 원리를 이용해서 문제를 해결하려고 했다. (비록 문제에서는 직사각형이 4개뿐이지만 위 방법을 사용하면 직사각형의개수가 매우많아져도 시간복잡도에 크게 영향이 없기 떄문) 해당방법으로 구현은 했지만 위처럼 ㄷ자로 이어지는 성벽을 구현하지 ..
[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..