분할정복

분할 정복

 

분할 정복이란 커다란 문제를 작은 부분 부분으로 나누어서 해결하는 방법입니다. 분할 정복의 전략은 재귀적 알고리즘을 사용하여 해결할 수 있습니다. 먼저 분할 정복을 하기 위해서는 두 가지 단계를 거칩니다.

 

1. 기본 단계를 해결합니다. 이 부분은 가능한 한 간단한 문제여야 합니다.

2. 문제가 기본 단계가 될 때까지 나누거나 작게 만들어야 합니다.

 

이것을 프로그래밍으로 표현하자면 다음과 같이 표현할 수 있습니다.

 

function F(x):
    if F(x)가 간단 then:
    return F(x)를 계산한 값
    else:
    x 를 x1, x2로 분할 F(x1)과 F(x2)를 호출
    return F(x1), F(x2)로 F(x)를 구한 값

 

분할 정복 예시 코드

 

분할 정복 간단코드 (더하기)

 

분할 정복을 쉽게 이해하기 위해 재귀를 이용한 더하기 코드는 다음과 같습니다.

 

def sum(lst):
    if lst == []:
        return 0
    else:
        print(f"sum({lst[:]}) = {lst[0]} + sum({lst[1:]})")
        return lst[0] + sum(lst[1:])

print(sum([1,2,3,4,5]))

 

그러면 출력 값은 다음과 같습니다.

 

 

먼저 sum([5])의 값은 5 + 0 이므로 5 입니다.

다음은 sum([4,5])의 값입니다. 이것은 4 + sum([5])이므로 sum([5])가 5여서 4 + 5 이므로 9입니다.

쭉~~~ 계산하다 보면

sum([1,2,3,4,5]) = 15가 나오는 것을 확인할 수 있습니다.

 

분할 정복 간단 코드 (카운트)

 

분할 정복을 이용한 카운트 코드는 다음과 같습니다.

 

# 리스트에 포함된 원소의 숫자를 세는 재귀 함수를 작성하기
def count_lst(lst):
    if lst == []:
        return 0
    else:
        print(f"count_lst({lst[:]}) = 1 + count_lst({lst[1:]})")
        return 1 + count_lst(lst[1:])

print(count_lst([1,2,3,4,1]))

 

그러면 출력 값은 다음과 같습니다.

 

 

---

 

위에서 나온 예시 코드는 아래의 책을 참고해서 작성 하였습니다.

 

https://www.hanbit.co.kr/store/books/look.php?p_code=B5896248244

Hello Coding 그림으로 개념을 이해하는 알고리즘 - 비전공자도 볼 수 있는 헬로 코딩