Divide and Conquer(분할 정복)

분할 정복(Divide and Conquer)은 큰 문제를 작은 부분 문제로 분할하여 해결하는 알고리즘 설계 패러다임입니다.
이 패러다임은 문제를 더 작은 하위 문제로 분할한 다음, 각 하위 문제를 재귀적으로 해결하고, 그 결과를 합쳐서 원래 문제의 해를 얻는 방식으로 동작합니다.
이러한 분할 정복 접근 방식은 문제를 더 작고 관리하기 쉬운 부분으로 나누어서 효과적으로 해결하는 데 사용됩니다.

분할 정복 알고리즘은 보통 다음의 세 단계로 진행됩니다.

1. 분할(Divide): 주어진 문제를 더 작은 하위 문제로 분할합니다. 이때, 하위 문제는 원래 문제와 구조적으로 유사해야 합니다.

2. 정복(Conquer): 작은 하위 문제들을 재귀적으로 해결합니다. 이 단계에서 하위 문제의 크기가 충분히 작아질 때까지 알고리즘이 반복됩니다.

3. 결합(Combine): 작은 하위 문제들의 해를 결합하여 원래 문제의 해를 구합니다. 이 단계에서 작은 하위 문제들의 해를 합치거나 조합하여 최종 결과를 얻습니다.

예

아래 예시는 1부터 10까지의 합을 분할 정복을 사용하여 구하는 예시 코드입니다.

def divide_and_conquer_sum(start, end):
    if start == end:
        return start
    else:
        mid = (start + end) // 2
        left_sum = divide_and_conquer_sum(start, mid)
        right_sum = divide_and_conquer_sum(mid + 1, end)
        return left_sum + right_sum

# 예시: 1부터 10까지의 합
result = divide_and_conquer_sum(1, 10)
print("1부터 10까지의 합:", result)

위의 코드의 과정은 아래와 같습니다.

첫 번째 호출: divide_and_conquer_sum(1, 10)

• mid = 5
• left_sum = divide_and_conquer_sum(1, 5)
• right_sum = divide_and_conquer_sum(6, 10)
• return 15 + 40 = 55

divide_and_conquer_sum(1, 5) 호출

• mid = 3
• left_sum = divide_and_conquer_sum(1, 3)
• right_sum = divide_and_conquer_sum(4, 5)
• return 6 + 9 = 15

divide_and_conquer_sum(1, 3) 호출

• mid = 2
• left_sum = divide_and_conquer_sum(1, 2)
• right_sum = divide_and_conquer_sum(3, 3) (기본 케이스: return 3)
• return 3 + 3 = 6

divide_and_conquer_sum(1, 2) 호출

• mid = 1
• left_sum = divide_and_conquer_sum(1, 1) (기본 케이스: return 1)
• right_sum = divide_and_conquer_sum(2, 2) (기본 케이스: return 2)
• return 1 + 2 = 3

divide_and_conquer_sum(4, 5) 호출

• mid = 4
• left_sum = divide_and_conquer_sum(4, 4) (기본 케이스: return 4)
• right_sum = divide_and_conquer_sum(5, 5) (기본 케이스: return 5)
• return 4 + 5 = 9

divide_and_conquer_sum(6, 10) 호출

• mid = 8
• left_sum = divide_and_conquer_sum(6, 8)
• right_sum = divide_and_conquer_sum(9, 10)
• return 21 + 19 = 40

이하 과정도 비슷한 방식으로 계속되어, 최종 결과로 55를 얻게 됩니다.

이 코드의 세 단계는 다음과 같습니다.

1. 분할(Divide):

• 주어진 범위는 1부터 10까지입니다.
• 범위를 두 개의 하위 범위로 분할합니다. 중간 값인 5를 기준으로 왼쪽 범위는 1부터 5까지, 오른쪽 범위는 6부터 10까지가 됩니다.

2. 정복(Conquer):

• 왼쪽 범위인 1부터 5까지의 합을 구합니다.
  • 이를 위해 재귀를 사용해 분할(Divide)과정을 다시 거칩니다.
