Algorithm 공부 #24 - dp(동적 계획법)

 

 

 

Algorithm 공부 #24 - dp

 

 

동적 계획법(Dynamic Programming)

  ● 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결하여 최동적으로 복잡한 문제의 답을 구함

  ● 동적 계획법의 원리와 구현 방식

       1. 큰 문제를 작은 문제로 나누기

       2. 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값이 항상 같아야 함

       3. 모든 작은 문제들은 한 번만 계산해 DP테이블에 저장하여 추후 재사용, 이 방식을 메모이제이션이라 함

       4. 동적 계획법은 톱 - 다운 방식과 바텀 - 업 방식으로 구현 가능

  ● 톱-다운 구현 방식 : 위에서부터 문제를 파악해 내려오는 방식 / 주로 재귀 함수 형태로 구현

                                     코드의 가독성이 좋고 이해하기가 편함

  ● 바텀-업 구현 방식 : 가장 작은 부분 문제부터 문제를 해결하면서 점점 큰 문제로 확장해 나가는 방식

                                     주로 반복문의 형태로 구현

 

 

 

             

백준 1463번 1로 만들기

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

1463번: 1로 만들기

#include<iostream>
using namespace std;
int arr[1000001];
int main() {
    int t;
    cin >> t;
    for (int x = 2; x <= t; x++) {
        arr[x] = arr[x - 1] + 1;
        if (x % 3 == 0)
                arr[x] = min(arr[x], arr[x / 3] + 1);
        if (x % 2 == 0)
            arr[x] = min(arr[x], arr[x / 2] + 1);


    }
    cout << arr[t];
}

 

 

백준 14503번 퇴사

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

14501번: 퇴사

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

vector<int>T;
vector<int>P;
vector<int>D;
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	T.resize(N + 1);
	P.resize(N + 1);
	D.resize(N + 2);

	for (int i = 1; i <= N; i++) {
		cin >> T[i] >> P[i];
	}

	for (int i = N; i > 0; i--) {
		if (i + T[i] > N + 1)
			D[i] = D[i + 1];
		else
			D[i] = max(D[i + 1], D[i + T[i]] + P[i]);
	}
	cout << D[1];
}

 

 

 

백준 2193번 이친수

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

2193번: 이친수

#include <iostream>
using namespace std;
long long int arr[91] = { 0,1,1 };
long long int fibo(int n) {
    if (n == 1 || n == 2)
        return 1;
    else if (arr[n] != 0)
        return arr[n];
    else {
        return arr[n] = fibo(n - 1) + fibo(n - 2);
    }

}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    cout << fibo(n);
}

 

 

 

백준 11726번 2 X n 타일링

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

11726번: 2×n 타일링

#include<iostream>
using namespace std;
int dp[1001] = { 0,1,2 };
int find(int a);
int main() {
	int n;
	cin >> n;
	cout << find(n);
}
int find(int a) {
	if (a == 1 || a == 2)
		return a;
	if (dp[a] != 0)
		return dp[a];
	else
		return dp[a] = (find(a - 2) + find(a - 1)) % 10007;

}

 

 

 

백준 10844번 쉬운 계단 수

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

10844번: 쉬운 계단 수

#include <iostream>

using namespace std;

long long memo[101][10], sol;
int N;

int main() {
	cin >> N;
	
	for (int i = 1; i < 10; i++)
		memo[1][i] = 1;

	for (int i = 2; i <= N; i++) {
		for (int j = 0; j < 10; j++) {
			if (j == 0)
				memo[i][j] += memo[i - 1][j + 1] % 1000000000;
			else if (j == 9)
				memo[i][j] += memo[i - 1][j - 1] % 1000000000;
			else {
				memo[i][j] += memo[i - 1][j - 1] % 1000000000;
				memo[i][j] += memo[i - 1][j + 1] % 1000000000;
			}
		}
	}

	for (int i = 0; i < 10; i++)
		sol += memo[N][i] % 1000000000;

	cout << sol % 1000000000;
}

 

 

 

백준 13398번 연속합 2

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

13398번: 연속합 2

  이런 경우에는 좌측에서 시작하는 최대 합배열과 우측에서 시작하는 최대 합배열을 만든 후

  두 배열을 인덱스마다 더해주면서 최댓값을 구해볼 수 있음

 

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

