분할정복(Divide and Conquer) 알고리즘은 큰 문제를 작은 문제로 분할한 후, 각 작은 문제를 해결하고, 이를 합쳐서 큰 문제를 해결하는 알고리즘입니다. 파이썬에서는 다음과 같이 분할정복 알고리즘을 구현할 수 있습니다.

예제: 이진 탐색

주어진 정렬된 리스트에서 특정한 값의 위치를 찾는 문제입니다. 이진 탐색은 리스트의 중간 위치의 값을 검사하여 찾고자 하는 값이 리스트의 중간 위치보다 큰지 작은지를 비교하여 검색 범위를 절반으로 줄여가면서 값을 찾아갑니다.

def binary_search(lst, x):
    start = 0
    end = len(lst) - 1
    while start <= end:
        mid = (start + end) // 2
        if lst[mid] == x:
            return mid
        elif lst[mid] > x:
            end = mid - 1
        else:
            start = mid + 1
    return -1

# 정렬된 리스트에서 5의 위치 찾기
lst = [1, 3, 5, 7, 9]
x = 5
print(binary_search(lst, x))  # 출력 결과: 2

위 코드에서 binary_search() 함수는 주어진 정렬된 리스트 lst에서 값을 찾는 이진 탐색 알고리즘을 구현합니다. 검색 범위를 나타내는 변수 start와 end를 초기화하고, 반복문을 통해 검색 범위를 절반씩 줄여나가면서 값을 찾습니다. 중간 위치의 값을 mid에 저장하고, 찾고자 하는 값 x와 비교하여 검색 범위를 조절합니다. 값을 찾으면 해당 위치를 리턴하고, 값이 없으면 -1을 리턴합니다.