1. 조합
조합은 nCr로 표현하고, 이는 n개의 숫자에서 r개를 뽑는 경우의 수를 뜻한다. 조합과 비교되는 순열은 nPr로 표현되고, n개의 숫자 중 r개를 뽑아 순서를 고려해 나열할 경우의 수를 이야기한다. 순열과 조합의 차이는 순서의 고려 유무이다. 즉, 조합에서는 데이터 1, 2, 3과 3, 2, 1을 같은 경우로 판단하고, 순열은 다른 경우로 판단한다.
일반적으로 조합은 '동적 계획법'의 시작이라고 볼 수 있다. 따라서 알고리즘에서 조합을 구현할 때는 점화식을 사용해 표현한다.
점화식 표현
1. 특정 문제를 가정한다.
먼저 적당한 조합 문제를 가정한다. 5개의 데이터에서 3개를 선택하는 조합의 경우의 수를 푸는 문제로 가정해본다.
2. 모든 부분 문제가 해결된 상황이라고 가정하고 지금 문제를 생각한다.
모든 부분 문제가 해결된 상황이라고 가정하자. 먼저 5개의 데이터 중 4개를 이미 선택이 완료된 데이터라고 가정한다. 그리고 마지막 데이터의 선택 여부에 따른 경우의 수를 계산한다. 만약 마지막 데이터를 포함해 총 3개의 데이터를 선택하려면 선택이 완료됐다고 가정한 4개의 데이터에서 2개를 선택해야 한다. 마지막 데이터를 포함하지 않고 총 3개의 데이터를 선택하려면 이전 데이터 4개중 3개를 선택해야 한다. 2가지 경우의 수를 합치면 데이터 5개 중 3개를 선택하는 경우의 수가 나온다.
앞 그림을 점화식으로 표현하면 다음과 같다.
5개 중 3개를 선택하는 경우의 수 점화식
D[5][3] = D[4][2] + D[4][3]
이 내용을 도출할 때 고민하는 부분이 '4개 중 2개를 선택하는 경우의 수와 4개 중 3개를 선택하는 경우의 수를 구해야 하는 거 아닌가?'이다. 하지만 앞에서도 언급했듯이 모든 부분의 문제가 해결됐다고 가정해야 한다. 지금은 5개 중 3개의 경우의 수를 구하는 것이 아니라 궁극적으로 조합과 관련된 점화식을 도출하는 것이기 떄문이다.
3. 특정 문제를 해결한 내용을 바탕으로 일반 점화식 도출
조합 점화식
D[i][j] = D[i-1][j-1] + D[i-1][j]
2. 동적 계획벅 (DP)
동적 계획법은 복잡한 문제를 여러 개의 간단한 문제로 분리하여 부분의 문제들을 해결함으로써 최정적으로 복잡한 문제의 답을 구하는 방법을 뜻한다.
동적 계획법의 원리와 구현
- 큰 문제를 작은 문제로 나눌 수 있어야 한다.
- 작은 문제들이 반복돼 나타나고 사용되며 이 작은 문제들의 결괏값은 항상 같아야 한다.
- 모든 작은 문제들은 한 번만 계산해 DP 테이블에 저장하며 추후 재사용할 때는 이 DP 테이블을 이용한다. 이를 메모이제이션 기법이라고 한다.
- 동적 계획법은 톱-다운 방식과 바텀-탑 방식으로 구현할 수 있다.
동적 계획법의 가장 대표적인 문제인 피보나치 수열을 예로 들 수 있다.
피보나치 수열 공식
D[N] = D[N-1] + D[N-2]
1. 동적 계획법으로 풀수 있는지 확인
6번째 피보나치 수열은 5번째 피보나치 수열과 4번째 피보나치 수열의 합이다. 즉, 6번째 피보나치 수열을 구하는 문제는 5번째 피보나치 수열과 4번째 피보나치 수열을 구하는 작은 문제로 나눌 수 있고, 수열의 값은 항상 같기 때문에 동적 계획법으로 풀 수 있다.
2. 점화식
점화식을 세울 때는 논리적으로 전체 문제를 나누고, 전체 문제와 부분 문제 간의 인과 관계를 파악하는 훈련이 필요하다. 즉, 피보나치 수열의 점화식은 D[i] = D[i-1]+D[i-2]이 된다.
3. 메모이제이션 원리 이해
메모이제이션은 부분 문제를 풀었을 때 이 문제를 DP테이블에 저장해 놓고 다음에 같은 문제가 나왔을 때 재계산하지 않고 DP테이블의 값을 이용하는 것을 말한다. 다음 그림을 보면 위에서 2번째와 3번째 피보나치 수열은 맨 왼쪽 탐색 부분에서 최초로 값이 구해지고, 이 때 DP 테이블에 값이 저장된다. 이에 따라 나중에 2번째와 3번쨰 피보나치 수열의 값이 필요할 때 재연산을 이용해 구하지 않고, DP 테이블에서 바로 값을 추출한다. 이러한 방식을 사용하면 불필요한 연산과 탐색이 줄어들어 시간 복잡도 측면에서 많은 이점을 가질 수 있다.
4. 톱-다운 구현 방식 이해
톱-다운 구현 방식은 말 그대로 위에서부터 문제를 파악해 내려오는 방식으로, 주로 재귀 함수 형태로 코드를 구현한다. 코드의 가독성이 좋고, 이해하기가 편하다는 장점이 있다.
ex) 피보나치 수 (백준 2747) - 톱다운
import java.io.*;
public class P2747_피보나치수 {
static int[] A;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
A = new int[n + 1];
for (int i = 0; i <= n; i++) A[i] = -1;
A[0] = 0;
A[1] = 1;
bw.write(String.valueOf(fibo(n)));
bw.flush();
bw.close();
br.close();
}
static int fibo(int i) {
if (A[i] != -1) return A[i];
return A[i] = fibo(i - 1) + fibo(i - 2);
}
}5. 바텀-업 구현 방식 이해
가장 작은 부분 문제부터 해결하면서 점점 큰 문제로 확장해 나가는 방식이다. 주로 반복문 형태이다.
ex) 피보나치 수 (백준 2747) - 바텀업
import java.io.*;
public class P2747_피보나치수 {
static int[] A;
static int n;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
n = Integer.parseInt(br.readLine());
A = new int[n + 1];
for (int i = 0; i <= n; i++) A[i] = -1;
A[0] = 0;
A[1] = 1;
bw.write(Integer.toString(fibo_bottomup(n)));
bw.flush();
bw.close();
br.close();
}
static int fibo_bottomup(int i) {
if (A[i] != -1) return A[i];
for (int j = 2; j <= n; j++) {
A[j] = A[j - 1] + A[j - 2];
}
return A[i];
}
}두 방식 중 좀 더 안전한 방식은 바텀-업이다. 톱-다운 방식은 재귀 함수의 형태로 구현돼있기 때문에 재귀의 깊이가 매우 깊어질 경우 런타임 에러가 발생할 수 있다. 하지만 실제 코딩 테스트에서 이 부분까지 고려해야 하는 난이도는 잘 나오지 않는다. 오히려 자신이 구현한 함수에 버그가 있을 확률이 더 높을 것이다. 이 부분을 제외하면 두 방식의 차이점은 거의 없다고 할 수 있다.
3. 실전 문제
이항 계수 1 (백준 11050)
import java.io.*;
import java.util.StringTokenizer;
public class P11050_이항계수1 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
int[][] D = new int[N + 1][N + 1];
for (int i = 0; i <= N; i++) {
D[i][i] = 1;
D[i][0] = 1;
D[i][1] = i;
}
for (int i = 2; i <= N; i++) {
for (int j = 2; j < i; j++) {
D[i][j] = D[i-1][j] + D[i-1][j-1];
}
}
bw.write(D[N][K]+"");
bw.close();
}
}
2xn 타일링 (백준 11726)
import java.io.*;
public class P11726_2xn타일링 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
int n = Integer.parseInt(br.readLine());
int[] D = new int[1001];
D[1] = 1;
D[2] = 2;
for (int i = 3; i <= n; i++) D[i] = (D[i - 1] + D[i - 2]) % 10007;
bw.write(D[n] + "");
bw.flush();
bw.close();
br.close();
}
}