vector<int>D;
vector<int>L;
vector<int>R;

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;
	D.resize(N);		
	for (int i = 0; i < N; i++)
		cin >> D[i];

	L.resize(N);
	L[0] = D[0];
	int result = L[0];
	for (int i = 1; i < N; i++) {
		L[i] = max(D[i], L[i - 1] + D[i]);
		result = max(result, L[i]);
	}

	R.resize(N);
	R[N - 1] = D[N - 1];
	for (int i =N- 2; i >=0; i--) {
		R[i] = max(D[i], R[i + 1] + D[i]);
	}

	for (int i = 1; i < N-1; i++) {
		int temp = L[i - 1] + R[i + 1];
		result = max(temp, result);
	}
	cout << result;
}

 

 

 

백준 9252번 LCS 2

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

9252번: LCS 2

 

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int N;
int dp[1001][1001];
string A, B;
vector<char>path;
void getText(int r, int c);

int main() {

	cin >> A >> B;
	
	for (int i = 1; i <= A.size(); i++) {
		for (int j = 1; j <= B.size(); 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]);
		}
	}
	cout << dp[A.size()][B.size()] << '\n';
	getText(A.size(), B.size());

	for (int i = path.size() - 1; i >= 0; i--)
		cout << path[i];
}
void getText(int r, int c) {
	if (r == 0 || c == 0)
		return;
	if (A[r - 1] == B[c - 1]) {
		path.push_back(A[r - 1]);
		getText(r - 1, c - 1);
	}
	else {
		if (dp[r - 1][c] > dp[r][c - 1])
			getText(r - 1, c);
		else
			getText(r, c - 1);
	}
}

 

 

 

백준 1915번 가장 큰 정사각형

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

1915번: 가장 큰 정사각형

  정사각형의 경우에는 넓이를 구한다는 개념보다는 한 변의 길이로 접근을 해서 풀 수 있다

#include <iostream>
#include <cmath>
using namespace std;

int N, M;
int D[1001][1001];

int main()
{
    cin >> N >> M;
    long max = 0;
    for (int i = 0; i < N; i++) {
        string mline;
        cin >> mline;
        for (int j = 0; j < M; j++) {
            D[i][j] = mline[j] - '0';
            if (D[i][j] == 1 && j > 0 && i > 0) {
                D[i][j] = min(D[i - 1][j - 1], min(D[i - 1][j], D[i][j - 1])) + D[i][j];
            }
            if (max < D[i][j]) {
                max = D[i][j];
            }
        }
    }
    cout << max* max << "\n";
}

 

 

 

백준 1328번 고층 빌딩

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

1328번: 고층 빌딩

  가장 작은 빌딩의 위치(건물 중간, 좌측 끝, 우측 끝)을 고려해서 접근하기

#include <iostream>
#include <cmath>
using namespace std;

static int N, L,R;
static long mod = 1000000007;
static long D[101][101][101];

int main()
{
    cin >> N >> L >> R;
    D[1][1][1] = 1; // 빌딩이 1개이면 놓은 수 있는 경우의 수는 1개
    for (int i = 2; i <= N; i++) {
        for (int j = 1; j <= L; j++) {
            for (int k = 1; k <= R; k++) {
                D[i][j][k] = (D[i - 1][j][k] * (i - 2) + (D[i - 1][j][k - 1] + D[i - 1][j - 1][k])) % mod;
            }
        }
    }
    cout << D[N][L][R] << "\n";
}

 

 

 

백준 2342번 Dance Dance Revolution

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

2342번: Dance Dance Revolution

   미리 각 위치에서 가는 거리의 최솟값 배열mp를 만들어놓은 후 문제 해결에 접근하기

#include <iostream>
#include <cmath>
#include <climits>
using namespace std;

long dp[100001][5][5];
int mp[5][5] = { { 0, 2, 2, 2, 2 },
                 { 2, 1, 3, 4, 3 },
                 { 2, 3, 1, 3, 4 },
                 { 2, 4, 3, 1, 3 },
                 { 2, 3, 4, 3, 1 } };

int main()
{
    int n = 0, s = 1;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            for (int k = 0; k < 100001; k++)
                dp[k][i][j] = 100001 * 4;
    dp[0][0][0] = 0;

    while (true) {
        cin >> n;
        if (n == 0)
            break;
        for (int i = 0; i < 5; i++) {
            if (n == i)
                continue;
            for (int j = 0; j < 5; j++) {

                dp[s][i][n] = min(dp[s - 1][i][j] + mp[j][n], dp[s][i][n]);
            }
        }
        for (int j = 0; j < 5; j++) {
            if (n == j)
                continue;
            for (int i = 0; i < 5; i++) {

                dp[s][n][j] = min(dp[s - 1][i][j] + mp[i][n], dp[s][n][j]);
            }
        }
        s++;
    }
    s--;
    long minVal = INT_MAX;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            minVal = min(minVal, dp[s][i][j]);
    cout << minVal << "\n";
}

