반응형 SMALL DP3 [백준] 11726번: 2xn 타일링 (Java/자바) 문제https://www.acmicpc.net/problem/11726 문제풀이전형적인 DP 문제이다. 이 문제는 처음에 봤을 때 완전 탐색으로 풀어야하나? 이렇게 고민되기도 하지만, 그렇게 된다면 구현 자체도 복잡할뿐만 아니라 2의 N승까지의 복잡도를 갖기 때문에 시간내에 풀 수 없게된다. 천천히 생각해보면 N = 1, N = 2, N = 3, ... 일때의 상황을 그려보고 점화식으로 풀이가 가능한 형식임을 눈치채야한다. 점화식은 dp[N] = dp[N-1] + dp [N-2] 이다.dp[1] = 1 // N == 1 일 때 가능한 조합은 1가지 뿐이다.dp[2] = 2 // N == 2 일 때 가능한 조합은 2가지 이다. (2x1 을 2개 쌓거나, 1x2를 2개 쌓거나)dp[3] = 3 // N ==.. 2024. 7. 28. ⭐ [백준] 11053번: 가장 긴 증가하는 부분 수열 (Java/자바) 문제https://www.acmicpc.net/problem/11053 문제풀이가장 베이직한 DP 문제라고 할 수 있다. 일반적으로 DP는 이전 값을 `기억` 하는데 초점을 맞추면 된다.memoization alogorithm 이라고 할 수 있는데 위 문제가 가장 기초가 되는 문제이다. 예제를 기준으로 설명하자면 아래와 같다. 1. N의 크기를 갖는 dp 배열을 생성한다.2. dp는 0~N 까지의 index의 수열들이 갖는 최대 부분 수열을 저장할 용도이다.3. dp는 초기에는 값을 업데이트 하지 않았기 때문에 자기 자신만을 수열로 갖는 상태이므로 1로 초기화 시켜준다.4. [ 10, 20, 10, 30, 20, 50 ] 수열의 0 index에서 부터 N번째 index까지 순차적으로 탐색한다.5. 탐.. 2024. 7. 24. [BOJ_2133_KOTLIN] 타일 채우기 문제 https://www.acmicpc.net/problem/2133 2133번: 타일 채우기 3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자. www.acmicpc.net 입력 첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다. 출력 첫째 줄에 경우의 수를 출력한다. 문제풀이 더보기 참고사이트 https://blog.naver.com/hands731/221806277981 2133번 : 타일 채우기 문제 : https://www.acmicpc.net/problem/2133 핵심 -n=6일때 1.dp[4]*dp[2] 2. 위에서 특이케이스를... blog.naver.com DP문제는 아직 너무 어려운 것 같다. 점화식을 찾으려고 나름대로 머리를 썼으나, 홀수인 경우 짝이 맞지.. 2021. 12. 29. 이전 1 다음 반응형 SMALL