• 오른쪽 범위인 6부터 10까지의 합을 구합니다.

3. 결합(Combine):

• 왼쪽 범위와 오른쪽 범위의 합을 합칩니다.
  • 15 + 40 = 55

Brute Force(무차별 대입)

brute force 방법은 문제를 해결하기 위해 가능한 모든 경우의 수를 탐색하는 방식입니다. 이 방식은 일반적으로 효율성이 떨어질 수 있지만, 모든 경우를 체크하기 때문에 정확한 답을 찾을 수 있습니다.

1. 접근 방법: 가능한 모든 조합을 생성하거나 탐색합니다.
2. 효율성: 일반적으로 느리며, 복잡도가 높을 수 있습니다. 대부분의 경우, 시간 복잡도는 O(n!) 또는 O(2^n)입니다.
3. 적용 분야: 정확한 답이 필요하고, 입력 크기가 작은 경우에 사용할 수 있습니다.

예

두 숫자 중 두 개를 선택하여 합이 목푯값과 같은 경우를 찾는 예시 코드입니다.

Python

def findSumPairBruteForce(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i + 1, n):
            if nums[i] + nums[j] == target:
                return True
    return False

numbers = [2, 4, 7, 11, 15]
target_sum = 9
print(findSumPairBruteForce(numbers, target_sum))  # True

관련 문제 1

정수로 이루어진 두 리스트가 주어집니다. 왼쪽 리스트에서 하나의 숫자를 선택하고, 오른쪽 리스트에서 하나의 숫자를 선택하여 두 수를 곱했을 때, 가장 작은 곱을 구하시오.

해답

함수 min_product는 리스트 left_numbers와 리스트 right_numbers를 파라미터로 받습니다. left_numbers는 왼쪽 리스트의 숫자들, right_numbers는 오른쪽 리스트의 숫자들이 담겨 있고, min_product는 left_numbers에서 숫자 하나와 right_numbers에서 숫자 하나를 뽑아서 곱했을 때 그 값이 최소가 되는 값을 리턴합니다.

def min_product(left_list: list, right_list: list) -> int:
    min_result = float("inf")
    for left in left_list:
        for right in right_list:
            current_result = left * right
            min_result = min(min_result, current_result)
    return min_result


# 테스트 코드
if __name__ == "__main__":
    print(min_product([1, 3, 4], [3, 4, 5]))    # 3
    print(min_product([-3, 4, -9], [3, -2, 1])) # -27

위의 코드는 주어진 두 리스트에서 각각 하나의 숫자를 선택하여 곱을 구하고, 그중에서 가장 작은 곱을 찾는 방식으로 문제를 해결합니다. 위의 예시 입력에 대해서는 가장 작은 곱을 구할 수 있습니다.

Java

public class ProductCalculator {  
    public static int minProduct(int[] leftList, int[] rightList) {  
        int minResult = Integer.MAX_VALUE;  
        for (int left : leftList) {  
        for (int right : rightList) {  
            int currentResult = left * right;  
            minResult = Math.min(minResult, currentResult);  
        }  
    }  
    return minResult;  
}  

    public static void main(String[] args) {  
        int[] leftList = {1, 3, 4};  
        int[] rightList = {3, 4, 5};  
        System.out.println(minProduct(leftList, rightList)); // 3  

        int[] leftList2 = {-3, 4, -9};  
        int[] rightList2 = {3, -2, 1};  
        System.out.println(minProduct(leftList2, rightList2)); // 27  
    }  
}

관련 문제 2

좌표 리스트에서 거리가 가장 먼 두 2차원 좌표를 찾으시오.
주어진 2차원 좌표 리스트에서 거리가 가장 먼 두 좌표를 찾아서 그 좌표 쌍을 반환하는 함수 farthest_coordinates(coordinates)를 작성하세요. 각 좌표는 튜플로 주어지며, x와 y 좌표값은 양의 정수로 가정합니다.

