728x90
반응형
분할 정복(Divide and Conquer)은 여러 알고리즘의 기본이 되는 알고리즘.
개념은 큰 문제를 점차 작은 문제로 나누어 가면서 풀 수 있는 최소단위 문제로 해결하고, 이를 다시 합쳐서 해결하는 것
절차
1) 분할 (Divide)
- 2개 이상의 문제들로 분리. 더이상 분할할 수 없을 때까지 동일한 여러 하위 문제로 나눔,
2) 정복 (Conquer)
- 나누어진 작은 문제를 해결.
3) 조합 (Combine)
- 해결한 문제들을 합침. 하위 문제의 결과를 원래 문제에 대한 결과로 조합(합침)
# 1~n까지의 합
def func_sum(s, e): # start, end
if s == e:
return s # 정보(해결): 가장 작은 문제의 해결 리턴
mid = (s + e) // 2 # 분할 조건 : 어떤 조건으로 분할 하는가?
# *분할 : 2개 이상의 작은 문제로 분할(2개의 합수로 분리(재귀). *조합: 작은 문제해결 결과를 조합(합침. + 로 결과 합침)
return func_sum(s, mid) + func_sum(mid + 1, e)
print(func_sum(1, 100))
728x90
반응형
'프로그램' 카테고리의 다른 글
[파이썬] 문제 : 두 수 입력받아 사칙연산 함수 만들기 (0) | 2022.11.18 |
---|---|
[파이썬] 문제 : [1,1..0.5,05]리스트 컴프리헨션 코드 만들기 (0) | 2022.11.18 |
[파이썬] 문제 : 두 문자열을 입력 받아 일치하는 문자열 겹치기 (0) | 2022.11.14 |
[파이썬] 문제 : 가변인수로 받은 값으로 정렬 (0) | 2022.11.14 |
[파이썬] 문제 : 완전수 판단 (0) | 2022.11.14 |
댓글