순열

08 May 2021

Reading time ~5 minutes

다이나믹 프로그래밍

DP에서 가장 중요한 것은 점화식의 기준이 되는 변수를 잡는 것!
메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
이미 계산된 결과(작은 문제)는 별도의 메모리 영역에 저장하여 다시 계산하지 않도록 함(메모이제이션)
- 값을 기록한다는 점에서 캐싱이라고도 함
다이나믹 프로그래밍 구현은 탑다운과 보텀업으로 구성
- 탑다운(메모이제이션) 방식은 하향식, 보텀업 방식은 상향식
- 다이나믹 프로그래밍의 전형적인 형태는 보텀업 방식
- 메모이제이션은 다이나믹 프로그래밍에 국한된 개념은 아님
결과 저장용 리스트는 DP 테이블이라 불림
다이나믹 프로그래밍과 분할 정복(퀵 정렬)의 차이점 : 부분 문제의 중복 여부
- DP에서는 각 부분 문제들이 서로 영향을 미치며 부분 문제가 중복됨
  - 아래 피보나치 수열의 경우, 부분 원소들이 계속 중복됨
피보나치 수열 예제
- 시간복잡도는 O(N)
- 단순히 재귀로 풀면 O(2^N)

#include <iostream>
using namespace std;

long long d[100];

int main(){
    d[1] = 1;
    d[2] = 1;
    int n = 50;

    for(int i=3; i<=n; i++){
        d[i] = d[i-1] + d[i-2];
    }
    cout << d[n] <<'\n'; 
}

조합 구현

조합을 DP로 구현하는 방법
- nCr = n-1Cr-1 + n-1Cr 성질 이용!

#include <iostream>
using namespace std;
int t, a, b, dp[31][31];
int cbn(int n, int r) {
	if(n == r || r == 0) return 1;
	if(dp[n][r]) return dp[n][r];
	return dp[n][r] = cbn(n - 1, r - 1) + cbn(n - 1, r);
}
int main() {
	cin >> t;
	while(t--) {
		cin >> a >> b;
		cout << cbn(b, a) << endl;
	}
}

다이나믹 프로그래밍 문제에 접근하는 방법

그리디, 구현, 완전 탐색 등의 아이디어로 문제를 해결할 수 있는지 검토
- 시간복잡도 등의 이유로 풀이 방법이 떠오르지 않으면, 다이나믹 프로그래밍 고려
일단 재귀 함수로 비효율적인 완전 탐색 프로그램(탑 다운)을 작성한 뒤 작은 문제에서 구한 답이 큰 문제에서 그대로 사용될 수 있으면, 코드를 개선함

1로 만들기 (백준)

DFS로 풀수 있을거 같지만, 시간초과 (1000 만 넘어가도 완전탐색은 시간 너무 오래 걸림)
DFS에서 값 비교하는 건, int 범위중 가장 큰걸로 놓고 비교하는거 연습하기!

#include<iostream>
#include<vector>

using namespace std;
int answer;
void Solution(int n, int c) {
	if (n == 1) {
		if (answer > c)answer = c;
	}
	else {
		if (n % 3 == 0)
			Solution(n / 3, c + 1);
		if (n % 2 == 0)
			Solution(n / 2, c + 1);
		Solution(n - 1, c + 1);
	}
}
int main() {
	int N;
	answer = 987654321;
	cin >> N;
	Solution(N, 0);
	cout << answer << "\n";

	return 0;
}

그럼, 완전탐색은 안되니 DP로 옮겨가자
- 테이블 정의 => dp[i] = i 를 1로 만들기 위해 필요한 연산 사용 횟수의 최솟값
- 점화식 찾기
  - D[12] = ?
    - 3으로 나누거나(D[12] = D[4] + 1)
    - 2로 나누거나(D[12] = D[6] + 1)
    - 1을 빼거나(D[12] = D[11] + 1)
  - 따라서, D[12] = min(D[4] + 1, D[6] + 1, D[11] + 1)
  - D[k] = ?
    - min(D[k/3] + 1, D[k/2] + 1, D[k-1] + 1)
