백준 (14) 썸네일형 리스트형 백준 9251번 LCS C/C++ 풀이 https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net DP 문제, 그 중에서도 2차 배열을 이용하면 쉽게 풀 수 있다. 각각의 string 글자 수를 가진 2차 배열을 만들어서 각각의 cell을 채워나간다. 각각의 글자가 같지 않을 때는 왼쪽이나 위(i나 j가 같은) 중에서 크기가 큰 열을 선택하고, 같은 상황이 온다면 왼쪽 위에서 1을 더한 뒤 왼쪽이나 위 열과 크기를 비교해서 합친다. string 입출.. 백준 12865번 평범한 배낭 C/C++ 풀이 https://www.acmicpc.net/problem/12865 12865번: 평범한 배낭 첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000) www.acmicpc.net 가장 고전적인 DP 문제 예전에는 DP를 점화식으로만 이해했었는데, 2차원 배열로 이해하고 나니 더 깊은 이해를 할 수 있게 되는 것 같다. https://gsmesie692.tistory.com/113 Dynamic Programming: 배낭 채우기 문제 (Knapsack Problem) 도둑이 보석가게에 배낭을 메고 침입했다... 백준 15486번 퇴사2 C/C++ 풀이 https://www.acmicpc.net/problem/15486 15486번: 퇴사 2 첫째 줄에 N (1 ≤ N ≤ 1,500,000)이 주어진다. 둘째 줄부터 N개의 줄에 Ti와 Pi가 공백으로 구분되어서 주어지며, 1일부터 N일까지 순서대로 주어진다. (1 ≤ Ti ≤ 50, 1 ≤ Pi ≤ 1,000) www.acmicpc.net 이 역시도 DP 문제 1부터 n까지 순회하면서 현재까지의 최댓값을 저장해둔다. dp[n]은 n일까지 일했을 때 얻을 수 있는 최대 수익으로 i번째 날에 들렸을 때, 현재까지 얻을 수 있는 최댓값과 그 날에 저장된 값을 비교하여 갱신하여 주고, i번째 날에 일했을 때 얻을 수 있는 최대 수익을 i번째 일했을 때 수익을 얻는 날(i + 해당 일의 소요 날짜) dp 배열에.. 백준 2228번 구간 나누기 C/C++ 풀이 https://www.acmicpc.net/problem/2228 2228번: 구간 나누기 N(1≤N≤100)개의 수로 이루어진 1차원 배열이 있다. 이 배열에서 M(1≤M≤⌈(N/2)⌉)개의 구간을 선택해서, 구간에 속한 수들의 총 합이 최대가 되도록 하려 한다. 단, 다음의 조건들이 만족되어야 �� www.acmicpc.net 이 역시 DP로 푸는 문제. 점화식을 dp[n][m](n개를 m개의 구간으로 나눴을 때의 최댓값) = dp[n-1][m](n을 포함하지 않고 m개를 선택했을 때의 최대값) 이거나 sum(i부터 n까지의 합) + dp[i - 2](하나의 공백이 있어야하기 때문에 i-2부터)[m-1](구간 하나 줄어들었으니 m-1로)' 으로 나타낼 수 있다. #include #include usi.. 백준 5535번 패셔니스타 C/C++ 풀이 https://www.acmicpc.net/problem/5535 DP 문제 전의 선택한 옷의 화려함 정도와 현재의 날짜를 요소로 두고 동적계획법을 사용하였다. 어렵지 않기 때문에 나머지는 코드로 설명 #include #include #include #include using namespace std; #define MAX 201 FILE* in = fopen("input.txt", "r"); int n, d; int tmp[MAX]; int min_tmp[MAX]; int max_tmp[MAX]; int cool[MAX]; int cache[101][MAX]; //재귀를 사용한 DP int dp(int coolness, int day) { //d 날짜가 됐다면 return if (day == d) re.. 백준 5557번 1학년 C/C++ 풀이 https://www.acmicpc.net/problem/5557 DP 문제. 해당 idx에 어떤 sum을 가지고 있는가를 저장해나가며 함수를 진행시켜나간다. 계산 중간에 0~20을 넘어가는 경우 더이상 진행하지 않기 때문에 이를 저장하지 않는다. #include #include #define MAX 101 FILE* in = fopen("input.txt", "r"); int n; int array[MAX]; long long int cnt; long long int cache[MAX][21]; int dst; //재귀로 구현한 dp long long int dp(int idx, int sum) { //계산 값이 범위를 벗어나는 경우 return if (sum 20) return.. 백준 1633번 최고의 팀 만들기 C/C++ 풀이 https://www.acmicpc.net/problem/1633 1633번: 최고의 팀 만들기 문제 꿍 협회는 매년 세계체스대회에 나갈 팀을 만들고 있다. 팀은 흑으로 플레이하는 15명과 백으로 플레이하는 15명, 총 30명으로 이루어진다. 꿍 협회는 가능한 최고의 팀을 만들려고 하는데 �� www.acmicpc.net 전형적인 동적계획법 문제. 재귀함수와 메모이제이션을 이용해서 문제를 풀었다. #include #include #include using namespace std; FILE* in = fopen("input.txt", "r"); int white[1001]; int black[1001]; int cache[1001][16][16]; int n; int dp(int w, int b, int.. 백준 14502번 연구소 C/C++ 풀이 acmicpc.net/problem/14502 14502번: 연구소 인체에 치명적인 바이러스를 연구하던 연구소에서 바이러스가 유출되었다. 다행히 바이러스는 아직 퍼지지 않았고, 바이러스의 확산을 막기 위해서 연구소에 벽을 세우려고 한다. 연구소는 크� www.acmicpc.net 문제에서 사용하는 범위의 크기가 크지 않아서 전체 map 안에서 벽과 바이러스가 없는 부분 재귀함수를 이용해서 3가지를 선택하고 그에 따라 안전 범위가 몇 개 생기는지를 구했다. #include #include using namespace std; FILE* in = stdin; #define MAX 8 int n, m; int map[MAX][MAX]; int cnt; int max = 0; int path[3]; bool c.. 이전 1 2 다음