반응형 Algorithm/프로그래머스30 Level2. 프로그래머스 피보나치 수 - JavaScript DP를 이용하여 풀 수 있습니다. DP는 큰 문제를 나누어 작은 문제를 해결하면서 점차 점차 큰 문제를 해결하는 방식입니다. 핵심은 memoization인데 작은 문제의 정답을 기록해 두어서 다음 문제를 풀 때 활용합니다. 문제 설명 피보나치의 경우 f(n) = f(n-1) + f(n-2)입니다. 기본적으로 f(0) = 0 f(1) =1 입니다. f(2) = f(1) + f(0) 이므로 f(2)는 1입니다. 다음으로 f(3) = f(2) + f(1) 이므로 f(3)은 2입니다. 이런 식으로 0 1 1 2 3 5 8 ... 으로 커집니다. function solution(n) { const divider = 1234567 const dp = [0, 1]; for( let i = 2; i 2020. 11. 5. Level3. 프로그래머스 야근 지수 - JavaScript 문제 설명 works에 있는 작업량을 n만큼 뺄 수 있는데 빼고 난 후 각 작업량의 제곱을 더한 값이 야근 지수가 됩니다. 작업량을 뺄 때 최대치만 없앤다고 좋은게 아니고 작업량을 최대한 비슷하게 만들면 야근 지수를 최소화 할 수 있습니다. 예를들어 [4,3,3]의 작업이 있을 때 4의 작업을 할 수 있다고 [3,3]을 만들면 3^2 + 3^2 = 18입니다. 하지만 최대값의 작업량을 없애면서 작업량을 비슷하게 만들면 [2,2,2]가 되고 2^2 + 2^2 + 2^2 = 12가 됩니다. 처음에는 모든 작업을 더하고 n 만큼 뺀 다음에 작업량을 골고루 분배해서 각 작업에 제곱을 하면 될줄 알았는데 테스트 케이스 에서 막혔습니다. 혹시나 이렇게 푸신 분은 알려주세요 ㅠ 다른 방법으로도 접근할 수 있는데 우선.. 2020. 11. 4. Level2. 프로그래머스 다음 큰 숫자 - JavaScript 문제 설명 어떤 수 n이 주어 질 때 n 보다 큰 자연수이고 2진수 변화 시 1의 개수가 같아야 한다. 또한 위의 조건을 만족하는 수 중 가장 작은 수라는 말이 있는데 이 뜻은 15(1111) 23(10111) 27(11011)이 있다고 했을 때 15보다 큰 수 중에 조건을 만족하는 수 는 많지만 가장 작은수는 23이기 때문에 23이 정답이다. 접근 1. n을 2진수로 변환하고 1의 개수를 가져와 a변수에 저장 2. for문을 num(n+1)을 시작으로 1,000,000 이하의 자연수까지 돌린다. 3. num을 2진수 변환하고 1의 개수를 가져와서 a와 비교하여 일치하면 리턴 아니면 계속 돌린다. function solution(n) { var answer = 0; const MAX_N = 1000000.. 2020. 11. 4. Level3. 프로그래머스 단어 변환(BFS) - JavaScript 문제 설명 단어 A에서 다른 단어 B로 바꿀 때 가장 짧은 변환 과정을 찾아야 한다. A가 바꿀 수 있는 단어는 words에 있는 단어로만 바꿀 수 있으며 한 번에 한개의 알파벳만 바꿀 수 있다. 에를 들어 hit에서 cog로 바꿔야 하고 words에는 [hot,dot,dog,lot,log,cog]가 들어 있다 했을 때 hit에서 알파벳 하나만 바꾸면 hot 으로 바꿀 수 있다. hot는 dot 또는 lot으로 바꿀 수 있다. 다시 dot은 cog로 lot은 cog로 바꿀 수 있다. 그렇다면 hit에서 cog로 4단계가 걸린다. - 각 단어를 노드라고 봤을 때 한 노드와 다음 노드가 인접한지 여부는 단어 변환이 가능한지로 판별할 수 있다. - 노드를 방문했다면 거리를 나타내는 값을 기록한다. hit - .. 2020. 11. 2. 이전 1 2 3 4 5 ··· 8 다음
