https://www.acmicpc.net/problem/13711

1. 문제설명

1부터 N까지 정수가 모두 한 번씩 등장하는 두 수열 A와 B가 주어졌을 때, 두 수열의 LCS 크기를 구하는 프로그램을 작성하시오.

이 문제는 두 수열의 LCS 크기를 구하는 문제이다.

단 조건으로 두 수열은 모두 1부터 N 사이의 숫자로 이루어져 있음을 준다.

문제에서 주어진 N이 10만이므로 O(N^2) 알고리즘인 LCS 알고리즘을 이용하면

시간초과로 틀린다.

문제에서 주어진 조건 두 수열은 모두 1부터 N 사이의 숫자로 이루어져있음을 활용하면

이 문제를 LIS 알고리즘으로 해결할 수 있다.

LIS는 수열이 주어졌을 때 수열 내 가장 긴 증가하는 부분을 구하는 알고리즘이다.

LIS 알고리즘은 이진탐색을 활용하면 O(NlogN)의 시간복잡도로 문제를 해결할 수 있다.

단 이 문제를 LIS로 해결하는 것을 생각해내기가 조금 어렵다.

예를 들어 두 수열 A, B가 다음과 같다고 가정하자

A : 4 5 6 1 2 3

B : 3 5 1 6 2 4

이 경우에 LCS 알고리즘으로 테이블을 그리면 답은 다음과 같다.

정답은 여러가지가 존재할 수 있지만

LCS의 길이는 3이 나온다.

A와 B는 둘다 1부터 N의 숫자로 이루어져있다.

LCS는 공통 부분 문자열을 구하는 것이므로

A와 B의 숫자를 같은 것 끼리 동일하게 변환을 해도 동일하게 공통 부분 문자열을 구할 수 있다.

좀 더 쉽게 예시를 들면

A : 4 5 6 1 2 3

B : 3 5 1 6 2 4

를

다음과 같이 변환해도 동일한 길이의 공통 부분 문자열을 바꿀 수 있다.

A,B에서 같은 원소를 동일하게 변환했기 때문이다.

위와 아래는 숫자는 다르지만 LCS의 길이를 구하는 데 있어서 동일한 상태라 볼 수 있다.

A : 1 2 3 4 5 6

B : 6 2 4 3 5 1

4->1

5->2

6->3

1->4

2->5

3->6

(A에 존재한 원소를 기준으로 변환한 것이다.)

이렇게 되면 이제 B에서 LIS를 구해주면 

LIS중 하나로

6 2 4 3 5 1

가 나오게 되고 길이는 3이 된다.

즉 1부터 N까지의 범위를 갖는 두 수열의 LCS 길이를 구하기 위해

수열을 변환하고 LIS 길이를 구하면 답을 구할 수 있다.

2. 문제풀이코드

#include <bits/stdc++.h>

#define MX 100003
using namespace std;

int n;
int A[MX], B[MX];
int changeNum[MX];
vector<int> ans;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> A[i];
    }
    for(int i=1; i<=n; i++){
        cin >> B[i];
    }

    //숫자 변환
    for(int i=1; i<=n; i++){
        changeNum[A[i]] = i;
    }
    for(int i=1; i<=n; i++){
        B[i] = changeNum[B[i]];
    }

    //Lis
    for(int i=1; i<=n; i++){
        int idx = lower_bound(ans.begin(), ans.end(), B[i]) - ans.begin();
        if(idx == ans.size()){
            ans.push_back(B[i]);
        }else{
            ans[idx] = B[i];
        }
    }

    cout << ans.size() << '\n';
    return 0;
}

https://www.acmicpc.net/problem/2213

1. 문제설명

서로 인접하지 않은 노드의 집합 중 합이 가장 큰 집합을 찾아야하는 문제이다.

트리를 순회하면서 각 노드마다 선택된 상태와 선택되지 않은 상태를 나누어서 DP로 문제를 해결해야한다.

이 문제에서는 독립집합의 노드를 모두 구해야하는데 이 부분이 어렵다

독립집합의 노드를 구하는 방법은

1. 현재 노드를 택한 경우가 택하지 않은 경우보다 결괏값이 커야한다.

2. 다시 트리를 순회하면서 이전 노드와 인접하지 않은 노드를 구해야한다.

1, 2번을 모두 만족시키는 노드를 골라야 정답이 된다.

2. 문제풀이코드 C++

#include <bits/stdc++.h>

using namespace std;
#define MX 10001

int n, weight[MX], dp[MX][2];
vector<int> adj[MX];
bool vis[MX];
vector<int> Path;

void DFS(int node) {
    vis[node] = 1;
    dp[node][1] = weight[node];

    for (auto nx: adj[node]) {
        if (vis[nx]) continue;

        DFS(nx);
        dp[node][1] += dp[nx][0];
        dp[node][0] += max(dp[nx][0], dp[nx][1]);

    }
}

void tracing(int cur, int pre){
    if(dp[cur][1] > dp[cur][0] && !vis[pre]){
        vis[cur] = 1;
        Path.push_back(cur);
    }

    for(auto nx: adj[cur]){
        if(nx==pre) continue;
        tracing(nx, cur);
    }
}


int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> weight[i];
    }

    int a, b, cnt = 0;

    for (int i = 0; i < n - 1; i++) {
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    DFS(1);
    memset(vis, 0 , sizeof(vis));
    tracing(1,0);
    sort(Path.begin(), Path.end());


    cout << max(dp[1][0], dp[1][1]) << '\n';
    for(auto num: Path){
        cout << num << ' ';
    }

    return 0;
}

