JS/알고리즘4 JS, DP(Dynamic Programming) [ 동적 계획법(Dynamic Programming) ] 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것 즉 큰 문제를 작은 문제로 쪼개서 그 답을 저장해두고 재활용 함 ▶ DP를 사용하는 이유 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러번 반복되어 비효율적인 계산이 될수 있음 예를 들어 피보나치 수의 경우 1이상의 n의 경우 F(n) = F(n-2) + F(n-1)적용되는 수를 말함(F(0)=0, F(1)=1) 만약 n이 4라면 재귀호출 방식을 사용하게 되면 F(4) = F2 + F(3) = (F(0) + F(1) ) + ( F(1) + F(2) ) = (F(0) + F(1) ) + ( F(1) + (F(0) + F(1) ) ).. 2023. 12. 13. JS, 약수구하기 기존의 반복문으로 주어진 수의 절반을 대상으로 확인하기를 하니 코테 문제 시간초과가 뜸 더 효율적인 방법이 필요하여 방법을 찾아보고 정리 [ 제곱근 사용하기 ] 약수를 구하고자 하는 수를 n이라고 하면 1 ~ √n 범위로 n의 약수를 구함 n의 약수를 나누었을 때 값 또한 n의 약수 √n의 값이 정수로 떨어질 경우 약수와 나누었을때의 값으로 넣은 약수가 중복되므로 중복제거를 해야함 ▶ 약수 구하는 코드 조건문 사용 const getDivisors = (num) => { let result = []; for(let i = 1 ; i a - b);//오름차순 정리 return result; } Set 사용 const getDivisors = (num) => { let result = []; for(let i.. 2023. 11. 23. JS, 에라토스테네스의 체 소수찾기 문제를 할때 반복문으로 풀게되면 효율성 테스트에서 시간초과로 실패가 뜸 이런 경우 에라토스테네스의 체 방법을 사용하면 효율적으로 문제를 풀어 효율성 테스트를 통과할 수 있음 [ 에라토스테네스의 체 ] 1부터 제외하고 2부터 N까지 자신을 제외하고 순차적으로 자신의 배수들을 지워가면 결국에는 소수들만 남는다는 원리 n까지가 아닌 √n까지만 검색해도 결과는 같음 ▶ 에라토스테네스의 체 과정 2부터 N까지 모든 정수를 적음 아직 지우지 않은 수 중 가장 작은 수를 찾음(이것을 P라고 하고 이 수는 소수) P를 지우고 아직 지우지 않은 P의 배수를 크기 순서대로 지움 아직 모든 수를 지우지 않았다면 다시 2번 단계부터 반복 ▶ 에라토스테네스의 체 코드 function solution(n) { let a.. 2023. 11. 23. JS, 최대공약수 최소공약수 구하기 최대공약수를 구할때 기본적으로 반복문을 돌려서 최대공약수를 구할수 있으나 유클리드 호제법을 이용하여 구하면 쉽게 간단하게 구할 수 있음 유클리드 호제법 두 수의 최대공약수를 구하는 알고리즘 2개의 자연수 A, B에 대하여 A를 B로 나눈 나머지를 r이라고 한다면(단, A>B) A와 B의 최대공약수는 B와 r의 최대공약수와 같음 이 성질에 따라 B를 r로 나눈 나머지를 r'을 구하고 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을때 나누는 수가 A와 B의 공약수 예시 유클리드 호제법으로 24, 15의 최대 공약수 구하기 24 % 15 = 9 15 % 9 = 6 9 % 6 = 3 6 % 3 = 0 구현 function gcd(a, b){ return (a % b) === 0 ? .. 2023. 11. 3. 이전 1 다음