- 초기값 정의하기
  - 매번 점화식이 돌아갈 수 있게 하기 위한 초기값이 어디까지인지를 잘 적용해야 하는데, 이 문제에서는 D[1]만 정해주면 됨
  - D[1] = 0

#include<iostream>
#include<vector>

using namespace std;
int answer;
int d[1000001];


int main() {
	int n;
    d[1] = 0;
    scanf("%d", &n);

    for(int i=2; i<=n; i++){
        d[i] = d[i-1] + 1;
        if(i%2 == 0){
            d[i] = min(d[i], d[i/2] + 1);
        }
        if(i % 3 == 0){
            d[i] = min(d[i], d[i/3] + 1);
        }
    }
    printf("%d", d[n]);


}

퇴사 (백준) - 뼈대문제

dp[i] : i일째의 최대금액
i일을 포함하는 경우
- 그 다음 일을 정할 수 있는 날(next1) : i + day[i]
i일을 포함하지 않는 경우 ( 오늘 스케줄을 안하고 내일 스케줄을 할떄 더 이득일 경우)
- 그 다음 일을 정할 수 있는 날 (next2) : i + 1
구하는 값은 dp[n+1]이 됨 (마0지막 날부터 1일 하면 최대 n+1 까지 인덱스가 가능함)

#include <vector>
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>

#define MAX_SIZE 51

using namespace std;

int day[MAX_SIZE];
int cost[MAX_SIZE];
int dp[MAX_SIZE];

int main(){
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n i++){
        scanf("%d %d", &day[i], &cost[i]);
    }

    int ret = 0;

    for(int i=1 i<=n; i++){
        int next1 = i + day[i];
        int next2 = i + 1;

        if(next1 <= n+1){
            dp[next1] = max(dp[next1], dp[i] + cost[i]);
        }
        if(next2 <= n+1){
            dp[next2] = max(dp[next2], dp[i]);
        }
       
        ret = max(max(ret, dp[next1]), dp[next2]);
    }

    printf("%d\n" ,ret);
}

다른 풀이 (N이 작으므로 완전탐색 활용)

#include <vector>
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <queue>

#define MAX_SIZE 51s

using namespace std;

int day[MAX_SIZE];
int cost[MAX_SIZE];

int max_value

void dfs(int d, int sum){
    if(d == n + 1){
        max_value = max(max_value, sum);
        return;
    }
    if(d + day[d] <= n + 1){
        dfs(d + day[d], sum + cost[d]);
    }
    if(d + 1 <= n + 1){
        dfs(d + 1, sum);
    }
}

int main(){
    int n;
    scanf("%d", &n);
    for(int i=1; i<=n i++){
        scanf("%d %d", &day[i], &cost[i]);
    }

    dfs(1, 0);


    printf("%d\n" ,max_value);
}

동전 1 (백준)

0원에서 3원짜리를 하나를 사용해서 3원을 만드는 상황을 확인해보자.
- 이런 경우에는 DP[3] += DP[0]이 된다. 왜 ?? 0원을 만들 수 있는 경우의 수에서 3원 하나를 사용하는 경우이기 때문이다.
- ‘2’원을 사용하게 되는 경우는 ?? DP[3] += DP[1] 이 된다. 왜 ?? 이 상황은 2원을 사용해서 3원을 맞추려고 한다. 그럼 ? 기존에 이미 1원을 가지고 있어야 하기 때문이다.
- 마지막으로 1원을 이용해서 만드는 방법을 보자. 이 경우에는 DP[3] += DP[2]가 된다. 왜 ? 현재 ‘1’원을 이용해서 3원을 맞추려면, 기존에 2원이 있어야 하고, 이 2원을 만드는 방법은 DP[2]에 저장되어 있기 때문이다.
현재 X원인 동전을 가지고 있다면, 이 동전을 이용해서 Y원을 만들고 싶다
- dp[y] = dp[y] + dp[y - x]

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

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> arr(n);
	vector<int> dp(k+1);
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	dp[0] = 1;	// 아무 동전도 선택하지 않은 경우
	for (int i = 0; i < n; i++) { //각 동전에 대해
		for (int j = arr[i]; j <= k; j++) { 
			dp[j] +=dp[j - arr[i]];
		}
	}

	cout<<dp[k]<<endl;
	return 0;
}

Algorithm