https://www.acmicpc.net/problem/16500

1.문제설명

처음 봤을 때 이게 왜 다이나믹 프로그래밍 문제일까 의문이 드는 문제입니다.

어떻게 다이나믹 프로그래밍으로 구현해야할지 고민이 필요합니다.

다이나믹 프로그래밍의 핵심은

주어진 문제를 여러개의 부분 문제로 나누어 풀고

그 결과를 이용해서 주어진 문제를 해결 하는 것입니다.

주어진 S 문자열의 0번 char부터 A 집합의 문자열들과 서로 비교하면서

A의 문자열이 S문자열의 부분과 일치하는지 확인합니다.

이 과정을 반복해서 S문자열의 몇번째 char 까지 만들 수 있는지

bool자료형의 dp 배열에 저장해두면서 그 이후의 부분을 만들 수 있는지 판단하면 됩니다.

그림을 보면 이해하기 쉬울겁니다.

softwarecontest와 software이 7번째 까지 일치하니까

dp[8] = true로 만들어줍니다

7이 아니라 8에 두는 건 인덱스 관리가 7에두는 것보다 다음 숫자인 8에 두는게 쉽기 때문입니다.

그 후 dp배열을 확인하면서 dp[i] == 1 인 지점부터 다시 A의 문자열들과 비교해줍니다

software은 다르니까 넘어가게 되고 contest가 8번부터 일치하므로 다시 dp[15] == 1로 만들어줍니다.

결과상 dp[S.length()] == 1 이라면 문자열 S를 만들 수 있다는 뜻입니다.

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n;
bool dp[101];
string s;
vector<string> A;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> s;
	cin >> n;
	
	for (int i = 0; i < n; i++) {
		string tmp;
		cin >> tmp;
		A.push_back(tmp);
	}

	for (int i = 0; i < s.length(); i++) {
		if (dp[i] || i==0) {
			int st = i;
			
			for (int j = 0; j < n; j++) {
				//부분문자열을 합칠 때 원래 문자열보다 더 길어지는 경우는 제외
				if (st + A[j].length() > s.length()) continue;

				bool flag = true;
				for (int k = 0; k < A[j].length(); k++) {
					if (A[j][k] != s[st + k]) {
						flag = false;
						break;
					}
				}

				if (flag) {
					dp[st + A[j].length()] = 1;
				}
			}
		}
	}

	cout << dp[s.length()];


	return 0;
}

https://www.acmicpc.net/problem/1005

#include <bits/stdc++.h>
using namespace std;

int d[1001];
vector<int> adj[1001];
int degree[1001];
int res[1001];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int t;
    cin >> t;

    for (int T = 0; T < t; T++) {
        int n, k;
        cin >> n >> k;
        memset(degree, 0, sizeof(degree));
        memset(res, 0, sizeof(res));
        memset(d, 0, sizeof(d));
        for (int i = 0; i < 1001; i++) adj[i].clear();


        for (int i = 1; i <= n; i++) {
            cin >> d[i];
        }

        for (int i = 0; i < k; i++) {
            int a, b;
            cin >> a >> b;
            adj[a].push_back(b);
            degree[b]++;
        }
        int w;
        cin >> w;

        queue<int> Q;

        for (int i = 1; i <= n; i++) {
            if (degree[i] == 0) {
                Q.push(i);
                res[i] = d[i];
            }
        }

        while (!Q.empty()) {
            int x = Q.front(); Q.pop();

            for (auto nx : adj[x]) {
                res[nx] = max(res[nx], res[x] + d[nx]);
                if (--degree[nx] == 0) {
                    Q.push(nx);
                }
            }

        }


        cout << res[w] << '\n';



    }


    return 0;
}

https://www.acmicpc.net/problem/14728

1. 문제설명

첫째 줄에는 이번 시험의 단원 개수 N(1 ≤ N ≤ 100)과

시험까지 공부 할 수 있는 총 시간 T(1 ≤ T ≤ 10000)가 공백을 사이에 두고 주어진다.

둘째 줄부터 N 줄에 걸쳐서 각 단원 별 예상 공부 시간 K(1 ≤ K ≤ 1000)와

그 단원 문제의 배점 S(1 ≤ S ≤ 1000)가 공백을 사이에 두고 주어진다.

각 문제는 한번 씩만 풀 수 있고 최대 점수를 구해야 한다.

2. 접근 방법[알고리즘]

각 문제는 한 번만 풀 수 있으므로

다이나믹 테이블 dy에 for문을 뒤부터 돌면서

최댓값을 누적해주면 된다.

for문을 뒤부터 도는 이유는

이 문제는 각 단원 문제를 단 한 번씩 풀 수 있는데

앞에서부터 돌면 계속해서 중복된 값을 더해서 누적하기 때문이다.

중복된 값을 누적하는 걸 피하기 위해 뒤부터 돈다.

만약 각 단원 문제를 여러번 풀 수 있다면

for문을 앞에서 부터 돌아 계속 중복해서 누적해주면 된다.

3. 문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int n, t, dy[10001];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> t;
	for (int i = 0; i < n; i++) {
		int k, s;
		cin >> k >> s;
		for (int j = t; j >= k; j--) {
			dy[j] = max(dy[j], dy[j - k] + s);
		}
	}
	cout << dy[t];

}