def farthest_coordinates(coordinates: list[tuple[int, int]]) -> list[tuple[int, int]]:  
    # 코드 구현  


if __name__ == "__main__":  
    test_coordinates = [(4, 1), (1, 30), (34, 50), (5, 3), (13, 19), (32, 4)]  
    print(farthest_coordinates(test_coordinates))

해답

두 점 사이의 거리

두 점 사이의 거리는 아래 공식을 통해서 구할 수 있습니다.

distance = √((x₂ - x₁)² + (y₂ - y₁)²)

이를 코드화하면 아래와 같습니다.

from math import sqrt

sqrt((coord1[0] - coord2[0]) ** 2 + (coord1[1] - coord2[1]) ** 2)

그리고 이 거리를 구하는 코드는 반복해서 사용해야 하기에 아래처럼 메서드로 분리합니다.

def distance(coord1: tuple[int, int], coord2: tuple[int, int]) -> float:
    return sqrt((coord1[0] - coord2[0]) ** 2 + (coord1[1] - coord2[1]) ** 2)

최댓값 구하기

이중 루프를 통해 각각의 좌표 쌍의 거리를 계산하면서, 현재까지 가장 먼 거리를 갖는 좌표 쌍과 거리를 업데이트합니다.

def farthest_coordinates(coordinates: list[tuple[int, int]]) -> list[tuple[int, int]]:  
    farthest_pair: list[tuple[int, int]] = [coordinates[0], coordinates[1]]  
    max_distance: float = distance(coordinates[0], coordinates[1])  

    for i in range(len(coordinates) - 1):  
        for j in range(i + 1, len(coordinates)):  
            coord1: tuple[int, int] = coordinates[i]  
            coord2: tuple[int, int] = coordinates[j]  
            cur_distance: float = distance(coord1, coord2)  

            if cur_distance > max_distance:  
                farthest_pair = [coordinates[i], coordinates[j]]  
                max_distance = cur_distance  

    return farthest_pair

python

from math import sqrt  


def distance(coord1: tuple[int, int], coord2: tuple[int, int]) -> float:  
    return sqrt((coord1[0] - coord2[0]) ** 2 + (coord1[1] - coord2[1]) ** 2)  


def farthest_coordinates(coordinates: list[tuple[int, int]]) -> list[tuple[int, int]]:  
    farthest_pair: list[tuple[int, int]] = [coordinates[0], coordinates[1]]  
    max_distance: float = distance(coordinates[0], coordinates[1])  

    for i in range(len(coordinates) - 1):  
        for j in range(i + 1, len(coordinates)):  
            coord1: tuple[int, int] = coordinates[i]  
            coord2: tuple[int, int] = coordinates[j]  
            cur_distance: float = distance(coord1, coord2)  

            if cur_distance > max_distance:  
                farthest_pair = [coordinates[i], coordinates[j]]  
                max_distance = cur_distance  

    return farthest_pair  


if __name__ == "__main__":  
    test_coordinates = [(4, 1), (1, 30), (34, 50), (5, 3), (13, 19), (32, 4)]  
    print(farthest_coordinates(test_coordinates))  # [(4, 1), (34, 50)]

java

public class FarthestCoordinates {  
    public static double distance(int[] coord1, int[] coord2) {  
        return Math.sqrt(Math.pow(coord1[0] - coord2[1], 2) + Math.pow(coord1[1] - coord2[1], 2));  
    }  

    public static int[][] farthestCoordinates(int[][] coordinates) {  
        int[][] farthestPair = {coordinates[0], coordinates[1]};  
        double maxDistance = distance(coordinates[0], coordinates[1]);  

        for (int i = 0; i < coordinates.length - 1; i++) {  
            for (int j = i + 1; j < coordinates.length; j++) {  
                int[] coord1 = coordinates[i];  
                int[] coord2 = coordinates[j];  
                double curDistance = distance(coord1, coord2);  

                if (curDistance > maxDistance) {  
                    farthestPair[0] = coordinates[i];  
                    farthestPair[1] = coordinates[j];  
                    maxDistance = curDistance;  
                }  
            }  
        }  

        return farthestPair;  
    }  

