Divide and conquer

설계 전략

• 작은 단위로 분할 (Divide) ⇒ 작은 문제 해결 (Conquer) ⇒ 해답 통합 (Combine)

Example

• Binary Search

index location(index low, index high) {
	index mid;

	if (low > high)
		return 0;
	else {
		mid = (low + high) / 2;
		if (x == S[mid])
			return mid;
		else if (x < S[mid])
			return location(low, mid - 1);
		else
			return location(mid + 1, high);
	}
}

locationout = location(1, n);

BOJ 예제

10815번: 숫자 카드

Dynamic programming

설계 전략

• divide and conquer는 top-down, dynamic programming은 bottom-up ⇒ dynamic programming은 같은 계산 반복 수행 X
• 작은 문제를 먼저 해결하여 큰 문제의 해결로 확산
• 재귀 관계식 정립 ⇒ 작은 사례를 먼저 해결

Example

• 이항계수 구하기

int bin2(int n, int k) {
	index i, j;
	int B[0..n][0..k];
	for (i = 0; i <= n; i++) {
		for (j = 0; j <= min(i, k); j++) {
			if (j == 0 || j == i)
				B[i][j] = 1;
			else B[i][j] = B[i - 1][j - 1] + B[i - 1][j];
		}
	}
	return B[n][k];
}

BOJ 예제

1932번: 정수 삼각형

1463번: 1로 만들기

Greedy algorithm