백준/동적프로그래밍15 백준 c++ 11053 "가장 긴 증가하는 부분 수열" -PlusUltraCode- https://www.acmicpc.net/problem/11053 [필자 사고] 처음 문제를 보고 있을 때는 완전탐색으로 문제를 풀어 나갔다. 다만 문제가 틀리고 채점 계시판에 있는 반례를 본 후 완전탐색이 아닌 Dp로 풀기로 방향을 바꿨다. 기존 알고 있던 dp는 처음부터 차례대로 증가하는 형태로 쌓아가는 느낌이 많았다. 이 문제는 증가는 하지만 index가 작은 값들을 수시로 검사하는 형태로 쌓아가는 방식이다. dp[i] = max(dp[i], dp[k]+1) 단 i>k 이 사고만 할 수 있으면 문제를 쉽게 풀 수 있다. 다른 후기들을 찾아보니 이 문제는 LIS의 기본 문제라한다. 기본 개념이 들어간 문제이니 기억해야 겠다. [소스 코드]#include#include #include #.. 2024. 5. 1. 백준 c++ 1912 "연속합" -PlusUltraCode- https://www.acmicpc.net/problem/1912 [필자 사고]연속합 문제이다. 시간복잡도를 측정하기 위해 문제에서 주어진 N의 크기를 본 결과 N=100000이다. 즉 시간복잡도 n^2 인 형태로 코드를 짜면 안된다. 잠시 고민해본 결과 다이나믹 프로그래밍이 떠올라 해당 코드를 작성했다. 필자는 Dynamic 이라는 배열을 만들었고 Dynamic의 들어가는 숫자는 arr의 숫자들 중 순서대로 합해서 최대가 되는 숫자들만 넣는 형식으로 정의했다. [소스 코드] #include#include using namespace std;int N;vector arr;vector Dynamic;int maxNum = -111111;void Input() { cin >> N; a.. 2024. 4. 29. 백준 9251 c++ -[PlusUltraCode] [필자 사고] 문제를 해석해보면 LCS 알고리즘을 사용해야 한다. LCS 알고리즘은 공부해두면 쉽게 풀 수 있는 문제이다. 1. 각 글자들을 비교한다. 2. 만약 각 단어가 다르다면 왼쪽 or 위쪽 중 큰 값을 저장한다.. 3. 만약 각 단어가 같다면 왼쪽 대각선의 값에서 +1을 더한다 [소스 코드] #include #include #include #include using namespace std; string str1, str2; int Arr[1001][1001] = { 0 }; void Input() { cin >> str1 >> str2; for (int i = 0; i < str1.size(); i++) { for (int k = 0; k < str2.size(); k++) { if (str1.. 2024. 2. 22. 백준 1328 c++ -고층 빌딩 [필자 생각] 1차원과 2차원 배열로만 동적프로그래밍을 생각해왔다. 아무리 생각해도 해답이 나오지 않아 자료들을 찾게 되었다. [깨달음] 이 문제는 처음으로 내게 3차원 동적프로그래밍의 사고를 열어준 문제였다. [문제 풀이] D[N][L][R] 의 배열을 만들어 준다. N의 갯수가 증가함에 따라 가장 작은 빌딩을 어디에 놓는지가 핵심인 문제이다. 1. 가장 작은 빌딩을 맨 왼쪽에 넣는다. => D[N-1][L-1][R] 2. 가장 작은 빌딩을 맨 오른쪽에 넣는다 => D[N-1][L][R-1] 3. 가장 작은 빌딩을 중간에 넣는다ㅏ. => D[N-1][L][R]*(N-2) 3번에서 N-2번 곱한 이유는 왼쪽과 오른쪽을 제외하면 나머지 넣을 수 있는 경우의 수가 N-2번이기 때문에 곱해줘야 된다. [소스코.. 2024. 2. 15. 이전 1 2 3 4 다음