반응형

www.acmicpc.net/problem/9251

 

9251번: LCS

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다. 예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

www.acmicpc.net

같으면 dp[i][j] = dp[i-1][j-1] + 1

다르면 dp[i][j] = max(dp[i][j-1], dp[i-1][j])

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
int dp[1001][1001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    string a, b;
    cin >> a >> b;
 
    int max_length = 0;
    for (int i = 1; i <= a.length(); i++) {
        for (int j = 1; j <= b.length(); j++) {
            if (a[i-1] == b[j-1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
 
            max_length = max(max_length, dp[i][j]);
        }
    }
    cout << max_length;
}
 cs

참고: 2020-1 문제 해결 기법 8주차 2번

8B(LCS) 설명 12161567_박기수.pptx
0.45MB

반응형

'백준 > DP' 카테고리의 다른 글

백준 1520 [복습 필수]  (0) 2021.01.30
백준 2579  (0) 2021.01.28
백준 2565  (0) 2021.01.28
백준 11053  (0) 2021.01.27
백준 12865  (0) 2021.01.26
반응형

www.acmicpc.net/problem/11053

 

11053번: 가장 긴 증가하는 부분 수열

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

DP 배열 2차원으로 하면 반례 생김

4

10 40 20 30

이중 for문 돌면서 기준 값(arr[i])보다 현재 값(arr[j])이 클 경우

증가시킬 지(dp[j] = dp[i] + 1) 말 지(dp[j] 변경 안함) 선택해야 함

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
using namespace std;
int arr[1001];
int dp[1001];
int n;
int max_length = 0;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
    
    for (int i = 1; i <= n; i++) {
        for (int j = i+1; j <= n; j++) {
            // 갱신할 지 말 지 선택
            if (arr[j] > arr[i])
                dp[j] = (dp[i] + 1 > dp[j]) ? dp[i] + 1 : dp[j];
        }
        // 최대 길이 갱신
        max_length = max_length > dp[i] ? max_length : dp[i];
    }
    cout << max_length + 1;
}
 cs
반응형

'백준 > DP' 카테고리의 다른 글

백준 1520 [복습 필수]  (0) 2021.01.30
백준 2579  (0) 2021.01.28
백준 2565  (0) 2021.01.28
백준 9251  (0) 2021.01.27
백준 12865  (0) 2021.01.26
반응형

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

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <algorithm>
using namespace std;
 
int weight[101];
int value[101];
int dp[101][100001];
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
        
    int N, K;
    cin >> N >> K;
    for (int i = 1;i <= N;i++) {
        cin >> weight[i] >> value[i];
    }
 
    // 목표: 무게를 j로 만들기
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= K; j++) {
            // 현재 물건 못 넣음
            if (weight[i] > j)
                dp[i][j] = dp[i - 1][j];
 
            // 현재 물건 넣을 수 있음
            else
                dp[i][j] = max(dp[i - 1][j - weight[i]] + value[i], dp[i-1][j]);
        }
    }
    cout << dp[N][K];
}
 cs

참고: (2020-1) 문제 해결 기법 9주차 2번

반응형

'백준 > DP' 카테고리의 다른 글

백준 1520 [복습 필수]  (0) 2021.01.30
백준 2579  (0) 2021.01.28
백준 2565  (0) 2021.01.28
백준 9251  (0) 2021.01.27
백준 11053  (0) 2021.01.27

+ Recent posts

티스토리툴바