컴퓨터하는 kimmessi

https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 해결 알고리즘 배열 양쪽에서 LIS알고리즘을 각각 수행해주고 두 dp 값의 합의 최댓값을 구해주면 된다. DP로도 풀리게 나온 문제 소스 코드 #include using namespace std; int arr[1001], dp[1001][2]; int main(){ int N; cin >> N; for(int i=0;i> arr[i]; dp[0][0] = 1; for(int i=1;i=0;i--){ dp[i]..

https://www.acmicpc.net/problem/13398 13398번: 연속합 2 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 문제 해결 알고리즘 한 칸 넘은 경우와 넘지 않은 경우 두 가지 배열을 다이나믹 프로그래밍을 한다. 소스 코드 #include using namespace std; const int MAX = 100001; int arr[MAX], dp[MAX][2]; int main(){ int n; cin >> n; for(int i=1;i> arr[i]; dp[i][0] = dp[i][1] = -1001; } ..

https://www.acmicpc.net/problem/7579 7579번: 앱 입력은 3줄로 이루어져 있다. 첫 줄에는 정수 N과 M이 공백문자로 구분되어 주어지며, 둘째 줄과 셋째 줄에는 각각 N개의 정수가 공백문자로 구분되어 주어진다. 둘째 줄의 N개의 정수는 현재 활 www.acmicpc.net 문제 해결 알고리즘 dp[i][j]에서 i는 배열의 i번째 원소 까지라는 뜻이고 j는 시간이다. dp[i][j]는 i번째까지의 원소들 중에서 j시간을 썼을 때, 최대 메모리이다. 소스 코드 #include using namespace std; int N, M; int Byte[101], Time[101], dp[101][10001], Sum = 0; int main(){ cin >> N >> M; for..

https://www.acmicpc.net/problem/11062 11062번: 카드 게임 근우와 명우는 재미있는 카드 게임을 하고 있다. N개의 카드가 일렬로 놓여 있다. 각 카드에는 점수가 적혀있다. 근우부터 시작하여 번갈아가면서 턴이 진행되는데 한 턴에는 가장 왼쪽에 있는 www.acmicpc.net 문제 해결 알고리즘 근우는 더 큰 카드를 갖고 점수를 최대로 하고, 명우는 근우의 점수가 최소로 되는 방향으로 플레이 해야한다. 소스 코드 #include using namespace std; int arr[1001], dp[1001][1001]; int cardgame(int left, int right, int turn){ if(left > right) return 0; if(dp[left][ri..

https://www.acmicpc.net/problem/5582 5582번: 공통 부분 문자열 두 문자열이 주어졌을 때, 두 문자열에 모두 포함된 가장 긴 공통 부분 문자열을 찾는 프로그램을 작성하시오. 어떤 문자열 s의 부분 문자열 t란, s에 t가 연속으로 나타나는 것을 말한다. 예를 들 www.acmicpc.net 문제 해결 알고리즘 간단한 문자열 + DP 문제 문자열을 탐색할 때, 두 문자가 같으면 그 두개의 전에 해당하는 배열에서 +1한 값을 입력한다. 거기서 최댓값을 구해준다. 소스 코드 #include using namespace std; int dp[4001][4001], result = 0; int main(){ string str1, str2; cin >> str1 >> str2; s..

https://www.acmicpc.net/problem/1915 1915번: 가장 큰 정사각형 첫째 줄에 n, m(1 ≤ n, m ≤ 1,000)이 주어진다. 다음 n개의 줄에는 m개의 숫자로 배열이 주어진다. www.acmicpc.net 문제 해결 알고리즘 다이나믹 프로그래밍으로 주변에 있는 사각형들 중 가장 작은 크기의 정사각형 크기에서 + 1 해준다. 갱신해줄 때마다 최댓값도 갱신해준다. 소스 코드 #include using namespace std; int n, m, result = 0; int dp[1001][1001]; void find_max_square(){ for(int k=1;k> m; for(int i=0;i> str; for(int j=0;j

https://www.acmicpc.net/problem/1256 1256번: 사전 동호와 규완이는 212호에서 문자열에 대해 공부하고 있다. 김진영 조교는 동호와 규완이에게 특별 과제를 주었다. 특별 과제는 특별한 문자열로 이루어 진 사전을 만드는 것이다. 사전에 수록되 www.acmicpc.net 문제 해결 알고리즘 다이나믹 프로그래밍으로 푸는 문제 next_permutation으로 일일히 순서대로 구하면 K가 최대 10억이기 때문에 시간초과를 받는다. a문자의 개수와, z문자의 개수로 이중배열을 선언해준다. dp[a문자의 개수][z문자의 개수] = dp[a문자의 개수 - 1][z문자의 개수] + dp[a문자의 개수][z문자의 개수-1] 위의 식대로 dp배열을 만들어주고 K가 a가 하나 적은 dp값보..

https://www.acmicpc.net/problem/5569 5569번: 출근 경로 상근이가 사는 도시는 남북 방향으로 도로가 w개, 동서 방향으로 도로가 h개 있다. 남북 방향 도로는 서쪽부터 순서대로 번호가 1, 2, ..., w로 매겨져 있다. 또, 동서 방향 도로는 남쪽부터 순서대 www.acmicpc.net 문제 해결 알고리즘 방향 전환이 가능한지, 방향이 아래인지 오른쪽인지 이 네가지로 나눠서 다이나믹 프로그래밍을 진행주어야한다. 소스 코드 #include using namespace std; const int mod = 100000; int arr[101][101][2][2]; // 행, 열, 방향 전환 가능 여부, 방향 아래 0 오른 1 int main(){ int w, h; cin ..

https://www.acmicpc.net/problem/5557 5557번: 1학년 상근이가 1학년 때, 덧셈, 뺄셈을 매우 좋아했다. 상근이는 숫자가 줄 지어있는 것을 보기만 하면, 마지막 두 숫자 사이에 '='을 넣고, 나머지 숫자 사이에는 '+' 또는 '-'를 넣어 등식을 만들며 놀 www.acmicpc.net 문제 해결 알고리즘 다이나믹 프로그래밍을 활용해서 풀어주는 문제 배열에 0부터 20까지 두고 첫번 째 수부터 그 안에 속하는 등식이면 배열에서 그 해당하는 값의 개수를 더해주면서 동적계획을 해준다. 소스 코드 #include using namespace std; int N; long long arr[103], dp[21][103]; long long result = 0; int main()..

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 문제 해결 알고리즘 전형적인 위상 정렬 알고리즘을 활용한 문제이다. 작업 시간이 있는 것이 좀 다른데, 이것은 계속해서 결괏값을 먼저 해야할 작업이 걸린 시간 + 현재 해야할 작업이 걸리는 시간과 계속 비교해주면서 더 큰 쪽을 결괏값에 대입해준다. https://kimmessi.tistory.com/194 [위상 정렬] BOJ 2056 작업 https://www.acmicpc.net/prob..