다이나믹
-
BOJ 11727 : 2xn 타일링 2백준 문제풀이/Dynamic Programming 2020. 5. 15. 17:51
문제 문제 풀어보기 풀이 이거 하나만 확인하세요 !! 경우의 수를 계산하는 모든 과정에서 모듈러 연산을 하셨나요 ? ㅎㅎ 코드 #include #include using namespace std; int d[1001][3]; #define mod 10007 int main() { ios::sync_with_stdio(false); cin.tie(NULL); int n; cin >> n; d[1][1] = 1; d[2][0] = d[2][1] = d[2][2] = 1; for (int i = 3; i
-
[DP] BOJ 9465 : 스티커백준 문제풀이/Dynamic Programming 2019. 8. 30. 21:57
문제 상근이의 여동생 상냥이는 문방구에서 스티커 2n개를 구매했다. 스티커는 그림 (a)와 같이 2행 n열로 배치되어 있다. 상냥이는 스티커를 이용해 책상을 꾸미려고 한다. 상냥이가 구매한 스티커의 품질은 매우 좋지 않다. 스티커 한 장을 떼면, 그 스티커와 변을 공유하는 스티커는 모두 찢어져서 사용할 수 없게 된다. 즉, 뗀 스티커의 왼쪽, 오른쪽, 위, 아래에 있는 스티커는 사용할 수 없게 된다. 모든 스티커를 붙일 수 없게된 상냥이는 각 스티커에 점수를 매기고, 점수의 합이 최대가 되게 스티커를 떼어내려고 한다. 먼저, 그림 (b)와 같이 각 스티커에 점수를 매겼다. 상냥이가 뗄 수 있는 스티커의 점수의 최댓값을 구하는 프로그램을 작성하시오. 즉, 2n개의 스티커 중에서 점수의 합이 최대가 되면서 ..
-
[알고리즘] 동적 계획법(Dynamic Programming)프로그래밍/알고리즘 2019. 6. 7. 23:56
List 1. 동적 계획법(Dynamic Programming) 이란? 2. 피보나치수열 구현 3. 메모이제이션(memoization) 동적 계획법(Dynamic Programming) 이 알고리즘은 다이나믹 프로그래밍 또는 DP라고 많이 불립니다. 이전에 배웠던 알고리즘과 차이가 있다면 큐(queue) , 스택(stack)처럼 특정 자료구조를 사용해야 하는 고정적인 개념이 아니라는 겁니다. 이름의 프로그래밍(Programming) 이란 단어가 의미하는 것은 컴퓨터 언어로 코딩을 하는 것을 말하는 것이 아니라 "계획하다"의 의미를 갖고 있습니다. 따라서 이 알고리즘은 특정 문제들을 특수한 형태로 계획해서 풀어나가야 할 때 사용됩니다. 동적 계획법은 대회나 SW 역량테스트 등의 등장 빈도가 아주 높고 기본..