🌓 분할정복

@ N~차시
@ N+1차시
@ Chapter 3

@ 재귀

💫 정의

---

1. 기본 단계를 해결합니다. 이 부분은 가능한 한 간단한 문제이어야만 합니다.
2. 문제가 기본 단계가 될 때까지 나누거나 작게 만듭니다.

🫧

@ Deduce 연역 : 추론
@ Induce 귀납 : 유도, 돌려서 말함 → 사례 → 확률 (<= 100%)
@ Induction 인덕션 : 자기장 유도 를 통해 열 생성
@ 수학적 귀납법 : 100%

분할 정복

REVIEW

Iteration 반복
N번 or 조건 만족까지 반복

Recursion 순환
스스로 호출하여 문제 해결
순환적 특징 갖는 문제 or 순환적 데이터 구조 (Like Tree)를 다루는 프로그램에 대해
밀접한 연관 : Inductive Definition 수학의 귀납적 정의, Recurrence Relation 점화식
함수 호출(시스템 스택)으로 인해 반복보다 느림
대부분 동일 기능의 반복 구조로 변환 가능

귀납적 정의

팩토리얼 n!
기본조항 f(0) = 1
귀납조항 f(n) = n * f(n-1), n >= 1

자연수 n
기본조항 n ∈ N
귀납조항 (n-1) ∈ N 이면, n ∈ N, n >= 2

피보나치 수열 fib(n)
0, n = 0
1, n = 1
fib(n-1) + fib(n-2), n >= 2

중복작업
I.E. f(3) 의 중복 계산
f(5) = f(4) + f(3)
f(4) = f(3) + f(2)

순환호출
→ 호출 시 비용
→ 중복 실행

@ U 중간고사 출제 : 표 채우기 (주어진 문제, 문제를 분할 정복으로 풀었을 때 부문제 수, 부문제 크기, 불한 시간, 합병 시간, 합병 정렬)

분할정복

Divide 문제를 부문제로 분할 (어디까지 어떻게 몇 개로 나눌지는 재량)
Conquer 재귀적으로 해결
Combine 결합 (필요하다면)

마스터정리
a = 부문제 수, n/b = 부문제 크기, O(n^c) = 분할 결합 시간
a = b^c : T(n) = O(n^c log n)
a > b^c : T(n) = O(n^d), d = log_b a
a < b^c : T(n) = O(n^c)

이진탐색
나누고 하나만 씀, 부문제 1개 = 결합 X
a = 1, b = 2, c = 0
a = b^c, T(n) = O(n^c log n) = O(log n)
순환호출 트리의 높이 log₂n에 비례

최대값 찾기
Like 이진탐색, 토너먼트 방식
배열을 반으로 나눠 각 최대값 구하고, 더 큰 값을 최대값으로
a = 2, b = 2, c = 0
a > b^c, T() = O(n^d), d = log_ba = 1 = θ(n)

거듭제곱 power(x, n)

IN 순환 알고리듬
1, n = 0
x * power(x, n-1), n >= 1

IN 분할정복 알고리듬
1, n = 0
power(x^2, n/2), n != odd
x * power(x^2, (n-1)/2), n = odd
a = 1, b = 2, c = 0
a = b^c, T(n) = θ(n^c log n) = θ(log n)

감소 정복?
이진탐색인 거듭제곱 처럼 부문제를 만들때 크기를 줄이는

TODO : 합병 정렬~

제자리 정렬인가 아닌가?
→ 일반적 관점) O
→ 엄근진 관점) 추가 공간 쓰는 ~를 쓰면 X

Stable한가 안한가?
Stable 하다

@ U 중간고사 출제 : 주어진 배열에 퀵 정렬을 적용한 초행 결과를 적고, 이를 바탕으로 퀵 정렬이 안정적인지 설명하시오. ‘안정적이다’ 라는 것이 어떤 의미인지 설명하시오. 퀵 정렬의 최악/최선 복잡도를 적으시오.
-> 퀵 안정적이지 않다, 는 무슨 의미냐면 똑같은 값의 순서가 그대로 유지되지 않는다

TODO : 퀵 정렬~

최악의 경우 ~

제자리 정렬인가 아닌가?
→ 일반적 관점) 추가 공간이 없으니까 O (단순 변수 제외)
→ 엄근진 관점) 재귀적으로 돌리면 시스템 스택에 쌓이니까.. X

Stable한가 안한가?
Stable 하지 않다

THRESHOLD - 임계값

낮추면 나눌 수 있을 때/풀기 쉬울 때까지 나누고 해결하겠다 (실제로는 아무것도 안함)
불필요한 함수 호출을 피하기 위해 함수 호출 전제 점검
→ 조건문이 많아져서 코드가 지저분해짐

높히면
어느 정도 크기의 문제라돋 풀 수 있는 거는 풀겠다
→ 아무 일도 안하는 순환호출 오버헤드 회피, 효율성 증가

효율성 극대화하기 위해 하이브리드 알고리듬
→ 작은 개수에서 빠름 : 퀵 + 삽입
→ 많은 개수에서 빠름 : Steam Sort? 합병 + 삽입, 대부분의 Python/Java 알고리듬
→ C는 퀵

@ U 중간고사 출제 : 트로미노

트로미노 타일로 체스판 채우기

타일 한 개를 모노미노 (Like 모노레일)
타일 두 개를 도미노
타일 세 개를 트로미노
타일 네 개를 테트로미노 (Like 테트리스)

구멍이 하나 있는 2^k * 2^k 체스판을,
L 모양의 트로미노 Tromino 타일로 채울 수 있는가?

수학적 귀납법
→ 도미노를 쓰러뜨리는 것
→ 작은 것으로 시작해서 큰 문제를

8 * 8 가능,
일반적으로는 가능할까?

가장 작은 크기의 부문제,
구멍이 하나 있는 2^1 * 2^1 체스판
어느 곳에 구멍이 있더라도 체스판 채우기 가능

구멍이 하나 있는 2^k * 2^k 체스판에서,
구멍이 하나 있는 2^1 * 2^1 체스판으로,
문제를 줄여나갈 수 있다면 분할정복 알고리듬으로 해결 가능

→ 판을 4개의 정사각형으로 분할
→ 구멍이 포함된 정사각형을 제외하고, 나머지 정사각형을 있는 트로미노 배치
→ 최소 (2^1 * 2^1) 까지 Loop

부문제 수 : 4
문제의 크기 : 절반 (주의 1/4 아님)