알고리즘/이론2 알고리즘에서 약수 개수 찾기(Feat. 제곱근까지만 검사해도 되는 이유!) 16의 약수의 개수를 찾는 코드를 작성해보자. 16을 1부터 16까지 반복문을 통해 나눈다. - 만약 나누어 떨어진다면 -> 약수이다 - 나누어 떨어지지 않으면 -> 약수가 아니다 그런데 항상 1부터 16까지 전부를 검색해야 할까? 16의 제곱근은 4이다. 16의 약수는 1, 2, 4, 8, 16이다. 1, 2, 4, 8, 6 제곱근인 4까지만 검사하면, 나머지 약수는 4를 기준으로 대칭으로 나온다. 따라서 4보다 큰 약수를 찾을 필요 없다 public int countDivisors(int n) { int count = 0; int root = (int) (Math.sqrt(n)); for(int i = 1; i 2023. 9. 11. DP(Dynamic Programming)이란? - 스티커, 동전, LCS, 행렬 곱셈 순서 동적 프로그래밍이란? 동적 프로그래밍은 큰 문제를 풀 때, 큰 문제의 일부인 작은 문제를 푸는 과정에서 발생하는 중복을 해결하는 방법이다. 이때 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있는 것을 최적 부분 구조(Optimal Substructure)를 가졌다고 표현한다. 대표적인 예시로 피보나치 수열이 있다. 피보나치 수열은 다음의 정의를 갖는다. f(n) = f(n-1) + f(n-2) f(1) = f(2) = 1 즉, n은 n-1과 n-2 피보나치 수를 모두 갖고 있다. 만약 이 문제를 재귀호출로 푼다면 어떨까? fib(n) { if (n == 1 or n == 2) then return 1 else return (fib(n-1) + fib(n-2)) } 이렇게 푸는 방식은 매우 비효율.. 2023. 5. 3. 이전 1 다음
