TIL #7 다이나믹 프로그래밍 (1)

노력하는 배짱이·2020년 8월 12일
JavaTIL알고리즘
0

1. 다이나믹 프로그래밍(Dynamic programming)

다이나믹 프로그래밍이란
단순하게 큰 문제를 작은 문제로 나눠서 푸는 알고리즘이라고 생각하면 된다.
다른 말로 동적 계획법이라고도 한다.

DP(=Dynamic Programming)는 두 가지 속성을 만족해야 문제를 풀 수 있다.
1. Overlapping Subproblem : 겹치는 부분 문제
2. Optimal Substructure : 최적 부분구조

피보나치 수 를 예를 들어보자.
F0=0F_0=0, F1=1F_1=1, Fn=Fn−1+Fn−2 (n≥2)F_n=F_{n-1}+F_{n-2} \ (n\geq2) 라고 주어졌을 때
FnF_n이 큰 문제에 해당하고 Fn−1F_{n-1}과
Fn−2F_{n-2}는 작은 문제에 해당한다.

Optimal Substructure를 만족하면 문제의 크기에 상관없이 어떤 한 문제의 정답은 일정하다.
즉,
4번째 피보나치 수를 구하면서 구한 2번째 피보나치 수와 3번재 피보나치 수를 구하면서 구한 2번째 피보나치 수는 항상 같다.

DP에서는 각 문제는 한 번만 풀어야 하고, Optimal Substructure를 만족하기 때문에 같은 문제는 구할 때마다 정답이 같다.
따라서 앞서 정답을 구했으면 배열과 같은 곳에 저장하여 이후에 바로 사용할 수 있게 하는것이다.

public int fibonacci(int n) {
	if (n <= 1) {
		return n;
	} else {
		return fibonacci(n - 1) + fibonacci(n - 2);
	}
}

기본적인 피보나치 수를 구하는 함수이고 시간복잡도는 O(2N)O(2^N)이다.

예를 들어 위 사진과 같이 fib(5)를 보자.
이 상황에서 fib(3), fib(2)는 여러 번 구하게 되는데, 이를 어떤 배열에 저장을 하게되면
한번만 구한 값을 가지고 다른 곳에서 바로 찾아 넣기만 하면 된다.

int[] mem = new int[100];
public int fibonacci(int n) {
	if (n <= 1) {
		return n;
	} else {
		if (mem[n] > 0) {
			return mem[n];
		}
		mem[n] = fibonacci(n - 1) + fibonacci(n - 2);
		return mem[n];
	}
}

이와 같은 형태로 구현할 수 있고 시간복잡도는 O(N)O(N)이 된다.
배열은 처음 0으로 초기화를 하고 이후 0이 아닌 수가 들어왔다면 이는 이전 과정에서 이미 구해진 답을 의미한다.

1.1 다이나믹 프로그래밍 구현 방식

  1. Top-down
  2. Bottom-up
    이 두가지 구현 방식이 있다.

1번에 경우 앞서 본 재귀호출로 구현된 부분을 의미하고 2번은 반복문을 통해 구현하는 것을 의미한다.

2번은 문제의 크기가 작은 문제부터 차례대로 푸는 형태이기 때문에 큰 문제는 항상 풀 수 있다는 점이다. 하지만 1번의 방법으로 금방 푸는 문제를 2번 방법으로는 오래 걸리는 경우가 존재한다.
또한 1번 방법으로 생기는 문제가 스택오버플로우가 있는데, 이는 대체적으로 개발자가 잘못 구현한 경우라고 한다. (예를들어 점화식을 잘 못 구한 것?) 

int[] d = new int[100];
public int fibonacci(int n) {
	d[0] = 0;
    	d[1] = 1;
    	for(int i=2; i <= n; i++){
        	d[i] = d[i-1] + d[i-2];
	}
    	return d[n];
}

2번 Bottom-up 방식의 코드이다.

2. DP 문제

2.1 문제 : 1로 만들기

이 문제는 주어진 연산(조건)을 선택해서 어떤 정수 N을 1로 만드는데 최소한의 횟수를 구하는 것이다.

조건은 아래와 같다.
1. X가 3으로 나누어 떨어지면 3으로 나눈다.
2. X가 2로 나누어 떨어지면 2로 나눈다.
3. 1을 뺀다.

1번, 2번, 3번순으로 N을 1로 만들게 되는 경우를 생각해 볼 수 있는데, 이는 문제가 존재한다.
예를들어, N을 10이라 했을 때 앞서 말한대로 풀면 10 -> 5 -> 4 -> 2 -> 1 총 4번의 연산이 나오지만
10 -> 9 -> 3 -> 1 총 3번의 연산이 나오는 경우가 있다. 따라서 이 방법으로 구할 수 없는 문제이다.

