> For the complete documentation index, see [llms.txt](https://mellona-log.gitbook.io/log/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mellona-log.gitbook.io/log/algorithm-datastructure/algorithm/undefined-4.md).

# 동적 계획법과 분할정복

## 1. 동적 계획법(DP)

> 동적 계획법으로 문제를 풀 때는, 우선 작은 문제부터 해결해나가보는 것이 좋다. 작은 문제들을 풀어나가다보면 이전에 구해둔 더 작은 문제들이 활용되는 것을 확인하게 된다. 이에 대한 규칙을 찾았을 때 **점화식**을 도출해내어 동적 계획법을 적용시키자

### 🍌 개념

> 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법, 작은 하위 문제의 해를 저장하고 활용하여 중복 계산을 피하며 문제를 해결하는 데 중점

* 입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제의 해를 활용해서, 보다 큰 크기의 부분 문제를 해결, 최종적으로 전체 문제를 해결하는 알고리즘
* **상향식 접근법**으로, 가장 최하위 해답을 구한 후, 이를 저장하고, 해당 결과값을 이용해서 상위 문제를 풀어가는 방식
* 한 가지 문제에 대해서, 단 한번만 풀도록 만들어주는 알고리즘
  * 즉, **똑같은 연산을 반복하지 않도록 만들어준다.** 실행시간을 줄이기 위해 사용되는 수학적 접근 방식의 알고리즘
* `Memoization` 기법을 사용함

### 🍌 접근 방식

* 커다란 문제를 쉽게 해결하기 위해 작게 쪼개서 해결하는 방법인 분할 정복과 매우 유사하지만 **간단한 문제로 만드는 과정에서 중복 여부에 대한 차이점**이 존재한다.
* 즉, 동적 계획법은 간단한 작은 문제들 속에서 `계속 반복되는 연산`을 활용하여 빠르게 풀 수 있는 것이 핵심

### 🍌 종류

1. 피보나치 수열
2. 배낭 문제
3. 최장 공통 부분 수열
4. 최단 경로 문제
5. 최소 거스름돈 문제
6. 매트릭스 체인 곱셈
7. 행렬 경로 문제

### 🍌 Memoization 기법이란?

* Memoization (메모이제이션) 이란: 프로그램 실행 시 이전에 계산한 값을 저장하여, 다시 계산하지 않도록 하여 전체 실행 속도를 빠르게 하는 기술
* 문제를 잘게 쪼갤 때, 부분 문제는 중복되어, 재활용됨

  * 예: 피보나치 수열 1 1 2 3 5 8 …. 1 1로 시작하고 뒤의 모든 항은 바로 앞 두항의 합의 수열

  > 피보나치 수열에서 재귀를 활용하여 풀 경우, 같은 연산을 계속 반복함을 알 수 있다.
  >
  > 이때, `메모이제이션`을 통해 **같은 작업을 되풀이 하지 않도록 구현하면 효율적**이다.

  * return f(n) = f(n-1) + f(n-2)
* 코드\[재귀] : 시간 복잡도 `O(2^n)`

```java
import java.util.Scanner;

public class Fibonacci {
    private static int fibonacci(int n){
        if(n <= 1) return n;
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();

        int result = fibonacci(n);
        System.out.printf("피보나치 수열의 %d번째 값 : %d", n, result);
    }
}
```

* 코드 2\[동적 방법 이용] : 시간 복잡도 `O(N)`

```java
public class Dynamic {
    
    public int dynamicFunc(int data){
        Integer[] cache = new Integer[data+1];
        cache[0] = 0;
        cache[1] = 1;
        for(int index=2; index<data+1; index++){
            cache[index] = cache[index-1] + cache[index-2];
        }
        return cache[data];
    }

    public static void main(String[] args){
        Dynamic dObject = new Dynamic();
        dObject.dynamicFunc(10);
    }
}
```

## 2. 분할 정복

> 분할 정복은 주로 큰 문제를 작은 하위 문제로 나누어 해결하는 데 중점

* 문제를 나눌 수 없을 때까지 나누어서 각각을 풀면서 다시 합병하여 문제의 답을 얻는 알고리즘
* 하양식 접근법으로, 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답을 구하는 방식
  * 일반적으로 재귀함수로 구현
* 문제를 잘게 쪼갤 때, 부분 문제는 서로 중복되지 않음
  * 예: 병합 정렬, 퀵 정렬 등

### 🍌 Merge Sort\[병합 정렬]

관련 동작 방법은 [노션](https://incredible-gem-98e.notion.site/8-22-248bec70cb274c17b0eee9199ab7011e?pvs=4)에..

#### 개념

1. 분할 정복 알고리즘의 하나로, **큰 문제를 작은 문제로 분할하여 해결**하는 방식을 사용하여 정렬을 수행하는 알고리즘
2. 대부분의 경우에 거의 `O(n log n)`의 시간 복잡도를 가지므로 대규모 데이터 정렬에 많이 사용
3. 합병 정렬은 데이터 양이 많아서 메모리를 효율적으로 관리해야 할 때나 안정적인 정렬을 원할 때 주로 선택되는 알고리즘

#### 동작방법

> 아래의 과정을 반복하면서 작은 배열부터 정렬하여 합쳐나가면, 전체 배열이 정렬된 상태가 된다. `합병 정렬`은 **재귀적인 구조**가 되므로, 아래 세 단계를 재귀적으로 수행해 내나가며 정렬이 완성된다.

1. **분할(Divide)** : 정렬할 배열을 반으로 나눈다. 이를 계속해서 작은 배열이 될 때까지 반복적으로 분할
2. **정복(Conquer)** : 분할된 작은 배열을 정렬, 만약 **배열의 길이가 1이거나 0이라면 이미 정렬된 상태**
3. **합병(Merge)** : 정렬된 작은 배열들을 하나로 합병한다. 이때, 두 배열을 비교하여 정렬된 순서대로 합치는데, 작은 값부터 순서대로 병합

```java
import java.util.ArrayList;

public class MergeSort {

    private ArrayList<Integer> mergeFunc(ArrayList<Integer> leftArr, ArrayList<Integer> rightArr) {

        ArrayList<Integer> mergedList = new ArrayList<Integer>();
        int leftPoint = 0;
        int rightPoint = 0;

        // CASE 1 : left/right가 둘 다 있을 때
        while(leftArr.size() > leftPoint && rightArr.size() > rightPoint){
            //자리바꿈이 일어나는 조건
            if(leftArr.get(rightPoint) > rightArr.get(rightPoint)){
                mergedList.add(rightArr.get(rightPoint));
                rightPoint += 1;
            }
            else{
                mergedList.add(leftArr.get(leftPoint));
                leftPoint += 1;
            }
        }

        // CASE 2 : right 데이터가 없을 때
        while(leftArr.size() > leftPoint){
            mergedList.add(leftArr.get(leftPoint));
            leftPoint += 1;
        }

        // CASE 3 : left 데이터가 없을 때
        while(rightArr.size() > rightPoint){
            mergedList.add(rightArr.get(rightPoint));
            rightPoint += 1;
        }

        return mergedList;
  }

    public ArrayList<Integer> margeSplitFunc(ArrayList<Integer> arrayList) {
        if(arrayList.size() <= 1){return arrayList;}
        // 중간값을 기준으로 병합하는 느낌
        int medium = arrayList.size()/2;

        ArrayList<Integer> leftArr = new ArrayList<Integer>();
        ArrayList<Integer> rightArr = new ArrayList<Integer>();

        leftArr = new ArrayList<Integer>(arrayList.subList(0, medium));
        rightArr = new ArrayList<Integer>(arrayList.subList(medium, arrayList.size()));

        // 정렬하는 함수 만들기
       return this.mergeFunc(leftArr, rightArr);
    }

    public static void main(String[] args){
        ArrayList<Integer> testData = new ArrayList<>();

        for(int index=0; index<100; index++){
            testData.add((int)(Math.random()*100));
        }

        System.out.println(testData);
        MergeSort mergeSort = new MergeSort();
        System.out.println(mergeSort.margeSplitFunc(testData));
    }
}
```

#### 합병 정렬 특징

1. 안정적인 정렬 알고리즘 : 동일한 값의 상대적인 순서가 변하지 않는다.
2. 외부 정렬에 적합 : 데이터의 양이 많아서 메모리에 모두 올리기 어려운 경우에도 사용 가능
3. 추가적인 메모리 필요 : 배열을 분할하고 합치는 과정에서 임시 배열이 필요하므로, 메모리를 추가적으로 사용한다.
4. 평균 및 최악 시간 복잡도: `O(n log n)`
5. 최선의 경우 시간 복잡도: `O(n log n)`
6. 정렬된 상태에서도 효율적: 이미 정렬된 배열을 합치는 경우에도 효율적으로 작동

### 🍌 퀵 정렬(QuickSort)

#### 퀵정렬의 정의

* 가장 많이 사용되는 알고리즘
* 정렬 라이브러리의 근간이 되는 알고리즘

#### 기준 데이터 설정, **그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면** ?

* 기준을 설정한 다음 큰 수와 작은수를 교환한 후 리스트를 반으로 나누는 방식
* `피벗`이 사용

  ⇒ 큰 숫자와 작은 숫자 교환시, 교환하기 위한 **기준**

  ⇒ 퀸 정렬을 **수행하기 전** 피벗을 어떻게 설정할것인지 미리 명시 해야 함
* 피벗과 데이터를 비교하는 비교 연산 횟수가 증가하므로, 시간 면에서는 조금 비효율적 but, 직관적이고 기억하기 쉽다

#### 호어 분할 방식

* 재귀 함수 동작원리가 같음

  ⇒ **종료조건**이 있어야 함 : 현재 리스트의 데이터 개수가 1개인 경우

1. 리스트에서 **첫 번째 데이터**를 피벗으로 정한다
2. 피벗 설정한 뒤에는 `왼쪽`에서부터 피벗보다 **큰** 데이터를 찾고, `오른쪽`에서부터 피벗보다 **작은** 데이터를 찾음
3. 큰 데이터와 작은 데이터의 **위치를 서로 교환**

#### 퀵 정렬 방식(호어 분할 방식 예시)

✨ **1파트**

1. 리스트의 첫 번째 데이터를 피벗으로 설정하므로 피벗은 ‘5’ 이후에 `왼쪽`에서부터 ‘5’보다 **큰** 데이터를 선택하므로 ‘7’이 선택, `오른쪽`에서부터 ‘5’보다 **작은** 데이터가 선택되므로 ‘4’가 선택 ⇒ 두 데이터의 위치 서로 변경

![](https://velog.velcdn.com/images/prettylee620/post/c6188d6b-7b23-4eb4-84da-ed98f23dbc0f/image.png)

2. 그다음 다시 피벗보다 큰 데이터와 작은 데이터를 각각 찾고, 그 뒤 두 값의 위치를 서로 변경

![](https://velog.velcdn.com/images/prettylee620/post/9460cdf3-6db0-4f43-8534-9d5521e54c05/image.png)

3. 그 다음 다시 피벗보다 큰 데이터와 작은 데이터를 찾는다.
   1. 단, 현재 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 **위치가 서로 엇갈릴 수**도 있다.
   2. 이렇게 두 값이 엇갈린 경우에는 ‘작은 데이터’와 ‘피벗’의 위치를 서로 변경한다.
   3. 작은 데이터의 ‘1’과 피벗인 ‘5’의 위치를 서로 변경하여 `분할 수행`

![](https://velog.velcdn.com/images/prettylee620/post/f253a992-05ae-47a9-9ef7-15b66c592f55/image.png)

4. `분할 완료` : 이와 같이 피벗이 이동한 상태에서 왼쪽 리스트와 오른쪽 리스트를 살펴보자
   1. 이제 ‘5’ 왼쪽에 있는 데이터는 모두 ‘5보다 작고, 오른쪽에 있는 데이터는 ‘5’보다 크다는 특징
   2. `분할` 혹은 `파티션` : 피벗의 **왼쪽**에는 **피벗보다 작은 데이터**가 위치, 피벗의 **오른쪽**에는 **피벗보다 작은 데이터**가 위치

![](https://velog.velcdn.com/images/prettylee620/post/18a068bd-ea22-4fba-9bbd-60456859b915/image.png)

✨ 2**파트**

왼쪽 리스트에서 다음 그림과 같이 정렬 진행, 구체적인 정렬 과정은 동일

![](https://velog.velcdn.com/images/prettylee620/post/e72f5399-4447-4641-a155-b63857c949d7/image.png)

✨ 3**파트**

오른쪽 리스트에서 다음 그림과 같이 정렬 진행, 구체적인 정렬 과정은 동일

![](https://velog.velcdn.com/images/prettylee620/post/a0d80f58-ae56-4345-aacc-f5906b461675/image.png)

#### 퀵 정렬의 시간복잡도

* 평균적 시간복잡도 : $`O(NlogN)`$
* 최악의 경우 시간복잡도 : $`O(N^2)`$

  ⇒ 데이터가 이미 정렬되어 있는 경우 매우 느리게 작동
* 앞에 정렬 알고리즘들의 비해 엄청 빠른 편
* 분할이 이루어지는 횟수가 기하급수적으로 감소

```java

package Danymic;

import java.util.Scanner;

public class QuickSortEx {

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int arr[] = {3, 33, 38, 5, 2, 7, 15, 36, 26, 27, 2};

        System.out.println("정렬 전 :"+arr);

        System.out.println("정렬 후");
        quickSort(arr, 0, arr.length-1);
    }

    public static void quickSort(int[] array, int left, int right) {
        if(left >= right) return;

        //분할
        int pivot = partition(array, left, right);

        // 자기 자신을 재귀적으로 부름
        quickSort(array, left, pivot);
        quickSort(array, pivot+1, right);
    }

    private static int partition(int[] array, int left, int right) {
        int pivot = array[left];
        int i = left, j= right;
        while (i < j){
            // 피벗을 기준으로 j를 기준으로 찾음
            while(pivot < array[j]){
                j--;
            }
            while(i<j && pivot >= array[i]){
                i++;
            }
            swap(array, i, j);
        }
        array[left] = array[i];
        array[i] = pivot;
        
        return i;
        
    }

    private static void swap(int[] array, int i, int j) {
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
}
```

#### arrayList를 이용한 동작원리

```java
import java.util.ArrayList;
import java.util.Arrays;

public class QuickSort {
    public ArrayList<Integer> sort(ArrayList<Integer> dataList) {
        if (dataList.size() <= 1) {
            return dataList;
        }
        int pivot = dataList.get(0);

        ArrayList<Integer> leftArr = new ArrayList<Integer>();
        ArrayList<Integer> rightArr = new ArrayList<Integer>();

        for (int index = 1; index < dataList.size(); index++) {
            if (dataList.get(index) > pivot) {
                rightArr.add(dataList.get(index));
            } else {
                leftArr.add(dataList.get(index));
            }
        }

      
        ArrayList<Integer> mergedArr = new ArrayList<Integer>();
        mergedArr.addAll(sort(leftArr));
        mergedArr.addAll(Arrays.asList(pivot));
        mergedArr.addAll(sort(rightArr));

        return mergedArr;
    }

    public static void main(String[] args) {
        ArrayList<Integer> testData = new ArrayList<Integer>();

        for (int index = 0; index < 100; index++) {
            testData.add((int)(Math.random() * 100));
        }
        QuickSort qSort = new QuickSort();
        System.out.println(qSort.sort(testData));
    }
}
```

### 🍌 종류

1. 합병 정렬
2. 퀵 정렬
3. 거듭제곱 알고리즘
4. 병렬 행렬 곱셈
5. 최근접 점 쌍 찾기
6. 최대 부분배열 문제

### 🍌공통점과 차이점

* 공통점
  * 문제를 잘게 쪼개서, 가장 작은 단위로 분할
* 차이점
  * 동적 계획법
    * 부분 문제는 중복되어, 상위 문제 해결 시 재활용됨
    * `Memoization` 기법 사용 (부분 문제의 해답을 저장해서 재활용하는 최적화 기법으로 사용)
  * 분할 정복
    * 부분 문제는 서로 중복되지 않음
    * `Memoization` 기법 사용 안함