동적 계획법(Dynamic Programming) 과 분할 정복(Divide and Conquer)
* 동적 계획법(DP)
- 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘 이다.
- 상향식 접근법으로, 가장 최하위 해답을 구한 후 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식이다.
- Memoization(메모이제이션) 기법을 사용한다.
- 프로그램 실행 시 이전에 계산한 값을 저장해서 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술이다.
- 잘개 쪼개진 작은 부분 문제들을 한번씩만 풀기 위해서 사용한다.
- 예시 : 피보나치 수열
- 말이 어려울 뿐이지 사실 한번 계산해서 얻은 결과를 배열과 같은 자료구조에 저장해서 추후에 필요할 경우 배열 인덱스 서칭을 통해 데이터를 가져오는 것이다.
* 분할 정복
- 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘 이다.
- 하향식 접근법으로, 상위의 해답을 구하기 위해 아래로 내려가면서 하위의 해답을 구하는 방식이다.
- 일반적으로 재귀 함수로 구현한다.
- 문제를 잘개 쪼갤 때, 부분 문제는 서로 중복되지 않는다.
- 예시 : 병합 정렬, 퀵 정렬 등
- 분할 정복에 대한 이해는 이후에 병합 정렬, 퀵 정렬에 대한 수업을 들으면서 이해해보자.
DP 와 DAQ 의 공통점과 차이점
* 공통점
- 문제를 잘개 쪼개서 가장 작은 단위로 분할한다.
* 차이점
- 동적 계획법(DP)
- 부분 문제는 중복되어 상위 문제 해결 시 재활용된다.
- Memoization 기법을 사용한다.(부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)
- 분할 정복(DAQ)
- 부분 문제는 서로 중복되지 않는다.
- Memoization 기법을 사용하지 않는다.
DP 에 대한 이해
- 피보나치 수열 문제 : 피보나치 수열 n 을 입력받아서 다음과 같이 계산한다.
여기서 피보나치 수열을 일반 재귀 호출 형식으로 작성할 경우 아래와 같이 문제가 발생할 수 있다.
- fibo(4) 의 값을 구하려면 fibo(3) 과 fibo(2) 의 값이 필요하고, fibo(3) 의 값을 구하려면 fibo(2), fibo(1) 의 값이 필요하며, fibo(2) 의 값을 구하려면 fibo(1), fibo(0) 의 값이 필요하다.
- 이를 보면 알 수 있듯이 동적 계획법을 사용하지 않고 일반 재귀 호출로 문제를 해결하게 되면 fibo(2), fibo(1), fibo(0) 과 같이 중복되는 문제의 경우, 이미 앞서 답을 구했음에도 불구하고 똑같은 문제를 중복해서 다시 해결하게 된다.
- 동적 계획법을 활용하면 Memoization 기법을 활용하기 때문에 똑같은 중복 문제를 다시 풀지 않고 전체 문제를 해결할 수 있게된다.
동적 계획법(DP) 문제의 풀이법
- 적용될 수 있는 점화식을 찾아내는 것이 중요하다.
- 점화식이란 이웃하는 두 개의 항 사이에 성립하는 관계를 나타낸 관계식이다.
- 예시 : dp[n] = dp[n - 1] + dp[n - 2]
피보나치 수열을 동적 계획법으로 작성하는 방식으로 풀 수 있는 문제를 백준에서 다음과 같이 찾아서 해결 해보았다.
https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
- Main.java
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.math.BigInteger;
public class Main {
static BigInteger[] tile = null;
public static void main(String[] args) throws NumberFormatException, IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
tile = new BigInteger[n];
if(n == 1)
tile[0] = BigInteger.valueOf(1);
else{
tile[0] = BigInteger.valueOf(1);
tile[1] = BigInteger.valueOf(2);
}
bw.write(tiling(n) + "\n");
bw.flush();
bw.close();
}
private static BigInteger tiling(int n) {
if(n == 1 || n == 2)
return tile[n-1];
else {
for(int i = 2; i < n; i++) {
tile[i] = tile[i-1].add(tile[i-2]);
}
}
return tile[n-1].remainder(BigInteger.valueOf(10007));
}
}
- 입력 숫자가 1,2 와 같이 작은 문제에 해당하는 부분은 따로 값을 찾아서 선언해놓은 배열에 적재해 주었다.
- 입력 숫자가 3이 넘어갈 때 부터는 피보나치 수열의 점화식 대로 n-1 번째 인덱스와 n-2 번째 인덱스 값의 합을 배열의 적절한 인덱스에 적재해주었다.
- 위와 같이 계산한 값을 배열에 적재해 주는것을 Memoization 기법 이라고 한다.
'자료구조 및 알고리즘 > 알고리즘' 카테고리의 다른 글
[알고리즘] 자바에서의 병합 정렬 (0) | 2021.12.03 |
---|---|
[알고리즘] 자바에서의 퀵 정렬 (0) | 2021.12.03 |
[알고리즘] 자바에서의 재귀 호출(Recursive Call) # 2 (0) | 2021.12.01 |
[알고리즘] 자바에서의 재귀 호출(Recursive Call) # 1 (0) | 2021.12.01 |
[알고리즘] 자바에서의 선택 정렬 (0) | 2021.11.30 |