이제 DP를 사용해보자.
제일 먼저 문제를 정의하는 것이 중요하다. 즉 점화식의 정의를 세우는 것이다.
해당 문제는 N을 1로 만드는 최소 연산 횟수를 구하는 것이다.
변수로 나타내면 D[N] = N을 1로 만드는 최소 연산 횟수 라고 할 수 있다.

그러면 작은 문제는 어떻게 나올 수 있는 것인가? 이미 문제에 조건이 주어져 있어 이를 적용하면 된다.
1번에 경우 사용한다고 치자. 그러면 N을 N/3으로 만드는 연산 1번과 N을 3으로 나누고 그 값을 1로 만드는 최소 연산 횟수의 합이 필요하다. 2번, 3번 역시 동일하다.
즉, 식으로 표현하면 1번은 D[N/3]+1 2번은 D[N/2]+1 3번은 D[N-1]+1 이라고 할 수 있다.
따라서 D[N]의 값은 1,2,3번의 최솟값에+1를 해주면 되는 것이다. D[N] = min(D[N/3],D[N/2],D[N-1])+1

public static int[] d;
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	d = new int[n + 1];
	System.out.println(go(n));
}
public static int go(int n) {
	if (n == 1) {
		return 0;
	}
	if (d[n] > 0) {
		return d[n];
	}
	d[n] = go(n - 1) + 1;
	if (n % 2 == 0) {
		int temp = go(n / 2) + 1;
		if (d[n] > temp) {
			d[n] = temp;
		}
	}
	if (n % 3 == 0) {
		int temp = go(n / 3) + 1;
		if (d[n] > temp) {
			d[n] = temp;
		}
	}
	return d[n];
}

여기서 3번 조건을 왜 먼저 했는지 의문이 들을 것이다. 그 이유는 최소값을 구하기 위해서는 비교를 해야하는데 3번이 쉽게 구해지는 것이기 때문에 편의상 저렇게 코드를 구성한 것이다.
아래 코드는 Botto-up방식으로 구현한 코드이다.

public static void main(String args[]) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] d = new int[n + 1];
	d[1] = 0;
	for (int i = 2; i <= n; i++) {
		d[i] = d[i - 1] + 1;
		if (i % 2 == 0 && d[i] > d[i / 2] + 1) {
			d[i] = d[i / 2] + 1;
		}
		if (i % 3 == 0 && d[i] > d[i / 3] + 1) {
			d[i] = d[i / 3] + 1;
		}
	}
	System.out.println(d[n]);
}

2.2 문제 : 2 X n 타일링

문제를 점화식으로 먼저 정의를 해야한다.
문제를 관계 하나와 나머지로 나누어야 하는데, 이 문제에서는 왼쪽부터 차례대로 블록을 놓았을 때 즉, 단계별로 블록을 놓았을 때 마지막 단계에서 어떤 블록을 놓아야하는지로 구분할 수 있다.

쉽게 말해서 단계별로 진행을 하면서 마지막 블록에는 1 X 2 블록 2개 또는 2 X 1 블록 한개 이 두가지 경우가 존재한다.

그러면 점화식은 어떻게 되는 것인가?
문제는 2 x n 크기의 직사각형을 채우는 방법의 수를 구하는 것이다. 따라서 D[n] = 2 X n 크기의 직사각형을 채우는 방법의 수 라고 정의할 수 있다.

2 X 1 블록이 마지막에 오는 경우는 전체 블록을 2 X N 블록이라 했을 때 마지막 블록 전은 2 X (N-1) 블록이다. 그러면 이 블록의 경우의수는 D[n-1]이 되는 것이다.
마찬가지로 1 X 2 블록 2개가 마지막에 오는 경우는 마지막 블록 전 블록이 2 X (n-2) 블록이 되고 이 경우의수는 D[n-2]가 된다.
이 두가지의 경우의 수를 합한 것이 결과로 이어지는 것이다.
즉, D[n] = D[n-1] + D[n-2] 이다.

Bottom-up 방식

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] d = new int[1001];
	d[0] = 1;
	d[1] = 1; // 2x1 타일 일 때 경우의 수는 1이다.
	for (int i = 2; i <= n; i++) {
		d[i] = d[i - 1] + d[i - 2];
		d[i] %= 10007;
	}
	System.out.println(d[n]);
}

Top-down방식