/*

	수열 입력받는 배열 : move
	입력받는 값이 0일 때까지 move를 입력받기

	각 발이 이동하느 ㄴ것에 대한 최솟값 미리 지정 
	mp[start][end] => start부터 end까지 이동할 때 드는 최소 힘

	dp[N][L][R] => N번째 수열만큼 움직였을 때 왼쪽발과 오른쪽
	              발의 위치까지 이동할 때 드는 최소 누적힘

    for문 돌리면서
    왼쪽발이 움직일때와
    오른쪽발이 움직일때를 따로따로 구해주기

    그런다음 최솟값 출력


*/

 

 

 

백준 11049번 행렬 곱셈 순서

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

11049번: 행렬 곱셈 순서

  1~N, 2~N,3~N 등 N을 제외한모든 부분 구역을 1개의 행렬로 만드는데 필요한 최소 연산 횟수를 미리 구한다면?

 

 

#include <iostream>
#include <vector>
#include <cmath>
#include <climits>
using namespace std;

static int N;
static  vector <pair<int, int>> M;
static long D[502][502];
int excute(int s, int e);

int main()
{
    cin >> N;
    M.resize(N + 1);
    for (int i = 0; i < N + 1; i++) {
        for (int j = 0; j < N + 1; j++) {
            D[i][j] = -1;
        }
    }

    for (int i = 1; i <= N; i++) {
        int y, x;
        cin >> y >> x;
        M[i] = make_pair(y, x);
    }
    cout << excute(1, N) << "\n";
}

int excute(int s, int e) {
    int result = INT_MAX;
    if (D[s][e] != -1) // 이미 계산한 적이 있는 부분이면 다시 계산하지 않는다 -> 메모이제이션
        return D[s][e];
    if (s == e) // 행렬 한 개의 곱셈 연산의 수
        return 0;
    if (s + 1 == e) // 행렬 두 개의 곱셈 연산의 수
        return M[s].first * M[s].second * M[e].second;
    for (int i = s; i < e; i++) // 행렬이 3개 이상일 경우 곱셈연산수 -> 점화식 처리
        result = min(result, M[s].first * M[i].second * M[e].second + excute(s, i) + excute(i + 1, e));
    return D[s][e] = result;
}

 

 

 

백준 2098번 외판원 순회

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

2098번: 외판원 순회

 

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;

int W[16][16];
int INF = 1000000 * 16 + 1;
int N;
int D[16][1 << 16];
int tsp(int c, int v);

int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			cin >> W[i][j];
	}
	cout << tsp(0, 1);
}

int tsp(int c, int v) {

	if (v == (1 << N) - 1)
		return W[c][0] == 0 ? INF : W[c][0];

	if (D[c][v] != 0)
		return D[c][v];
	int min_val = INF;
	for (int i = 0; i < N; i++) {
		if ((v & (1 << i)) == 0 && W[c][i] != 0) {
			min_val = min(min_val, tsp(i, (v | (1 << i))) + W[c][i]);
		}

	}
	D[c][v] = min_val;
	return D[c][v];
}

 

 

 

백준 14003번 

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

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

#include<iostream>
using namespace std;

int N, maxlength;
int B[1000001];
int A[1000001];
int D[1000001];
int ans[1000001];
int binarysearch(int l, int r, int now);
int main() {

	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;
	for (int i = 1; i <= N; i++)
		cin >> A[i];

	int index;
	B[++maxlength] = A[1];
	D[1] = 1;

	for (int i = 2; i <= N; i++) {
		if (B[maxlength] < A[i]) {
			B[++maxlength] = A[i];
			D[i] = maxlength;
		}
		else {
			index = binarysearch(1, maxlength, A[i]);
			B[index] = A[i];
			D[i] = index;
		}
	}
	cout << maxlength << '\n';
	index = maxlength;
	int x = B[maxlength] + 1;

	for (int i = N; i >= 1; i--) {
		if (D[i] == index && A[i] < x) {
			ans[index] = A[i];
			x = A[i];
			index--;
		}
	}

	for (int i = 1; i <= maxlength; i++)
		cout << ans[i] << " ";

}
int binarysearch(int l, int r, int now) {
	int mid;

	while (l < r) {
		mid = (l + r) / 2;
		if (B[mid] < now)
			l = mid + 1;
		else
			r = mid;
	}
	return l;
}