이번 주차는 좀 중요한 주차인 듯하다. 특히나 트리(세그먼트 트리)같은 경우에는 코딩 테스트에 단골로 나오는 그런 주제라고 하니 좀 시간을 들여 원리 이해 및 문제 풀이에 신경을 쓰도록!
21일차 : 이진 트리
22일차 : 세그먼트 트리 ★중요
23일차 : 최소 공통 조상
24일차 : 조합과 순열 ★중요
25일차 : 조합/순열 문제 풀이
[21일차]
[이진 트리]
: 각 노드의 자식 노드의 갯수가 2 이하로 구성돼 있는 트리
*트리 영역에서 가장 많이 사용되는 형태임
- 이진 트리의 종류
편향 이진 트리 : 노드들이 한쪽으로 편향돼 생성된 이진 트리
포화 이진 트리 : 트리의 높이가 모두 일정하며 리프 노드가 꽉찬 이진 트리
완전 이진 트리 : 마지막 레벨을 제외하고 완전하게 노드들이 채워져 있고, 마지막 레벨은 왼쪽부터 채워진 트리 → 중간에 빈 곳 없이 왼쪽부터 차곡차곡 채워진 트리를 의미. 마지막 레벨은 비어있어도 이 규칙만 지키면 됨.
*데이터를 트리에 저장할 때 편향 이진 형태로 저장 시, 탐색 속도 저하 및 공간 낭비.
→ 일반적으로 코테에서 데이터를 트리에 담는다고 하면 완전 이진 트리 형태 떠올리면 됨.
- 이진 트리의 순차 표현
: 가장 직관적이면서 편리한 트리 자료구조 형태는 '배열'임
이진 트리 순차 표현
표현 : [1] [2] [3] [4] [5] [6] [7]
좌측 : A B C D E F G
우측 : A B ㅡ C ㅡ ㅡ ㅡ
이와 같이 1차원 배열 형태로 표현이 가능.
이 때, 트리 노드와 배열의 인덱스 간 상관 관계는?
이동 목표 노드
인덱스 연산
제약 조건(N = 노드 개수)
루트 노드
index = 1
부모 노드
index = index / 2
현재 노드가 루트 노드가 아님
왼쪽 자식 노드
index = index * 2
index * 2 <= N
오른쪽 자식 노드
index = index * 2 + 1
index * 2 + 1 <= N
→ 이 인덱스 연산 방식은 추후 세그먼트 트리나 LCA(Lowest Common Ancestor) 알고리즘에서 기본이 되는 연산. 꼭 숙지 !!!
- 예제 문제
백준 1991번 : 트리 순회하기 (실버 1)
package study.week5;
import java.io.*;
import java.util.*;
public class P1991 {
static int[][] tree = new int[26][2]; // 2차원 배열로 트리 생성 [알파벳][자식구분용]
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine()); // 트리의 노드 갯수 입력
for (int i = 0; i<N; i++) {
String node = br.readLine(); // 노드 정보 입력 부모, 자식 (문자열 형태임)
StringTokenizer st = new StringTokenizer(node); // 입력받은 노드 정보로
char parent = st.nextToken().charAt(0); // 부모 노드 잘라서 문자형으로 변환
char left = st.nextToken().charAt(0); // 왼쪽 자식 잘라서 문자형으로 변환
char right = st.nextToken().charAt(0); // 오른 자식 잘라서 문자형으로 변환
int pIdx = parent - 'A'; // 2차원 배열에 쓸 부모 인덱스 정수로 변환
// # 참고!! # 어차피 입력받은 알파벳에 따라 숫자형으로 바꿨기 때문에 숫자 = 알파벳 똑같다 보면 됨!
// 뭐 숫자 순서대로 알파벳 저장됐다 생각하면 되니 오히려 더 편할 수도?
if (left == '.') { // 왼쪽 자식이 '.'이면 없다는 걸로 간주
tree[pIdx][0] = -1; // 없으면 -1로 채워 없다는 걸 구분함.
} else { // 있으면
tree[pIdx][0] = left - 'A'; // 해당 부모 인덱스의 왼쪽 자식 저장
}
if (right == '.') { // 오른쪽 자식이 '.'이면 없다는 걸로 간주
tree[pIdx][1] = -1; // 없으면 -1로 채워 없다는 걸 구분함.
} else { // 있으면
tree[pIdx][1] = right - 'A'; // 해당 부모 인덱스의 오른쪽 자식 저장
}
}
preOrder(0); // 전위 순회 형태로 출력 : (루트) (왼자식) (오른자식)
System.out.println();
inOrder(0); // 중위 순회 형태로 출력 : (왼자식) (루트) (오른자식)
System.out.println();
postOrder(0); // 후위 순회 형태로 출력 : (왼자식) (오른자식) (루트)
System.out.println();
}
// 각각 재귀 형태로 구현함!!
// 좀 구구절절 설명하자면 node == -1일 때, 리턴하는 이유는
// 어차피 재귀적으로 자식 노드들을 계속 호출하면서 출력하는 형태기 때문에 (모든 노드들이 호출됨 한번씩)
// 이렇게 해야만 모든 노드가 출력되니까! 암튼 그래서 자식 없는 노드가 마지막에 없는 자식 호출하면 -1이 되니까 끝나는 거.
public static void preOrder(int node) {
if (node == -1) return; // 해당 노드(부모)가 -1이면 걍 리턴 암것도 출력 X.
System.out.print((char)(node + 'A')); // 부모 노드 호출!
preOrder(tree[node][0]); // 왼 자식 호출 : 이 때 자식이 없다면 -1이니 이 다음 재귀에서 걍 리턴.
preOrder(tree[node][1]); // 오른 자식 호출 : 이 때 자식이 없다면 -1이니 이 다음 재귀에서 걍 리턴.
}
public static void inOrder(int node) {
if (node == -1) return;
inOrder(tree[node][0]);
System.out.print((char)(node + 'A'));
inOrder(tree[node][1]);
}
public static void postOrder(int node) {
if (node == -1) return;
postOrder(tree[node][0]);
postOrder(tree[node][1]);
System.out.print((char)(node + 'A'));
}
}
이 문제에서는 1차원 배열 형태가 아니라 2차원으로 표현했는데, 만약 1차원 형태로 위 문제를 표현했을 때의 문제점은 A~Z까지 26개의 알파벳이 입력되는데 완전 이진 트리나 포화 이진 트리 같은 형태가 아니라, 편향 이진 트리일 경우에는 Z까지 입력받을 경우 26층의 트리가 형성되는데 이렇게 되면 다른 자식 노드들이 없는 공간도 모두 메모리로 생성해줘야 하기 때문에 공간 낭비 개커짐. 그렇기에 2차원 형태로 tree[부모인덱스][자식구분용] 이렇게 선언을 하게 되면, tree[A][0] = A의 왼쪽 자식, tree[A][1] = A의 오른쪽 자식 의 형태로 구현해서 가독성도 올리고, 인덱스 값들로 인해 더 빠르게 접근이 가능함.
[22일차]
[세그먼트 트리]
: *세그먼트 트리는 완전 이진 트리의 성질을 무조건 따름!!! 주어진 데이터들의 구간 합과 데이터 업데이트를 빠르게 수행하기 위해 고안해 낸 자료구조 형태.
더 큰 범위는 '인덱스 트리'라고 불림.
- 핵심 이론?
: 세그먼트 트리 종류는 구간 합, 최대/최소 구하기로 나눌 수 있고, 구현 단계의 트리 초기화하기,
질의값 구하기(구간 합 또는 최대/최소), 데이터 업데이트하기로 나눌수 있음.
트리 초기화하기 : 리프 노드 갯수가 데이터의 갯수(N) 이상이 되도록 트리 배열을 만든다. 트리 배열 크기는 2^k >= N 을 만족하는 k의 최솟값을 구한 후, 2^k * 2를 트리 배열 크기로 정의한다. 이렇게 되면 트리 배열의 크기는 데이터 갯수(N)의 최소 2배가 된다. 생성한 후에 원본 데이터를 리프 노드에 입력한다. 이 때, 시작 인덱스는 2^k로 취해서 입력을 진행한다. #검색해보니 데이터가 N개면 간단하게 그냥 N * 4 크기로 배열 만든다고 함.
그 후, 리프 노들르 제외한 나머지 노드의 값을 채운다. (시작 인덱스 - 1)번 노드 부터 1번 노드 쪽으로 값을 채운다. 인덱스들을 채울 때는 자식 노드를 이용해 값을 채울 수 있다. 자식 노드 인덱슨느 이진 트리 형식이기 때문에 2N, 2N + 1이 된다. 케이스별로 적절히 계산한다. 아래에 케이스들을 명시함.
케이스 별 세그먼트 트리
- 구간 합 : A[N] = A[2N] + A[2N+1] - 최대 : A[N] = Math.max(A[2N], A[2N+1] - 최소 : A[N] = Math.min(A[2N], A[2N+1]이렇게 세그먼트 트리를 구성해 놓으면 그 이후 질의와 관련된 결괏값이나 데이터 업데이트 요구사항에 관해 좀 더 빠른 시간 복잡도 안에서 해결할 수 있게 됨
질의값 구하기 주어진 질의 인덱스를 세그먼트 트리의 리프 노드에 해당하는 인덱스로 변경한다. 인덱스는 : 주어진 질의 index + 2^k - 1로 구한다. 위의 경우에는 k = 3이었으니 이를 예로 들겠음. Ex) 시작 idx : 2, 끝 idx : 6, 세그먼트 트리 idx : 질의 인덱스 + 8 - 1 *여기서 질의란? 예를 들어, 2~8번 노드를 모두 더해서 출력하라. 3번부터 10만 번 범위 안에서 가장 큰 숫자는? 과 같이 구간을 지정하며 특정 값을 반환하라는 것이 질의.
[질의에 해당하는 노드 선택 과정] 1. 시작 구간 인덱스 % 2 == 1일 때, 해당 노드를 '선택' 2. 종료 구간 인덱스 % 2 == 0일 때, 해당 노드를 '선택' 3. 시작 구간 인덱스 다시 설정 → 시작 구간 인덱스 = (시작 구간 인덱스 + 1) / 2. ex) 520이었을 때, (520 + 1) / 2 = 260 4. 종료 구간 인덱스 다시 설정 → 종료 구간 인덱스 = (종료 구간 인덱스 - 1) /2. ex) 520일 때, (520 - 1) / 2 = 259로. 위의 과정을 반복하다가 종료 구간 인덱스 < 시작 구간 인덱스가 되면 종료. → while(start <= end)
*해당 노드를 '선택'한다는 것의 의미 - 왼쪽(시작)노드가 홀수일 때 (start % 2 == 1), 세그먼트 트리에서 홀수 인덱스는 '오른쪽 자식'을 의미함. 해당 노드가 오른쪽 자식인데, 나와 같은 자식인 왼쪽 자식은 start 범위의 밖에 있게 됨. 이 경우엔 부모 노드로 합쳐질 수 없음. 그래서 해당 오른쪽 자식의 값만 결과에 더해주고 start 인덱스를 ++증가하여 범위를 좁힌다. - 오른쪽(종료)노드가 짝수일 때 (end % 2 == 0), 짝수 인덱스는 '왼쪽 자식'을 의미함. 이 때도 동일하게 왼쪽 자식인데, 같은 자식인 오른쪽 자식은 end 범위 밖에 있게 되므로, 부모 노드와 합쳐질 수 없음. 그렇기에 해당 왼쪽 자식의 값만 결과에 더해주고, end 인덱스를 --감소시켜 범위를 좁힌다.
이런 작업(양옆의 범위 검사)을 거치고, 구간 인덱스를 다시 설정하고, 그 인덱스에서 다시 양옆 범위 검사를 진행하는 형태 / 2를 하는 이유는 자식 노드들의 합인 부모 노드 인덱스로 재설정하기 위함임. 최종적으로 start <= end가 되는 경우는, 구간 내에서의 루트 노드가 됐을 경우임. (모든 자식 노드들의 값이 합쳐진 노드)
이렇게 복잡한 트리를 사용하는 이유는 단순 for문의 경우 데이터가 커질 경우 1만개만 돼도 1만x1만 = 1억으로 시간초과, 하지만 세그먼트 트리는 미리 구해둔 트리 구조를 통해 O(logN)의 속도로 답을 찾을 수 있음.
- 예제 문제
백준 2042번 : 구간 합 구하기 3 (골드 1)
package study.week5.day22.P2042;
import java.io.*;
import java.util.*;
public class P2042 {
static long[] tree;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken()); // 노드 갯수
int M = Integer.parseInt(st.nextToken()); // 변경 횟수 (값)
int K = Integer.parseInt(st.nextToken()); // 구간 합 횟수
int treeHeight = 1; // 트리의 초기 높이 설정
while (true) { // 노드 갯수에 따라 트리 높이 재설정
if (Math.pow(2, treeHeight) >= N) break;
treeHeight++;
}
int treeSize = (int) Math.pow(2, treeHeight) * 2; // 트리 높이에 따라 트리 크기 설정
tree = new long[treeSize];
int leftNodeStartIdx = treeSize / 2 - 1; // 시작 인덱스(기준 인덱스) 지정. 트리 사이즈 반에 - 1
for (int i = 1; i<=N; i++) {
tree[leftNodeStartIdx + i] = Long.parseLong(br.readLine()); // 리프 노드에 데이터 입력하기
}
setTree(treeSize-1); // 리프 노드 외 조상 노드들 데이터 채우기
for (int i = 0; i<M+K; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken()); // 질의 타입 구분
int s = Integer.parseInt(st.nextToken()); // 시작 구간 / 바꿀 대상
long e = Long.parseLong(st.nextToken()); // 종료 구간 / 바꿀 수
if (a == 1) {
changeVal(leftNodeStartIdx + s, e); // 리프 노드의 s 번째 숫자를 e로 바꿈
}
else if (a == 2) {
s = s + leftNodeStartIdx;
e = e + leftNodeStartIdx;
System.out.println(getSum(s, (int) e)); // 구간 합 구간 지정
}
else {
return;
}
}
br.close();
}
private static long getSum(int s, int e) {
long partSum = 0;
while (s <= e) { // start <= end
if (s % 2 == 1) { // 왼쪽 자식이 홀수면?
partSum = partSum + tree[s]; // 자신의 값만 더하기
s++;
}
if (e % 2 == 0) { // 오른쪽 자식이 짝수면?
partSum = partSum + tree[e]; // 자신의 값만 더하기
e--;
}
s = s/2; // 그 외는 부모 노드에 합쳐서 진행
e = e/2; // 그 외는 부모 노드에 합쳐서 진행
}
return partSum;
}
private static void changeVal(int index, long val) {
// index : 변경할 노드 인덱스 번호, val : 변경할 숫자(값)
tree[index] = val; // 우선 전달받은 인덱스의 노드를 val로 변경.
while (index > 1) { // 1번 노드, 최상위 노드가 될 때까지 반복
index = index / 2; // 부모 노드로 인덱스 변경
tree[index] = tree[index * 2] + tree[index * 2 + 1]; // 부모 노드의 값을 다시 설정. 바뀐 자식들 값 합
}
}
private static void setTree(int i) { // 리프 노드 외 노드 값들 채우기.
while (i != 1) { // 루트 노드가 될 때까지 진행
tree[i / 2] += tree[i]; // 부모 노드에 현재 노드(자식) 값 더하기
i--; // 인덱스 -1 해서 다음 노드도 동일하게 진행.
}
}
}
백준 10868번 : 최솟값 찾기 2 (골드 1)
백준 11505번 : 구간 곱 구하기 (골드 1)
[23일차]
[최소 공통 조상] LCA(Lowest Common Ancestor) : 트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때, 처음 공통으로 만나게 되는 부모 노드를 '최소 공통 조상'이라 함.
- 핵심 원리? 두 가지의 방식으로 풀어나갈 수 있는데, 노드의 크기를 기준으로 나눌 수 있다. [1] 일반적인 LCA 구하기 (트리 높이가 크지 않을 때)
위와 같은 트리가 있을 때, 4번 노드와 15번 노드의 LCA를 구한다고 했을 때 먼저 루트 노드에서 탐색을 시작해 각 노드들의 부모 노드와 깊이를 저장한다. 이 때 탐색은 DFS나 BFS를 이용해 수행.
탐색 결과 이런 형태로 배열이 만들어지고 현재 4번 노드와 15번 노드의 깊이(층)이 다르기 때문에, 더 깊은 노드인 4번 노드를 1개씩 올려 주면서 같은 깊이로 맞춰준다. 이 순간에 두 노드가 같다면 해당 노드가 LCA이므로 탐색을 종료. 깊이가 같은 상태에서는 두 노드가 동시에 올라가면서 같은 노드가 될 때까지 반복. 결과적으로 해당 그래프에서는 노드가 1이 되는 순간 두 노드가 만나게 되며 LCA는 1이 된다.
이 방법이 일반적으로 LCA를 구하는 방법인데, 트리의 높이가 커질 경우에 시간 제약에 걸릴 수 있다. 이 방법은 최악의 경우, 트리가 편향 트리일 때 노드 갯수만큼 최대 O(N)의 시간 복잡도를 가진다. 문제에서 100만개의 노드를 가지고 1000번만 질의를 반복해도 10억 번의 연산이 수행되기 때문에 좀 더 새로운 방법이 필요하다.
[2] LCA 빠르게 구하기 우선 이 방식의 핵심은, 기본 원리는 기존과 비슷한데, LCA를 찾으러 올라가는 과정에서 한 단계씩 깊이를 올려주는 게 아닌 2^k씩 올라가 비교하는 방식이다. 즉, 2의 제곱수 씩 올라가며 찾는 것이므로, logN의 시간 복잡도로 해결이 가능하다. 그러므로, 자신의 부모 노드만 저장해 두는 게 아닌 2^k번째 위치의 부모 노드까지 저장해 두어야 한다.
- 부모 노드 배열 정의 : P[K][N] = N번 노드의 2^K번째 부모의 노드 번호 - 부모 노드 배열 점화식 : P[K][N] = P[K - 1][P[K - 1][N]] → P[K - 1][N]의 [K - 1] 위 조상. 예로 K가 3이라고 했을 때, P[3][N] = P[2][P[2][N]] 이 되는데, K가 제곱수를 뜻한다 했으니 N의 2^3위는 N의 2^2의 2^2위가 됨. 8 → 4 + 4 이런 식으로 8칸 위 조상은 4칸위 조상의 4칸위 조상.
그렇다면 왜 2 제곱수로 표현하는 건지? 이걸 '이진 점프'라고도 하는데, 10만 개 노드가 있다고 했을 때, 2의 제곱으로 표현하면 2^17 범위 내에서 모두 표현이 가능하다. 1, 2, 4, 8, ... , 131072 이렇게 구했을 때, 3은 2칸 위의 1칸 위이다. 6은 4칸 위의 2칸 위이다. 와 같이 2 제곱수들을 조합해서 모든 범위를 표현 가능하기 때문이다. 그래서 노드의 갯수가 많아지더라도 logN의 속도로 범위를 표현할 수 있다는 장점을 가지며 2 제곱수로 표현하는 이유이다.
이렇게 하면 기존 일반적인 LCA 구할 때는 O(N)의 시간으로 층을 하나씩 올라가야 했지만, 점화식을 만들어놓고, 그 점화식을 읽기만 함으로써 O(1)의 시간으로 줄일 수 있어 전체 탐색 시간은 O(logN)이 된다.
- 예제 문제
백준 11437번 : 최소 공통 조상 구하기 1 (골드 3)
package study.week5.day23.P11437;
import java.io.*;
import java.util.*;
public class P11437 {
static ArrayList<Integer>[] tree;
static int[] depth;
static int[] parent;
static boolean[] visited;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int N = Integer.parseInt(br.readLine());
tree = new ArrayList[N + 1];
for (int i = 1; i <= N; i++) {
tree[i] = new ArrayList<Integer>();
}
for (int i = 0; i<N-1; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
tree[start].add(end);
tree[end].add(start);
}
depth = new int[N + 1];
parent = new int[N + 1];
visited = new boolean[N + 1];
BFS(1);
StringBuilder sb = new StringBuilder();
int M = Integer.parseInt(br.readLine());
for (int i = 0; i<M; i++) {
st = new StringTokenizer(br.readLine());
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
sb.append(LCA(a, b)).append("\n");
}
System.out.print(sb);
}
static int LCA(int a, int b) {
if (depth[a] < depth[b]) {
int temp = a;
a = b;
b = temp;
}
while (depth[a] != depth[b]) {
a = parent[a];
}
while (a != b) {
a = parent[a];
b = parent[b];
}
return a;
}
private static void BFS(int node) {
Queue<Integer> Q = new LinkedList<Integer>();
Q.add(node);
visited[node] = true;
depth[node] = 0;
while (!Q.isEmpty()) {
int now_node = Q.poll();
for (int next : tree[now_node]) {
if (!visited[next]) {
visited[next] = true;
parent[next] = now_node;
depth[next] = depth[now_node] + 1;
Q.add(next);
}
}
}
}
}
백준 11438번 : 최소 공통 조상 구하기 2 (플래티넘)
[24일차]
[조합/순열]
- 조합 (Combination) : 조합은 nCr로 표현하고, 이는 n개의 숫자에서 r개를 뽑는 경우의 수를 뜻함.
- 순열 : 순열은 nPr로 표현하고, n개의 숫자 중 r개를뽑아 순서를 고려해 나열할 경우의 수를 말함.
*순열과 조합의 차이는 순서의 고려 여부 → 조합에서는 (1, 2, 3)과 (3, 2, 1)을 같은 경우로 판단하고, 순열은 다른 경우라고 판단함.
- 공식
순열 : nPr = n! / (n - r)! → 예로 5개 중 2개를 고르는 경우의 수는 총 5*4 = 20가지가 됨.
조합 : nCr = n! / (n - r)! r! → 5개 중 2개를 고르는 경우 순열 결과인 5*4에 2!로 나눠 5*4 / 2 = 10가지 경우의 수 가 된다. 이는 1과 2를 선택할 때와 2와 1을 선택할 때를 동일한 경우의 수로 만들기 위해서 2로 나누는 것.
- 핵심 원리?
조합은 '동적 계획법'의 시작이라 볼 수 있음.
알고리즘에서는 조합 구현할 때 위 수학 공식을 코드화하지 않고 점화식을 사용해서 표현한다.
[점화식을 세우는 3단계]
특정 문제 가정하기 5개의 데이터에서 3개를 선택하는 조합의 경우의 수를 푸는 문제로 가정.
모든 부분 문제가 해결된 상황이라 가정하고 지금 문제 생각하기 모든 부분 문제가 해결된 상황이라 가정. 먼저 5개의 데이터 중 4개를 이미 선택이 완료된 데이터라고 가정 마지막 데이터의 선택 여부에 따른 경우의 수를 계산 쉽게 말해, {A, B, C, D, E}라는 5개의 데이터가 있을 때, E를 기준으로 선택 여부에 따는 경우의 수를 계산한다는 것. (E, ?, ?)처럼 E를 선택했을 때는, 2개를 더 선택해야 하므로 4개중 2개를 선택하는 4C2이 되고. (?, ?, ?)처럼 E를 선택하지 않았을 때는, 3개를 더 선택해야 하므로 4개중 3개를 선택하는 4C3이 된다는 뜻이다. 그리고 이렇게 나온 두 선택에 따른 경우의 수인 4C2와 4C3을 더하면 5C3이 된다. → E를 선택했을 때와 선택하지 않았을 때 외의 경우는 존재하지 않기 때문. 즉 이게 모든 경우의 수를 의미.
이렇게 하는 이유는 뭘까? : 5C3을 한 번에 구하기엔 너무 크고 복잡하므로, 문제를 가장 작은 단위까지 쪼개서 해결한다. 기준은 마지막 데이터하나(5번째. E)를 선택할지 말지에 따라 5C3 → 4C3 + 4C2로 쪼개지고, E 안 뽑음 : 4C3 → 3C3 + 3C2, E 뽑음 : 4C2 →3C1 + 3C2 다시 3C2 → 2C2 + 2C1, 3C1 → 2C1 + 2C0 2C1 → 1C0 + 1C1 이런식으로 쪼개진 문제들은 다시 더 작은 문제로 쪼개지며, 가장 작은 단위가 될 때까지 진행한다. 여기서 3C3, 2C0같은 경우에는 3개중 3개를 뽑는 것이니 무조건 1개의 경우밖에 안나오고, 2개중 0개를 뽑는 경우도 '안 뽑는다'는 하나의 경우이기 때문에 1개의 경우의 수로 친다. (공집합의 개념과 같음) 즉, 2C1에서 최종적으로 1C0 + 1C1로 나누면, 1 + 1의 경우의 수라는 답이 나오게 된다. 이 때부터는 작게 쪼갠 문제의 해답을 조합해서 큰 문제의 해답을 풀어나가는 것이다.
굳이 이런 쪼개서 더하는 점화식을 쓰는 이유는 공식처럼 n! / r!(n - r)!을 쓰게 되면 계산 중간에 거대한 팩토리얼 값이 나와 컴퓨터가 담을 수 있는 숫자의 크기를 초과할 가능성이 큼. 즉, 한 번에 큰 숫자의 팩토리얼을 구해서 나누는 게 아니라 팩토리얼을 잘게 쪼개서 작은 수 단위로 계산해서 더해가며 답을 구하는 방식으로 사용하기 때문에 오버플로우가 발생할 위험이 없어진다.
그래서 재귀적으로 이렇게 문제를 쪼개고 답을 구해놓으면, (점화식을 만들어놓으면) 이 점화식을 바로 가져다쓸 수 있기 때문에 O(1)의 시간으로 답을 구할 수 있다. (이미 계산된 값을 배열에 저장해둬서) 이 때 표를 만드는 시간(점화식 채우는 시간) : O(N^2)의 시간이 꼭 필요하다. 점화식이 완성되면 어떤 조합이든 O(1)의 시간으로 답을 구할 수 있다.(메모이제이션)
일반 점화식 도출 결과적으로 큰 문제를 부분 문제로 쪼개어 계산하는 것의 점화식은 D[ i ][ j ] = D[ i - 1 ][ j ] + D[ i - 1][ j - 1 ] 로 표현할 수 있다. D[ i - 1 ][ j ] : 마지막 데이터를 선택하지 않음 D[ i - 1 ][ j - 1] : 마지막 데이터를 이미 선택함