public static int[] d;
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	d = new int[1001];
	System.out.println(go(n));
}
public static int go(int n) {
	if (n <= 1) {
		return 1;
	}
	if (d[n] > 0) {
		return d[n];
	}
	d[n] = go(n - 1) + go(n - 2);
	d[n] %= 10007;
	return d[n];
}

2.3 문제 : 2 X n 타일링 2

2.2 문제와 푸는 방식이 매우 비슷하다.
2 X 2 블록이 추가된 것인데, 2.2 문제에서 나온 점화식을 그대로 가져오면 D[n] = D[n-1] + D[n-2] 이다.
여기에 2 X 2 블록에 대한 부분을 추가하면 끝난다. 이 블록은 가로가 2이기 때문에 D[n-2] 라고 할 수 있다.

따라서 점화식은 D[n] = D[n-1] + 2 * D[n-2] 라고 할 수 있다.
부가적으로 설명하면 D[n-2]부분은 1 X 2 블록 2개일 때와 2 X 2 블록 하나일 때 두 개이기 때문에 2를 곱한것이다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] d = new int[1001];
	d[0] = 1;
	d[1] = 1; // 2x1 타일 일 때 경우의 수는 1이다.
	for (int i = 2; i <= n; i++) {
		d[i] = d[i - 1] + d[i - 2] * 2;
		d[i] %= 10007;
	}
	System.out.println(d[n]);
}

2.4 문제 : 1,2,3 더하기

문제는 정수 n을 1,2,3의 합으로 나타내는 방법의 수를 구하는 문제이다. 따라서 D[n] = n을 1,2,3의 합으로 나타내는 방법의 수 라고 할 수 있다.

n = O + O + O + ... + O + O 형태로 생각할 수 있는데, 여기서 제일 마지막 부분이 1, 2, 3 이 3가지가 오는 경우를 살펴봐야한다.
즉, O + O + O + ... + O + 1 과 O + O + O + ... + O + 2 그리고 O + O + O + ... + O + 3 이러한 형태인데 각각 앞부분은 n-1 , n-2, n-3 으로 나타낼 수 있다.

정리하면 첫 번째는 (n-1) + 1 = n 두 번째는 (n-2) + 2 = n 세 번째는 (n-3) + 3 = n 이러한 형태인 것이다. 따라서 해당하는 것에 경우의 수를 다 더하면 결과가 나온다.

점화식으로 나타내면 D[n] = D[n-1] + D[n-2] + D[n-3] 이라 할 수 있다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int t = sc.nextInt();
	int[] d = new int[11];
	d[0] = 1; d[1] = 1; d[2] = 2; 
	for(int i=3;i<=10;i++) {
		d[i] = d[i-1] + d[i-2] + d[i-3];
	}
	while (t-- > 0) {
		int n = sc.nextInt();
		System.out.println(d[n]);
	}
}

2.5 문제 : 카드 구매하기

문제는 주어진 카드의 개수 N개를 구매하는데 드는 최대 비용을 구하는 것이다. 그리고 i번째 카드팩은 i개의 카드를 담고 있고, 가격은 P[i]원이다.

카드팩1 + 카드팩2 + ... + 카드팩(마지막) = N개를 생각해 볼 수 있다. 그러면 마지막 카드팩에 오는 카드는 몇개인 것인가? 이는 알 수 없는 것이다. 따라서 마지막에 오는 카드팩이 1부터 특정 변수 i개까지 라고 생각할 수 있다.

그러면 마지막 카드팩의 카드가 i개라고 했을 때 그 이전까지 오는 카드의 개수는 N-i라고 할 수 있다.

이 문제는 카드 N개를 구매하는 비용의 최댓값을 구하는 것이다. 따라서 D[N] = 카드 N개를 구매하는 비용의 최댓값이다.

다시 돌아가서 N-i 부분의 비용의 최댓값은 D[N-i]라고 생각할 수 있고, 또한 마지막 카드팩의 비용은 P[i]라고 할 수 있다. 여기서 i의 범위를 고려해야하는데 최소는 카드가 1개일 경우부터 최대 카드가 N개일 때 까지이다. 즉 1≤i≤N1\leq i \leq N이다.

예를들어, 카드 n개를 구매하는 방법을 생각해보자

  • 카드 1개가 들어있는 카드팩을 구매하고, 카드 n-1개를 구매한다. P[1] + D[n-1]
  • 카드 2개가 들어있는 카드팩을 구매하고, 카드 n-2개를 구매한다. P[2] + D[n-2]
  • ...
  • 카드 n-1개가 들어있는 카드팩을 구매하고, 카드 1개를 구매한다. P[n-1] + D[1]
  • 카드 n개가 들어있는 카드팩을 구매하고, 카드 0개를 구매한다. P[n] + D[0]

