다이나믹프로그래밍
-
[알고리즘]다이나믹프로그래밍-1로만들기알고리즘 2022. 2. 21. 22:30
정수 X에 사용할수있는연산은 다음과같이 세가지 1. X가 3으로 나누어 떨어지면 3으로 나눈다. 2. X가 2로 나누어떨어지면 2로나눈다. 3. 1을 뺀다. 예제 ) 8 , 10 최소 : 8 4 2 1 (3회) 3으로 먼저 나누려는 경우 : 8 7 6 2 1 (4회) 최소 : 10 9 3 1 (3회) 2로 먼저나누려는 경우 : 10 5 4 2 1 (4회) 점화식 구하기 2나 3의 배수일 경우 바로 구한다. 아닐경우 -1을 하여 다시 구한다. public static int[] arr; public static int calc(int n){ if( n== 1 ){ return 0; } if( arr[n] > 0 ){ return arr[n]; } arr[n] = calc( n-1 ) + 1; //2로 나누..
-
[알고리즘] 다이나믹프로그래밍알고리즘 2022. 2. 21. 21:50
Overlapping Subproblem 겹치는 작은 문제 Optimal Substructure 최적부분구조 Optimal Substructure 목적 문제의 정답을 작은 문제의 정답에서 구할수 있다. 모든 문제를 풀며, 모든 문제는 1번만 풀어야한다. 시간복잡도 문제의 개수 : N 모든 문제를 1번씩 푸는 시간 : 1 O(N)의 시간복잡도를 가진다. ex) 서울 > 부산 가장빠른길은 대전과 대구를 거친다의 조건이 있을경우, 대전 > 부산 가장빠른길은 대구를 거친다. 프로그래밍 방법 Optimal Substructure을 만족하면 정답을 메모한다. ( 코드에선 배열 ) Memoization 예제 피보나치수열 피보나치를 구하게 될경우 아래의 코드와 같다. int fi(int n){ if( n