dynamic programming5 [C/C++] 백준 9252번 https://www.acmicpc.net/problem/9252 안녕하세요오늘 풀어볼 문제는 백준 9252번, 골드 4번 문제입니다. LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제로 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 프로그램을 구한다. 조건첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다. 아이디어DP 배열 정의:dp[i][j]: A[1…i]A[1 \ldots i]A[1…i]와 B[1…j]B[1 \ldots j]B[1…j]의 LCS 길이.점화식:A[i]==B[j]일 경우:dp[i][j]=dp[i−1][j−1]+1A[i]!=B[j]일 경우dp[i][j.. 2025. 1. 12. [C/C++] 백준 14002번 https://www.acmicpc.net/problem/14002안녕하신지오늘은 백준 14002번, 골드4번 문제를 풀고자한다. 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 구해보자.어제와 엊그제 비슷한 유형의 문제를 풀었는데 두 문제의 경우, 가장 긴 증가하는 부분 수열의 길이와 합을 구하는 문제였다면, 이번에는 길이와 그 수열을 구하는 문제이다. 조건첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000) 아이디어추적 배열 사용:prev[i]: i번째 원소의 이전 원소가 배열의 몇 번째 원소인지 저장.prev 배열을 통해 가장 긴 증가하는 부분 수열을 역추적하여 수열을 복원... 2025. 1. 11. [C/C++] 백준 11055번 https://www.acmicpc.net/problem/11055 오늘 풀어볼 문제는 백준 11055번, 실버2 문제이다.수열 A가 주어졌을 때, 그 수열의 증가하는 부분 수열 중에서 합이 가장 큰 것을 구하는 프로그램을 만들어보자. 조건첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)첫째 줄에 수열 A의 합이 가장 큰 증가하는 부분 수열의 합을 출력한다. 아이디어점화식dp[i]: i번째 수를 마지막으로 포함하는 가장 긴 증가하는 부분 수열의 길이.점화식dp[i]=max(dp[i], dp[j]+arr[i])초기값dp[i]=arr[i]결과dp 배열의 최댓값이 정답 코드#include #include.. 2025. 1. 10. [C/C++] 백준 11053번 https://www.acmicpc.net/problem/11053 오늘은 백준 11053번, 실버2 문제를 풀어보려한다.수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 구현해보자. 가장 긴 증가하는 부분 수열(LIS, Longest Increasing Subsequence)은 DP를 사용해서 해결할 수 있다. 조건배열에서 부분 수열 중, 항목이 증가하는 수열의 최대 길이를 찾는다.점화식 정의dp[i]: i번째 수를 마지막으로 포함하는 가장 긴 증가하는 부분 수열의 길이.점화식:dp[i]=max(dp[j]+1)(0≤jiandarr[j]arr[i]) j는 i 이전의 인덱스 중 arr[j]를 만족하는 값만 고려.dp[i]는 dp[j]+1의 최댓값.초기값dp[i]=1: 각 원소는 스.. 2025. 1. 9. [C/C++] 백준 1912번 https://www.acmicpc.net/problem/1912 굿모닝.오늘 풀어볼 문제는 백준 1912번, 실버2 문제이다. n개의 정수로 이루어진 임의의 수열이 주어질 때, 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 프로그램을 만든다. 조건첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다.수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. 아이디어dp[i]: i번째 수를 포함하는 연속된 부분합의 최댓값.dp[1]=num[1]: 첫 번째 수는 그대로 선택.점화식dp[i]=max(dp[i−1]+num[i],num[i]) 코드#include #include #include us.. 2025. 1. 8. 이전 1 다음