식으로 정리하면 D[n] = max(D[n-i] + P[i]) (1≤i≤n1\leq i \leq n) 이다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] p = new int[n + 1];
	for (int i = 1; i <= n; i++) {
		p[i] = sc.nextInt();
	}
	int[] d = new int[n + 1];
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++) {
			if (d[i] < d[i - j] + p[j]) {
				d[i] = d[i - j] + p[j];
			}
		}
	}
	System.out.println(d[n]);
}

2.6 문제 : 카드 구매하기 2

2.5 문제와 비슷하지만 이 문제는 최솟값을 구하는 문제이다.

하지만 최솟값을 구하는 문제이기 때문에 2.4 문제처럼 0으로 초기화된 배열을 그대로 쓸 수 없다. 따라서 1000 * 10000 으로 초기화 하거나 -1로 초기화 하는 것이 좋다. 왜냐하면 카드의 갯수는 최대 1000개이고, 최대 비용은 10000이기 때문에 그 이상으로 나올 수 없기 때문이다. 또한 -1로 하는 것은 해당 문제에서는 음수가 나올 수 없기 때문이다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	int[] p = new int[n + 1];
	for (int i = 1; i <= n; i++) {
		p[i] = sc.nextInt();
	}
	int[] d = new int[n + 1];
	for (int i = 1; i <= n; i++) {
		d[i] = -1;
		for (int j = 1; j <= i; j++) {
			if (d[i] == -1 || d[i] > d[i - j] + p[j]) {
				d[i] = d[i - j] + p[j];
			}
		}
	}
	System.out.println(d[n]);
}

2.7 문제 : 1,2,3 더하기 5

2.4 문제에서 같은 수를 두 번 이상 연속해서 사용하면 안된다는 조건이 붙은 문제이다.

2.4 문제에서 나온 점화식이 아래와 같이 도출된 것을 알 수 있었다.

  • d[n] = d[n-1] + 1
  • d[n] = d[n-2] + 2
  • d[n] = d[n-3] + 3

하지만 연속해서 사용하면 안된다는 조건때문에 새로운 점화식이 필요한데 예를 들면 d[n-1]에서 n-1를 만드는 식의 마지막에 사용한 수가 1인 경우 조건에 위배되는 상황이 발생한다.

따라서 2차원 배열로 점화식을 변경해야한다.
마지막에 1이 오는 경우 1 앞에는 2 또는 3이 와야하며 마지막에 2나 3이 오는 경우도 마찬가지이다.
d[n][j] : n을 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j 라고 정의할 수 있다.

예를 들어,
d[n][1] = n을 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 1 이다. 즉 바로 전에 사용할 수 있는 수는 2,3인데 이를 점화식으로 나타내면 d[n][1] = d[n-1][2] + d[n-1][3]으로 나타낼 수 있다. 다른 것도 마찬가지로 적용을 하면 d[n][2] = d[n-2][1] + d[n-2][3] 과 d[n][3] = d[n-3][1] + d[n-3][2]이 나온다.

초기화하는 과정에서 1,2,3 더하기에서 한 것처럼 d[0]=1로 하면 중복이 발생한다.
d[0][1] = 1, d[0][2] = 1, d[0][3] = 1로 초기화를 하면 d[1][1] = d[0][2] + d[0][3] = 2 가 된다. 원래 d[1][1] = 1 이 되어야하는데 중복으로 인해 결과가 다른 것이다. 따라서 이 부분을 예외처리가 필요하다.

j = 1일 때를 예를 들어보면
n>1n>1 일 때 d[n][1] = d[n-1][2] + d[n-1][3] 이고, n == 1 이면 d[n][1] = 1, n<1n<1 이면 d[n][1] = 0 이렇게 해야한다.

static final long mod = 1000000009L;
static final int limit = 100000;
static long[][] d = new long[limit + 1][4];
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	for (int i = 1; i <= limit; i++) {
		if (i - 1 >= 0) {
			d[i][1] = d[i - 1][2] + d[i - 1][3];
			if (i == 1) {
				d[i][1] = 1;
			}
		}
		if (i - 2 >= 0) {
			d[i][2] = d[i - 2][1] + d[i - 2][3];
			if (i == 2) {
				d[i][2] = 1;
			}
		}
		if (i - 3 >= 0) {
			d[i][3] = d[i - 3][1] + d[i - 3][2];
			if (i == 3) {
				d[i][3] = 1;
			}
		}
		d[i][1] %= mod;
		d[i][2] %= mod;
		d[i][3] %= mod;
	}
	int t = sc.nextInt();
	while (t-- > 0) {
		int n = sc.nextInt();
		System.out.println((d[n][1] + d[n][2] + d[n][3]) % mod);
	}
}

