전체 글270 백준 가장 긴 증가하는 부분 수열 11053 문제 설명 : 주어진 수열 내에서 가장 긴 수열의 길이를 찾는 것이다. 문제내에서 주어진 것의 예시를 보겠습니다. 수열 A = {10, 20, 10, 30, 20, 50} 여기서 10, 20, 30 ,50되니 4이다 문제 풀이 : 여기서 점화식은 dp[idx] -> idx번째 원소의 값이 있는 위치에서 가장긴 수열의 길이이다. 이러한 점화식이 있을때 조건은 범위가 i = 1 ~ i 가장 긴 부분수열이니 원소의 값도 더 작아야한다 중요 부분 소스 for (int i = 0; i < idx; i++) { if (i < idx && v[i] < v[idx]) { dp[idx] = max(solve(i) + 1, dp[idx]); } 2021. 8. 3. 백준 12865 평범한 배낭 문제 설명 : 문제에 제한된 무게내에서 최대의 가치를 담자 문제의 점화식 d[idx][kk] => 현재 idx까지 봤고 idx + 1을 보며 남은 무게가 kk일 경우 최대의 가치 문제 풀이 : 조건1. 가치를 더 할때 해당 남은 무게에 해당 무게를 빼게 될때 남은 무게가 0이상이 되어야한다 조건2. 무게를 더 했을경우나 더하지 않았을 경우 최댓값을 찾으면된다 dp테이블에 초깃값을 넣을때 아무것도 안해도 기본 가치는 0이기에 d[idx][kk] = 0을 넣는다 //idx번째는 보고 idx + 1번째를 보려고하는 중이다. if (kk - w[idx + 1] >= 0) { dp[idx][kk] = max(solve(idx + 1, kk - w[idx + 1]) + v[idx + 1], solve(idx + 1.. 2021. 8. 3. B. Two Tables 문제 설명 문제는 큰 룸이 있고 거기에 하나의 사각형이 있고, 다음 주어진 크기의 사각형을 기존의 사각형을 최소한으로 움직여서 둘이 겹치치 않 도록 하라는 문제이다. 틀린 이유 : 마지막에 w, h축을 비교 후 둘다 움직일 경우 최소를 봐야하는데 고려하지 않았다 각 각 ans에 대한 최소를 구하려고 ``` if (x2 - x1 + w 2021. 8. 2. dp.. 개념 개념 dp는 점화식의 정의를 잘 내려야한다 dp의 방식은 top -down, botton -up 방식이 있는데 top - down방식을 쓰면 점화식 조건을 그대로 쓸 수 있는 장점이 있다. dp는 어떤 것이 dp인가 -> 문제를 나눌때 문제가 겹치는 부분이 있을 수 있다 예를 들면 피보나치를 트리 구조로 나타내면 겹치는 부분들이 많다 이부분들을 메모이제이션 기법을 적용하면 빠른 시간 내에 구할 수 있다 시간복잡도 구하기 dp의 시간복잡도 구하기 -> dp 테이블의 크기(문제의 갯수) * 하나 푸는데 참조하는 부분문제의 갯수이다 2021. 8. 2. 이전 1 ··· 61 62 63 64 65 66 67 68 다음
