분할 정복의 기본 개념 다지기

1. 분할 정복(divide and conquer)

 

분할 = 큰 문제를 여러 개의 작은 문제로 쪼갠 다음

 

정복 = 작은 문제들의 답을 이용해 큰 문제의 답을 구하는 방법

 

 

 

 

충분히 크기가 큰 문제를 쉽게 해결할 수 있는 부분 문제로 분할해 나가고, 

 

분할된 하위 문제를 해결하여 이 결과를 조합하여 윗단계 문제에 대한 답으로 낸다

 

 

2. 방법

 

정답을 쉽게 도출할 수 있을 때까지 재귀적으로 분할된 단위로 자신을 호출하면서 범위를 조금씩 줄여나감(분할단계)

 

답을 쉽게 도출하는 단계까지 도달한다면 재귀함수는 정답을 return하고 

 

이렇게 return하면서 이를 이용해 재귀 stack에 쌓인 윗단계 재귀함수의 값을 return해나가는 것이 정복단계 

 

def f(x):
    
    if (f(x)가 간단함):
        return f(x)
    
    else:
        
        x를 x1,x2로 분할
        
        return f(x1), f(x2)로 f(x)를 계산

 

결국 어떻게 분할하고 설계하느냐에 따라 성능의 차이가 매우 크다.

 

당연히 이렇게 설계하는 과정이 매우 어렵다.

 

이렇게 분할정복으로 해결하면 효율적인 문제들이 분명 있지만,

 

재귀를 사용하기 때문에 과도한 메모리 사용, 스택 오버플로우 등으로 오히려 비효율적일 수 있다.

 

과도한 메모리 사용은 메모이제이션 기법으로 속도를 해결할 수도 있다.

 

 

3. 연습문제

 

4779번: 칸토어 집합 (acmicpc.net)

4779번: 칸토어 집합

 

 

4. 풀이

 

방법이 친절하게 나와있는데...

 

 

 

 

처음부터 시작하면 바로 정답을 내기 매우 어렵다..

 

n이 주어졌을때 뭘 출력해야할지 모른다 말이지

 

하지만 그림을 보면 마치 분할 정복 과정과 비슷하다

 

n = 0이면 정답은 "-"인건 바로 알 수 있다. 그래서 n = 0까지 분할하는걸 목표로 한다.

 

3**n인 문자열에서 3등분해서 (1/3만큼 "-"출력) + (1/3만큼 공백 출력) + (1/3만큼 "-" 출력) 형태라는 걸 알 수 있다.

 

그러니까 3**n을 1/3씩 계속 줄여나가면서 3**n이 1이면 "-"을 출력하고

 

아니라면 (1/3 로 줄여나감) + (1/3 공백) + (1/3 로 줄여나감)을 출력하면 된다

 

from sys import stdin

def cantor(n):
    
    if n == 1:
        
        return '-'
    
    else:
        
        return cantor(n//3) + ' '*(n//3) + cantor(n//3)

while 1:
    
    try:

        n = int(stdin.readline())

        print(cantor(3**n))

    except:
        
        break

 

 

근데 결과가 왜 나오는지 신기하긴 하네..

 

재귀함수는 진짜 어렵다.. 연습이 더 필요하겠는데