Dynamic Programming (2) 썸네일형 리스트형 [코딩테스트][알고리즘] 4. DP( Dynamic Programming) 다이나믹 프로그래밍 다이나믹프로그래밍의 기본적인 아이디어는 한 번 풀었던 문제를 다시 풀지 말자! 라는 것이다. 풀었던 문제의 답을 배열에 저장해놓고 필요할때 다시 사용함으로써 시간복잡도를 줄일 수 있게 된다. 이러한 과정을 메모이제이션(Memoization) 이라고한다. 이러한 메모이제이션을 거치면 저장할 공간이 필요하기에 공간복잡도는 불리해지지만, 시간복잡도는 유리해진다. DP는 분할정복기법( 해결했던 문제도 다시 계산 )을 개선 한 것 인데, 대표적인 예가 피보나치수열을 구하는 것이다. 피보나치 수열은 1 1 2 3 5 8 13 21 34 - - - 와 같이 D[i] = D[i-1] + D[i-2] 의 공식에 의해 진행되는 수들의 나열이다. 분할정복기법을 사용하여 피보나치 수열의 6번째 수를 구하는 과정은 다음과 같다.. JAVA - 백준 알고리즘 - 2133 타일 채우기 https://www.acmicpc.net/problem/2133 이 문제는 DP (동적 계획법) 알고리즘을 사용하면 풀 수 있는 문제이다. 자세한 설명은 주석을 참고하면 된다. dp를 풀때는 아무것도 하지 않는 경우도 경우의 수 1로 본다는 것을 알아두어야겠다. import java.util.Scanner; public class Main { static int[] arr = new int[31]; // dp 값 저장을 위한 배열 static int result; public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); // 입력 System.out.print(dp(N)); // 출.. 이전 1 다음