Algorithm179 백준 11727 ▶11727번 문제 ▶풀이방법 import java.io.*; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int num = Integer.parseInt(br.readLine()); int[] dp = new int[num+2]; dp[1] = 1; dp[2] = 3; for(int i = 3; i 2022. 3. 20. 백준 11726 ▶11726번 문제 ▶풀이방법 import java.io.*; public class Main{ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int num = Integer.parseInt(br.readLine()); int[] dp = new int[num+2]; dp[1] = 1; dp[2] = 2; for(int i = 3; i 2022. 3. 19. 알고리즘 - Dynamic Programming(동적 계획법) ▶ 다이나믹 프로그래밍 - 복잡한 큰 문제를 간단한 여러 작은 문제로 나눠서 푸는 알고리즘 ▶ 다이나믹 프로그래밍 방법. - 모든 작은 문제들은 한번만 풀어야 함. - 작은 문제들에 대한 정답을 어딘가에 메모해 놓아야 함 -> Memoization - 같은 문제가 나타나면 메모해 두었던 작은 문제의 결과값을 이용함. - 피보나치 수열 사용 ▶ 다이나믹 프로그래밍 조건 1. 작은 문제가 반복이 일어나는 경우. 2. 최적 부분 구조. 작은 문제의 결과 구할 때 과정에 사용된 정답 항상 같음. ▶ 다이나믹 프로그래밍 구현 방법 1. Top-Down : 재귀함수 이용한 방법(문제를 여러 문제로 나눠 놓고 필요할 때 구함) 2. Botto.. 2022. 3. 19. 백준 1463(Dynamic Programming) ▶1463 문제 ▶ 문제풀이 - 동적 계획법 사용해야함 점화식 : dp[n] = Math.min(dp[n-1], dp[n/2], dp[n/3]) + 1; - 초기값 설정 : 위의 문제에서 1이 입력되었을 때 이미 1이기 때문에 0이 출력됨. (dp[1] = 0) - dp[2] = dp[1] + 1 = 1; - dp[3] = dp[1] + 1 = 1; - dp[4] = dp[2] + 1 = 2; - dp[5] = dp[4] + 1 = 3; ..... - dp[10] = dp[9] + 1 = 3; import java.io.*; public class Main{ public static void main(String[] args.. 2022. 3. 19. 이전 1 ··· 33 34 35 36 37 38 39 ··· 45 다음
