DC | Divide-Conquer | 분할 정복
@ N~차시
@ N+1차시
@ Chapter 3
@ 재귀
💫 정의
- 기본 단계를 해결합니다. 이 부분은 가능한 한 간단한 문제이어야만 합니다.
- 문제가 기본 단계가 될 때까지 나누거나 작게 만듭니다.
🫧 _
@ 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 중간고사 출제 : 표 채우기 (주어진 문제, 문제를 DC로 풀었을 때 부문제 수, 부문제 크기, 불한 시간, 합병 시간, 합병 정렬)
DC
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 = logb 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)
순환호출 트리의 높이 log2n에 비례
최대값 찾기
Like 이진탐색, 토너먼트 방식
배열을 반으로 나눠 각 최대값 구하고, 더 큰 값을 최대값으로
a = 2, b = 2, c = 0
a > b^c, T() = O(n^d), d = logba = 1 = θ(n)
거듭제곱 power(x, n)
IN 순환 알고리듬
1, n = 0
x * power(x, n-1), n >= 1
IN DC
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 체스판으로,
문제를 줄여나갈 수 있다면 DC로 해결 가능
→ 판을 4개의 정사각형으로 분할
→ 구멍이 포함된 정사각형을 제외하고, 나머지 정사각형을 있는 트로미노 배치
→ 최소 (2^1 * 2^1) 까지 Loop
부문제 수 : 4
문제의 크기 : 절반 (주의 1/4 아님)
- DC
- 부문제의 정복은 순환호출에 의존
- 부문제는 해결되었다고 보고 부문제를 어떻게 풀지 고민하지 않음
- 순환적 사고의 장점이고 DC가 갖는 외형적 단순함의 근원
- 효율성 문제를 보완하려면 (시스템) 스택의 순환 구조를 (명시적) 스택의 반복 구조로 변환
- DC를 쓰면 좋지 않은 경우?
- 부문제의 크기가 커지는 경우
- 현실적으로 없는
- 두 개 이상의 부문제로 나누어지지만, 부문제의 크기가 거의 변하지 않는 경우
- 피보나치 수열 계산 알고리즘: 두 개의 부문제로 나누어지지만, 각 부문제의 크기는 n-1과 n-2
- 문제 특성상 O(2n)의 복잡도를 갖는다면 DC 기법을 배제할 필요는 없음(하노이탑)
- 동일한 부문제들이 자주 등장하는 경우 (중첩,재활용)
- DC는 모든 부문제들을 독립적으로 해결: 부문제들이 중첩되는 경우 비효율적
- 피보나치 수열 문제는 부문제의 크기도 조금씩 줄어들고 동일한 부문제들도 자주 등장
- 상대적으로 높은 복잡도의 가능성이 있는 문제들의 유형
- 부문제의 크기가 줄어들지만 부문제의 크기를 모두 합하면 문제의 크기보다 커지는 경우
- 상대적으로 낮은 로그형이나 선형의 복잡도를 가질 수 없음
- 체스판 채우기 알고리즘: 부문제가 4개 이고 부문제의 크기의 합이 원래 문제 크기의 2배
- 부문제의 크기가 커지는 경우