    public static void main(String[] args) {  
        int[][] testCoordinates = {{4, 1}, {1, 30}, {34, 50}, {5, 3}, {13, 19}, {32, 4}};  
        int[][] result = farthestCoordinates(testCoordinates);  
        for (int[] coord : result) {  
            System.out.print("(" + coord[0] + ", " + coord[1] + ") ");  
        }  
        // (4, 1) (34, 50)
    }  
}

재귀 함수(Recursive Function)이란?

재귀 함수는 함수 내에서 자기 자신을 다시 호출하는 함수를 의미합니다. 이를 통해 반복적인 작업을 수행할 수 있습니다.

재귀 함수의 구조

def 재귀함수():
    if 종료_조건:
        return 결과
    ...
    재귀함수()
    ...

예

팩토리얼은 재귀 함수의 대표적인 예시입니다.

def factorial(n):
    if n == 1:
        return 1
    return n * factorial(n - 1)

factorial(5)를 호출한다고 가정하면, 아래와 같은 과정을 거치게 됩니다.

1. 첫 번째 호출: factorial(5)가 호출됩니다.
   • n = 5이므로, 5 * factorial(4)를 반환해야 합니다.
   • factorial(4)를 호출하기 위해 다음 단계로 넘어갑니다.
2. 두 번째 호출: factorial(4)가 호출됩니다.
   • n = 4이므로, 4 * factorial(3)를 반환해야 합니다.
   • factorial(3)를 호출하기 위해 다음 단계로 넘어갑니다.
3. 세 번째 호출: factorial(3)가 호출됩니다.
   • n = 3이므로, 3 * factorial(2)를 반환해야 합니다.
   • factorial(2)를 호출하기 위해 다음 단계로 넘어갑니다.
4. 네 번째 호출: factorial(2)가 호출됩니다.
   • n = 2이므로, 2 * factorial(1)를 반환해야 합니다.
   • factorial(1)를 호출하기 위해 다음 단계로 넘어갑니다.
5. 다섯 번째 호출: factorial(1)이 호출됩니다.
   • n = 1이므로, 1을 반환합니다.

각 단계에서 반환된 값을 거꾸로 계산하면 아래와 같습니다.

1. factorial(1) = 1
2. factorial(2) = 2 * 1 = 2
3. factorial(3) = 3 * 2 = 6
4. factorial(4) = 4 * 6 = 24
5. factorial(5) = 5 * 24 = 120

장단점

장점

1. 코드의 간결성: 재귀 함수를 사용하면 복잡한 알고리즘도 간결하게 표현할 수 있습니다.
2. 수학적 정의와 가깝다: 재귀적인 수학적 정의를 바로 코드로 옮길 수 있어 이해하기 쉽습니다.

   단점

3. 메모리 사용: 각 함수 호출마다 스택 메모리에 정보가 저장되므로 메모리 사용이 증가할 수 있습니다.
   -> 글 하단의 python에서의 재귀 호출의 깊이 제한 참고
4. 속도: 일반적인 반복문에 비해 함수 호출 오버헤드로 인해 속도가 느릴 수 있습니다.
   -> 글 하단의 함수 호출 오버헤드 참고

참고

python에서의 재귀 호출의 깊이 제한

python에서는 재귀 호출의 깊이에 제한을 두어 메모리의 오버플로우를 방지합니다. 이 제한은 시스템에 따라 다르나, 기본적으로는 1000번의 재귀 호출이 제한됩니다.

만약 이 제한을 변경하고 싶다면, sys 모듈의 setrecursionlimit함수를 사용해 변경할 수 있습니다.

import sys

sys.setrecursionlimit(2000)

이러면 최대 재귀 깊이를 2000으로 수정할 수 있습니다.

함수 호출 오버헤드란

함수 호출 오버헤드는 함수를 호출할 때 발생하는 추가적인 작업으로 인해 소요되는 시간과 리소스를 말합니다. 특히 재귀 함수와 같이 함수 호출이 연쇄적으로 발생하는 경우, 함수 호출 오버헤드는 성능에 영향을 미칠 수 있습니다.

