백준33 [11057] 오르막 수 - C++ 문제 왜 DP를 써야 하는지 감조차 오지 않을 당신을 난 이미 알고 있다. 기본 적으로 입력이 1일 때는 10개이다. 0 1 2 3 4 5 6 7 8 9 2일 때 00 01... 09 - 10개 11 12... 19 - 9개 22 23... 29 - 8개 33 34... 39 - 7개 ... 99 - 1개 3일 때 000 001... 009 - 10개 011 012... 019 - 9개 022 023... 029 - 8개 ... 999 뭔가가 보인다면 대단한 것이며, 안 보여도 좋다, 당신의 눈을 뜨이게 하는 것이 나의 역할이다. Q. DP 테이블에 어떻게 의미를 부여해 줘야 할까? A. DP [i] = i번째 숫자가 처음인 상태에서의 최대 경우의 수 위의 설명은 좀 어려울 수 있으니 그림으로 보자 그림.. 2023. 6. 26. [9465] 스티커 - C++ 이 글은 정말 이해가 가지 않는 분들을 위해 쓰인 글입니다. 문제 브루트 포스를 생각할 수 도 있지만 $ O(2^n) $이며 입력의 최대 값이 100'000만 인 것을 보아 불가능하다. Q. 과연 DP로는 풀 수 있을까? A. DP [i] = i번째 까지 스티커를 떼었을 때의 최댓값으로 놓고 푼다면 가능하다. 경우의 수들이 존재하는데 그림으로 보자 i번째 스티커를 떼기 위한 경우의 수들 떼려는 스티커 = 파란색 파란색을 뗴기 위한 전까지의 최댓값 = 주황색 위 그림처럼 4가지 존재하며 이것을 구현해 주면 된다. 코드 #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } in.. 2023. 6. 26. [1915] 가장 큰 정사각형 - C++ 정말 너무 진이 빠진다ㅏㅏ 풀이 정사각형인지 판단하려면 어떻게 해야 할까? 위, 옆, 대각선을 확인하면 된다. 이걸로 이 문제는 해결이라 볼 수 있다. 점화식 $$\large dp [x][y] = min(\{dp [x-1][y], dp [x][y-1], dp [x-1][y-1]\})$$ 전체 코드 #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } int n, m; int arr[1002][1002], dp[1002][1002]; int main(){ init(); cin >> n >> m; //입력 for(int i = 1; i > str; for(int j = 1; j 2023. 6. 23. [9252] LCS2 - C++ 풀이 먼저 내가 썼던 글을 보고 오도록 하자, 그래야 이 문제도 이해할 수 있다! https://juuuuung.tistory.com/126 [9251]LCS - C++ 풀이 LCS - 최장 공통부분 수열 점화식 if(A[i-1] == B[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 비교하는 두 문자가 같다면 dp [i-1][j-1] + 1 비교하는 두 문자가 다르다면 dp[i-1][j], dp [ juuuuung.tistory.com ※위의 글을 읽었다는 가정하에 풀이를 시작하겠다.※ 최대 공통 문자열의 수를 구하는 알고리즘(LCS) cin >> A >> B; for(int i = 1; i A >> B; .. 2023. 6. 23. [9251]LCS - C++ 풀이 LCS - 최장 공통부분 수열 점화식 if(A[i-1] == B[j-1]) dp[i][j] = dp[i-1][j-1] + 1; else dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 비교하는 두 문자가 같다면 dp [i-1][j-1] + 1 비교하는 두 문자가 다르다면 dp[i-1][j], dp [i][j-1] 둘 중 큰 값을 구한다. 그림 설명 더보기 전체 코드 #include using namespace std; void init(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); } string A, B; int dp[1003][1003]; int main(){ init(); cin >> A >> B; for(.. 2023. 6. 23. [2294] 동전 2 - C++ 안 좋은 풀이와 좋은 풀이 두 가지 다 보여 드리겠습니다. 안 좋은 풀이 DP테이블을 이차원 배열로 놓고 풀었다. 행 ( row ) = 내가 가진 동전의 순서 열 ( column ) = 만들 수 있는 임의의 가치 먼저 코드를 보고 그림으로 이해해 보도록 하자 //상수 #define MAX 2E+9 //변수들 int n, k; int coin[101]; int dp[101][10'002]; //입력 cin >> n >> k; for(int i =1; i > coin[i]; //실행 로직 for(int i = 1; i 2023. 6. 22. 이전 1 2 3 4 5 6 다음
