https://www.acmicpc.net/problem/9251 9251번: LCS LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다. www.acmicpc.net 풀이 문제를 풀기 위해서는 주어진 2개의 문자열 중 하나를 기준으로 잡아 생각해야 한다. 여기서는 그 문자열을 기준문자열, 그렇지 않은 문자열을 비교문자열이라고 하겠다. ACAYKP가 여기서는 기준문자열, CAPCAK가 비교문자열이다. 기준문자열의 길이만큼 dp 배열을 만든다. 즉 배열 칸이 의미하는 것은 각 번째의 문자를 말한다. 문자열 A C A Y..
Algorithm/DP
https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 이 문제를 보고 가장 먼저 생각난 것은 바이토닉 수열의 중앙점이다 S1 ... SN-1 > SN에서 Sk를 말하는 것이다. Sk를 어디로 S1~SN 중 어디로 할지 정하고, S1~SK에서 나오는 증가하는 부분수열의 개수+ SK~SN에서 나오는 감소하는 부분수열의 개수를 K 값에 따라 비교해 최댓값을 출력하면 된다. 2023.06.11 - [algorithm/dp] - [백준] 11053번:..
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 풀이 소위 냅색문제라고 불리는 문제이다. 2차원 배열을 사용해서 풀면 된다. 열은 무게를, 행은 몇 번째 물건까지 넣었는지 표시하고, 테이블의 각 자리에 가치를 저장한다. 냅색문제에서 물건을 대할때 선택지는 2가지다. 물건을 넣던가 혹은 그렇지 않던가. 1. 그래서 물건을 넣지 않을 거면 이전 행에서 그대로 할당받고 2. 물건을 넣..
https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 결국 전깃줄끼리 꼬이지 않게 하려면 어떻게 하야할까? 전깃줄들을 A에서 B로 간다는 관점으로 바라보자. A에서 시작하는 점을 1~10까지 오름차순으로 정렬할 때. 그 줄에 대응하는 B 역시 오름차순으로 정렬되면 된다. 문제에서는 (A,B) 형태로 입력을 받는다. 그렇다면 A와 B를 pair형태로 저장하고, A를 기준으로 정렬한다. 그리고 A를 기준으로 정렬한 페어쌍에서 B부분만 추출해, 몇 개가 빠..
풀이 포도주를 먹어서 얻는 값은 모두 양수이다. 즉, 무조건 먹을 수 있으면 먹는게 이득이다. 입력값들을 arr[]에 저장한다. 그리고 동적계획법을 위한 dp[]를 만든다. dp[n]은 n번째 잔을 마지막으로 먹었을 때 가지는 최대의 점수 값이다. 하지만 n-2,n-1번째 잔까지 모두 먹은 경우는 n번째 잔을 먹을 수 없다. 즉 이번에 먹는 잔이 1.(n-2번째 잔은 먹지 않은 상태) AND (n-1번째 잔은 먹은 상태) 거나 2.(n-2번째 잔은 먹은 상태) AND (n-1번째 잔은 먹지 않은 상태) 여야 한다. 둘다 먹지 않은 상태는 위에서 쓴데로, 무조건 먹는게 이득이라고 했으니 생각하지 않는다. 즉 1번 식은 n-3번째까지 먹었을 경우의 최댓값에 n-1번째 잔과 n번째 잔을 더하고 2번 식은 n-..
풀이 숫자가 들어있는 직사각형 표가 주어진다. 그리고 주어진 표에서 직사각형모양으로 수를 선택할 때 그 직사각형 안 수들의 합을 구하라는 문제다. 반복문을 통해 그때그때 답을 구하게 된다면 큰 수가 주어졌을 때 시간초과가 날 것이다. 최대로 계산하는 경우는 1024*100,000으로 대략 10억 번이다. 그런데 문제 제한 시간은 1초로 초당 1억 번 정도 계산한다고 치면 시간초과가 나는 것이다. 그래서 우리는 이 문제를 동적계획법을 이용한 합으로 계산할 것이다. sum 배열에는 0,0 부터 그 위치를 꼭짓점으로 하는 직사각형을 그리고 그 합을 저장한다. 가령 sum[1][3]에는 arr [0][0], arr [0][1], arr [0][2], arr [0][3], arr [1][0], arr [1][1]..
풀이 수열에서 n번째 중 몇 번째에 오는지 표시하는 열과, 1~9까지의 수를 나타내는 열로 2차원 배열 arr을 만든다. 그리고 배열에는 그 번째가 그 숫자로 끝날 때의 값을 넣는다. 가령 arr [2][3] 은 2번째 자리가 3으로 끝날 때의 계단 수이다. 계단 수의 규칙에 따라, 0으로 끝났다면 앞 수는 1이어야만 계단수이다. 1로 끝났다면 앞 수는 0이나 2여야만 계단수이다. 2로 끝났다면 이전수는 1이나 3이어야만 계단수이다. 3으로 끝났다면 이전수는 2나 4여야만 계단수이다. . . . 8로 끝났다면 이전수는 7이나 9이어야만 계단수이다. 9로 끝났다면 이전수는 8이어야만 계단수이다. 즉, arr [m][n]=arr [m-1][n+1]+arr [m-1][n-1]이다. (단, n이 0이면 arr ..
풀이 피라미드 형태의 문제 그대로 배열을 만들면 된다. n에는 높이, m에는 수평개수가 들어가는 arr [n][m] 배열을 만든다. n에는 높이, m에는 수평개수가 들어가는 dp[n][m] 배열도 만든다. dp [0][0]에 점화식을 위한 처음값 arr [0][0]을 넣어준다. 그리고 dp[n][m]에 dp [n-1][m]과 dp [n-1][m-1] 중 큰 값을 고르고 arr [n][m]을 더해 할당한다. 이때 인덱스가 최소 최대 범위를 넘지 않도록 조심한다. 그리고 마지막 dp[n]에서 배열들 중 최댓값을 출력한다. 해답 코드 #include #include #define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) using namespace s..