삽입 정렬 알고리즘(insertion sort algorithm)

삽입 정렬(insertion sort)은 리스트를 반복하면서 각 항목을 이미 정렬된 부분 리스트의 올바른 위치에 "삽입"함으로써 동작합니다.

1. 리스트의 두 번째 항목에서 시작하여 왼쪽의 항목과 비교합니다.
2. 현재 항목이 왼쪽 항목보다 작으면 왼쪽 항목을 오른쪽으로 이동시킵니다.
3. 이를 현재 항목이 왼쪽 항목보다 크거나 왼쪽에 더 이상 항목이 없을 때까지 반복합니다.
4. 그런 다음 현재 항목을 마지막으로 비어 있는 위치에 삽입합니다.
5. 이 과정을 리스트의 모든 항목에 대해 반복합니다.

이를 파이썬 코드로 구현하면 다음과 같습니다:

def insertion_sort(arr: list[int]) -> list[int]:
    # 배열 전체를 반복하면서
    for i in range(1, len(arr)):
        key: int = arr[i]

        # 이미 정렬된 배열 부분에서 올바른 위치를 찾아가는 과정
        j: int = i - 1
        while j >=0 and key < arr[j] :
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

    return arr


if __name__ == "__main__":
    arr: list[int] = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
    print(insertion_sort(arr))
    # [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

예를 들어, 이 함수에 [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5] 배열을 전달하면,
3 과 1을 비교하고, 1 이 더 작으므로 순서를 바꿉니다. [1, 3, 4, 1, 5, 9, 2, 6, 5, 3, 5] 이렇게 바뀐 이후 3번째 인덱스인 4 를 비교하기 시작합니다. 4는 1 보다 크므로 지나가고, 3 보다 크므로 지나갑니다. 이런 식으로 배열의 마지막 인덱스까지 정렬을 진행합니다.

삽입 정렬의 시간 복잡도는 최악의 경우 O(n^2)입니다. 그러나 리스트가 이미 거의 정렬되어 있는 경우 삽입 정렬은 매우 효율적일 수 있으며, 이 경우 시간 복잡도는 O(n)이 됩니다.

선택 정렬 알고리즘(selection sort)

1. 리스트 중에서 최소값을 찾습니다.
2. 그 값을 리스트의 맨 앞에 위치한 값과 바꿉니다.
3. 맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복합니다.

Python 코드

def selection_sort(arr: list[int]) -> list[int]:
    length: int = len(arr)
    # 배열 전체를 반복하면서
    for index_1 in range(length):
        min_index: int = index_1
        # 현재 위치에서 가장 작은 원소를 찾습니다.
        for index_2 in range(index_1 + 1, length):
            if arr[min_index] > arr[index_2]:
                min_index = index_2

        # 가장 작은 원소와 현재 원소를 교환합니다.
        arr[index_1], arr[min_index] = arr[min_index], arr[index_1]

    return arr


if __name__ == "__main__":
    arr: list[int] = [3, 1, 4, 9, 5, 7, 5]
    print(selection_sort(arr))
    # [1, 3, 4, 5, 5, 7, 9]

예를 들어, 이 함수에 [3, 1, 4, 9, 5, 7, 5] 배열을 전달하면,
3 과 1 을 비교해 1 이 더 작으므로 min_index은 0에서 1 의 위치정보인 1로 바뀝니다. 그리고 나머지 숫자들과 차례대로 비교합니다.
그러면 배열이 [1, 3, 4, 9, 5, 7, 5] 로 바뀝니다.
이러한 과정을 반복하면 배열 [1, 3, 4, 5, 5, 7, 9] 이라는 결과가 나옵니다.

선택 정렬의 시간 복잡도는 O(n^2)입니다. 이는 리스트의 모든 요소를 한 번씩 검사해야 하기 때문이며, 따라서 큰 리스트에서는 매우 느릴 수 있습니다.