ALGORITHM/DP3 [JAVA] 백준 2293번 https://www.acmicpc.net/problem/2293 동전 1 -다이나믹 프로그래밍 [백준 2293번] 동전 1 예제를 풀어 봄 문제 파악 해서 정리 해 봄: n개의 숫자 조합을 이용해 합 k를 맞추는 경우의 수를 찾는 문제. (순서 상관없고, n개 다 이용 안 해도 됨, 동전 중복 사용 가능) 풀이 생각해 봄: dp 1원부터 생각->1,2원 두가지 동전 종류가 있을 때 생각 -> 1,2,3원 세 가지 동전 종류가 있을 때 생각 ~ 이 과정에서 규칙을 발견하고 점화식 세워보기 코드 짜기. 출처 https://songsunbi.tistory.com/67 하나 더 고려해야 할 점이 있습니다. 3원으로 경우의 수를 계산하는데 1원과 2원의 경우를 계산할 필요가 있을까요? 어차피 제가 가지고 있는 .. 2019. 6. 2. [JAVA] 백준 2839번 문제: https://www.acmicpc.net/problem/2839dp는 메모리는 많이 차지하나, 빨리 푸려고 쓸 때 쓰는 방법dp 문제 풀 때 tip -> 문제에서 제시된 범위 ex( 2 2019. 1. 27. Dynamic Programming 수업 필기 2.Divide and Conquer-> top down 해결법, 나누어진 부분들 사이에 상관관계가 없는 문제를 해결하는데 적합. ex) 피보나치 알고리즘에 d&c 방법을 사용하면 호율적 x. 왜냐? 피보나치의 경우 나누어진 부분들이 서로 연관되어 있기 때문 3.재귀적 해법. divide and conquer로 푸는 방법 중 가장 안좋은 예 4.피보나치를 d&c로 풀면 심각하게 비효율적&엄청난 중복 호출. 5,6.동적 프로그램이 solution. ex) 피보나치 수를 구하는 동적 프로그래밍 알고리즘fibonacci(n){f[0] = 0; f[1] = 1;for (i =2; iprincipal of optimality가 성립함. 2. Principle of Optimality가 성립하지 않는 예)* Lon.. 2018. 12. 17. Prev. 1 Next.