john8538 님의 블로그

https://www.acmicpc.net/problem/1149  동적계획법 즉 DP를 활용하여 문제를 해결할 수 있다.  그림을 통하여 문제를 조금 더 간편하게 이해해보자.    문제 이해N개의 집이 있고, 각 집은 빨강(R), 초록(G), 파랑(B) 중 하나의 색으로 칠해야 한다.인접한 집들은 서로 다른 색으로 칠해져야 한다.각 집을 각 색으로 칠하는 비용이 주어진다.목표는 모든 규칙을 만족하면서 전체 비용을 최소화하는 것.해결 접근 방식 (동적 프로그래밍)그림에서 보이듯이, 각 단계(집)마다 3가지 선택(R, G, B)이 존재.각 단계에서의 최소 비용은 이전 단계의 결과에 의존.따라서 이를 해결하려면 전에 단계에서 가져올 수 있는 숫자중 최소를 구한 후, 현재 위치와 더하면 된다!이를 계속 한 행..

https://www.acmicpc.net/problem/11727  우선 문제에 접근해보자. 2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성해야한다.규칙을 그림을 통하여 그려보았다.  2x3을 보게 된다면 규칙을 쉽게 찾을 수 있다. 앞서 구한 2x2에서 2x1이 오른쪽으로 붙어 2x3이 되는 경우와 2x1이 왼쪽으로 붙어 2x3이 되는 경우총 2가지가 존재한다. 따라서 2x2에서 구한 3개에 2x1(2개)를 더해 총 5개가 된다.2x4를 생각해보자. 2x3에서 2x1이 붙는 경우와 2x2에서 2개씩 결합하는 경우가 존재해 총 11개가 된다.이를 점화식으로 구해보자. A(n) = A(n-1) + (2 X A(n-2)) 가 된다.이를 코드로 작성하자. n = ..

https://www.acmicpc.net/problem/9095DP란?Divide-And-Conquer : Top-down approach나누어진 부분들 사이에 서로 상관관계가 없는 문제를 해결하는데 적합피보나치 알고리즘의 경우에는 나눈어진 부분들이 서로 연관이 있다.즉, 분할정복식 방법을 적용하여 알고리즘을 설계하게 되면 같은 항을 한 번 이상 계산하는 결과를 초래하게 되므로 효율적이지 않다. 따라서 이 경우에는 분할정복식 방법은 적합하지 않다. Dynamic programming: bottom-up approach큰 문제를 작은 문제로 나눈 다는 점은 Divde-And-Conquer와 동일하다.그러나 작은 문제를 먼저 해결하고, 그 결과를 저장한 다음, 후에 그 결과가 필요할 때마다 다시 계산하는 ..