DP
-
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
-
BOJ 2293 : 동전 1백준 문제풀이/Dynamic Programming 2020. 1. 23. 16:56
문제 n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다. 사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다. 입력 첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 출력 첫째 줄에 경우의 수를 출력한다. 경우의 수는 2^31보다 작다. 풀이 일반적으로 도출되는 점화식은 다음과 같다. d[i] = d[i-1] + d[i-2] + d[i-5] 하지만 이 점화식은 중복되는 동전의 조합을 처리하지 못한..
-
[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 역량테스트 등의 등장 빈도가 아주 높고 기본..
-
[DP] BOJ 11053 번 문제 풀이백준 문제풀이/Dynamic Programming 2019. 5. 13. 15:05
문제분석 DP 유형의 문제들은 점화식을 도출하는 것이 문제의 전부입니다!! D[i] = i 번째 인덱스를 마지막으로 하는 수열의 최대 길이 arr[i] = 주어진 수열 이라고 정의하고 시작하겠습니다. 그러면, D[1] = 1 은 자명합니다. D[2] 부터는 주어진 수열의 데이터를 비교해야 합니다. 1. 이전 값 중에 arr[2] 보다 작은 값들을 모두 후보 인덱스로 둡니다. 2. D[후보 인덱스] 중에 최댓값을 구합니다. 3. 그 최댓값에 자기 자신인 1을 더해줍니다. 설명이 조금 복잡하니 예시문제로 다시 봅시다. 10 20 10 30 20 50 이러한 수열이 있습니다. 이때, D[4] 를 구하고자 합니다. 그러면 우선 arr[4] = 30 의 값 보다 작은 값들을 이전 인덱스에서 색출합니다. 10 20..
-
[DP] BOJ 11726 번 문제백준 문제풀이/Dynamic Programming 2019. 5. 11. 01:48
문제분석 내용이 어렵지 않아서 추가적인 설명은 굳이 필요 없을 것 같아서 패스할게요~ 저만 그럴 수도 있지만... 처음에 이 문제를 보고 생각한 게 배열의 행을 2로 잡고 해야 되나? 도형을 뭐로 표현하지? 라고 생각했었는데 그럴 필요가 없더군요... DP 문제 점화식만 파악하면 되는 문제입니다. 우선 눈으로만 봐도 알 수 있는 경우의 수를 정의해봅시다! D[n] = 가로길이가 n 인 직사각형을 채우는 경우의 수 A = 가로길이가 2 인 직사각형 B = 가로길이가 1 인 직사각형 이라고 했을 때, D[0] = 0 D[1] = 1 D[2] = 2 3가지 경우는 확실해집니다. 이제 D[3] 에 대해서 봅시다. 상황을 두 가지로 나누어 볼 수 있습니다. D[3] 의 처음 블록을 A 로 시작하는 경우 이 경우 ..
-
[DP] BOJ 1149 번 문제 풀이백준 문제풀이/Dynamic Programming 2019. 5. 6. 16:00
문제 분석 문제는 RGB 거리에 R,G,B 의 색으로 집을 칠하는 최소비용을 구하는 것이다. 이때, 이웃하는 집의 색은 달라야 한다. 예를 들어 G 의 인덱스가 i 라고 할 때 i + 1 과 i - 1 이 이웃하는 집이다. 우선 최소비용과 색을 포함할 수 있는 배열을 선언하자. d[i][0] = i 번째 집까지 칠할 때 최소비용 단, i 번째 집은 빨간색 d[i][1] = i 번째 집까지 칠할 때 최소비용 단, i 번째 집은 초록색 d[i][2] = i 번째 집까지 칠할 때 최소비용 단, i 번째 집은 파란색 이제 배열이 선언됐으니 점화식을 끌어내 보자. 우선 경우의 수가 하나밖에 없는 초깃값들을 초기화 하자. d[0][0] = s[0][0] , d[0][1] = s[0][1] , d[0][2] = s[..
-
[DP] BOJ 2579번 문제풀이백준 문제풀이/Dynamic Programming 2019. 5. 4. 23:35
문제 분석 각 계단을 오를 때 계단에 적혀있는 숫자의 합이 가장 큰 경우를 구하는 문제다. 조건은 다음과 같습니다. ...더보기 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다. 마지막 도착 계단은 반드시 밟아야 한다. 자, 지금부터 s[i] = 계단의 적힌 숫자 d[i][j] = 현재까지 j 개의 계단을 연속해서 밟고, i 번째 계단에 올라섰을 때의 점수 합의 최댓값이라고 합시다. (단, i 번째 계단은 반드시 밟는다.) 이상태에서 주어진 계단에 대해서 한번 값을 찾아봅시다. 첫 번째 계단에서는 이러한 값이 도출됩니다. d[..