알고리즘/DP(Dynamic programming, 동적프로그래밍) (18) 썸네일형 리스트형 백준(BOJ) 15486 퇴사2 퇴사1 문제와의 차이점 동영상보고 기록해 놓기: https://www.acmicpc.net/problem/15486 어떻게 현실적으로 이 문제를 보고 어떻게 "이문제는 DP로 풀어야 한다"라고 떠올릴 수 있는 것인가? 우선은 해본다. 아래 그림과 같이 그려보는것이다. 1,2,3일째는 모두 그 이득이 0이다. 그런데 1일차에 있는 일을 하게 되면 그 이득으로 4일 차에 10을 얻게 된다. 마찬가지로 2일차의 일을 하게 되면 그 이득으로 7일차에 20의 이득을 얻게 된다. 이렇게 차근차근 표시해 나가는 것이다 우선은. 마찬가지로 3일차에 해당하는 일을 하게 되면 4일 차에 10의 이득을 얻게 된다. 그런데 이미 4일차에는 1일차에 해당하는 일을 했을때 얻을 수 있는 이득이 있다. 그러므로 1일차에 일을 하여.. 백준(BOJ) 9655번 돌게임 https://www.acmicpc.net/problem/9655 DP쓸필요 없이 그냥 단순히 규칙만 찾으면 끝나는 문제다. " n = 1 : 돌이 1개가 있으면 상근이가 1개를 가져가면 끝나므로 상근이가 이긴다. n = 2 : 처음에 상근이가 1개를 가져가고 창영이가 남은 1개를 가져가면 되므로 창영이가 이긴다. n = 3 : 상근이가 처음에 돌 3개를 가져가면 끝나므로 상근이가 이긴다. n = 4 : 상근이가 돌 1개를 가져가든, 3개를 가져가든 돌이 1개나 3개가 남으므로 창영이가 이긴다. n = 5 : 상근이가 처음에 돌 1개를 가져갈 수 도 있고 3개를 가져갈 수도 있다. → 1개를 가져갔을 경우 : 4개가 남고 창영이가 1개를 가져가든 3개를 가져가든 1개나 3개가 남으므로 상근이가 이긴다. .. 백준(BOJ) 1010번 다리놓기 https://www.acmicpc.net/problem/1010 조합을 사용하여 정말 간단히 풀리는 문제다. 내가 조합을 공부할 때는 이보다 훨씬 복잡했다. 조합을 재귀트리로 구현할때 어떻게 구현하는지와 아래와 같이 dp를 써서 구현할 때 어떻게 저런 수식이 나오는지 그리고 시중의 다른 풀이법에 대하여 공부하자. import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ public static int solution(int r, int n){ int[][]dp=new int[n+1][r+1]; for(.. 백준(BOJ) 9095 : 1, 2, 3 더하기 (countSum과 같은 문제) https://www.acmicpc.net/problem/9095 countSum문제: https://judge.koreatech.ac.kr/problem.php?id=1207 countSum과 같은 문제로 동전1, 동전2 문제와 역시 비교해서 알아두자! ( 동전1 https://flexyduck.tistory.com/92 https://www.acmicpc.net/problem/2293 동전2 https://flexyduck.tistory.com/116 https://www.acmicpc.net/problem/2294 ) 1,2,3 더하기 문제 =countSum 과 유사한 문제이다. 구성이 같고 순서가 다른 것을 다른 것으로 취급한다. for coin in coins: for i in range(coi.. [백준] 2293 동전1 https://www.acmicpc.net/problem/2293 아래 내용 이해한다면 모두 이해한 것임. 구성이 같더라도 순서가 다른것을 모두 다르게 취급하는 경우 (countSum문제) ==>>dp for문에서 아이템의 항목들을 내부반복문으로 사용 구성이 같더라도 순서가 다른것을 모두 같게 취급하는 경우(일반적이지 않은 경우로 직관적으로 이해되진 않음) (동전1 문제) ==>>dp for문에서 아이템의 항목들을 외부반복문으로 사용(아이템의 항목들이 외부반복문으로 사용되므로 2차원 테이블로는 만들수 없음. 다만 이해를 돕기 위해 2차원 테이블을 그림) dp[j]+=dp[j-i] 의 의미: dp[j] => 새로운 수를 사용하지 않은 이전의 수만 사용한 기존의 경우. dp[j-i] =>새로운수와 기존의 수.. [백준] 11066번: 파일 합치기 https://www.acmicpc.net/problem/11066 영상강의: https://fastcampus.co.kr/courses/210773/clips/ 영상보다 쉬운 해설: https://guy-who-writes-sourcecode.tistory.com/43 "dp를 어떻게 정의하는가가 상당히 어렵고 이런 문제를 처음접한다면 dp를 절대 구할 수 없습니다. 왜냐하면 이것은 유형이기 때문입니다." ==>>그동안 내가 공부했던 점화식을 구하는데 사용했던 최적의 원리를 적용하기 너무 어렵다(최적해의 부분해가 또다시 그것의 부분문제의 최적해가 된다는 것을 적용하기 힘듬). dp문제의 특징은 이미 이전의 값은 구해졌다고 가정하고 시작한다. 그 구해진 값을 통해서 이번값을 어떻게 구하는지만 해결하면 된.. [백준] 9251번 : LCS(Longest Common Subsequence) https://cryosleep.tistory.com/17 LCS란? Longest Common Subsequence=최장 공통 부분순서 그냥 댕쉬움. 문제 풀면서 인지한 동적 프로그래밍, Tabulation의 테이블 작성의 공통점. 정답을 구하기 위해 당장에는 무의미한것까지 맨땅부터 차근차근 다 해보는 것이다(당장에는 무의미하지만 그 무의미한게 답을 구하게 해줌). 두개의 문자열을 비교하는 것이므로 2차원 배열임. x축=문자열A, y축=문자열B 배열은 문자열 각각의 길이에서의 LCS의 길이로 구성됨. 비교되는 2개의 문자열의 타겟 문자가 같으면 dp[i][j]=1+dp[i-1][j-1] 비교되는 2개의 문자열의 타겟 문자가 다르면 dp[i][j]=max(dp[i-1][j], dp[i][j-1] from.. 배낭채우기 문제 0,1 배낭채우기 문제 출처:https://gsmesie692.tistory.com/113 내정리: 중요한 것은 Greedy이든 Dynamic Programming이든 같은 종류의 문제(최댓값을 구하라, 최소값을 구하라등)에 적용될 수 있는 해결책들이라는 것이다. 다만 탐욕적 방법이 안될때 동적 기법이 사용될 수 있다는 것이 차이점이다. 따라서 어떤 문제를 볼때 어느 하나만 생각하는 것은 옳지 않다. 모든 기법을 생각할 수 있는 것이 자연스러운 것이다. 도둑이 보석가게에 배낭을 메고 침입했다. 배낭의 최대 용량은 W이며, 이를 초과해서 보석을 담으면 배낭이 찢어질 것이다. 각 보석들의 무게와 가격은 알고 있다. 배낭이 찢어지지 않는 선에서 가격 합이 최대가 되도록 보석을 담는 방법은? 흔히 알고리즘을 배.. 이전 1 2 3 다음