2.8 문제 : 쉬운 계단 수

예시로 주어진 45656과 같은 인접한 자리의 차이가 1이 나는 수를 계단수라고 하는데 이 문제는 길이가 N인 계단 수의 개수를 구하는 문제이다.

점화식은 D[N][L] = 길이가 N인 계단수이고 마지막 수가 L인 계단수의 개수라고 할 수 있다.

길이가 N이니까 N번째 수는 L 그러면 이전의 수는 L+1 또는 L-1이 올 수 있고 N-1번째라고 할 수 있다.
따라서 점화식을 D[N][L] = D[N-1][L-1] + D[N-1][L+1]형태로 나타낼 수 있다. 하지만 L=0 인 경우는 L-1를 할 경우 음수가 나오기 때문에 예외처리를 해줘야 하고, L=9인 경우는 L+1를 하면 10이 나오기 때문에 예외처리 해줘야한다.

public static long mod = 1000000000L;
public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	long[][] d = new long[n + 1][10]; // 길이가 n , 0~9 까지 수
	for (int i = 1; i <= 9; i++) {
		d[1][i] = 1;
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= 9; j++) {
			d[i][j] = 0;
			if (j - 1 >= 0) {
				d[i][j] += d[i - 1][j - 1];
			}
			if (j + 1 <= 9) {
				d[i][j] += d[i - 1][j + 1];
			}
			d[i][j] %= mod;
		}
	}
	long result = 0;
	for (int i = 0; i <= 9; i++) {
		result += d[n][i];
	}
	result %= mod;
	System.out.println(result);
}

2.9 문제 : 이친수

이 문제의 조건을 먼저 봐야한다.
1. 이친수는 0으로 시작하지 않는다.
2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다.

이 두가지 조건을 가지고 점화식을 세워보면 D[N][L] = N자리 이친수이고 마지막 수가 L인 이친수의 개수 라고 할 수 있다.

L에 올 수 있는 수는 0 또는 1이고 이를 나눠서 생각해보자.
N번째에 0이 오면 N-1번째에는 0과 1 둘다 올 수 있다. 그러면 D[N][0] = D[N-1][0] + D[N-1][1] 이 된다. 그러면 N번째에 1이 오면 N-1번째에는 1은 조건에 위배되니까 0 밖에 오지 못한다. 따라서 D[N][1] = D[N-1][0]이 된다.
결과를 구하려면 이 두개를 더하면 되는데 즉, D[N][L] = D[N][0] + D[N][1] 를 해주면 되는 것이다.

그러면 길이가 최소일 때 (N=1) 이때는 D[1][0]=0 이고, D[1][1] = 1 이 된다. 

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	long[][] d = new long[n + 1][2];
	d[1][0] = 0;
	d[1][1] = 1;
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j < 2; j++) {
			if (j == 0) {
				d[i][j] = d[i - 1][j] + d[i - 1][j + 1];
			}else if (j == 1) {
				d[i][j] = d[i - 1][j - 1];
			}
		}
	}
	System.out.println(d[n][0] + d[n][1]);
}

이 문제를 일차원으로 고칠 수가 있다.
D[N] = N자리 이친수의 개수로 정의하고 이 안에는 마지막 수가 0이 올 때와 1이 올 때 두가지가 다 들어간 상태이다.
마지막 수가 0이 오면 N-1 번째에는 0또는 1이 올 수 있으니 D[N-1]이다. 마지막에 1이 오면 N-1 번째에는 0밖에 못 오고 1은 올 수가 없으니 N-1 번째와 N번째를 통째로 하나로 생각 할 수 있다. 그러면 N-2번째는 0 또는 1이 올 수 있으니까 D[N-2]를 구하면 되는 것이다.
즉, D[N] = D[N-1] + D[N-2] 인 점화식을 도출 할 수 있다.

public static void main(String[] args) {
	Scanner sc = new Scanner(System.in);
	int n = sc.nextInt();
	long[] d = new long[n + 1];
	d[1] = 1;
	if(n>=2) {
		d[2] = 1;
	}
	for(int i=3;i<=n;i++) {
		d[i] = d[i-1] + d[i-2];
	}
	System.out.println(d[n]);
}

참고

백준 알고리즘 기초 강의를 듣고 공부하기 위해 정리한 것입니다.

profile
노력하는 배짱이
이전 포스트

TIL #6 알고리즘 기초 - 수학 (문제)

다음 포스트

TIL #8 다이나믹 프로그래밍 (2)

0개의 댓글