동적 계획법과 분할정복

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)

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)

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[병합 정렬]

관련 동작 방법은 노션에..

개념

1. 분할 정복 알고리즘의 하나로, 큰 문제를 작은 문제로 분할하여 해결하는 방식을 사용하여 정렬을 수행하는 알고리즘

2. 대부분의 경우에 거의 O(n log n)의 시간 복잡도를 가지므로 대규모 데이터 정렬에 많이 사용

3. 합병 정렬은 데이터 양이 많아서 메모리를 효율적으로 관리해야 할 때나 안정적인 정렬을 원할 때 주로 선택되는 알고리즘

동작방법

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

1. 분할(Divide) : 정렬할 배열을 반으로 나눈다. 이를 계속해서 작은 배열이 될 때까지 반복적으로 분할

2. 정복(Conquer) : 분할된 작은 배열을 정렬, 만약 배열의 길이가 1이거나 0이라면 이미 정렬된 상태

3. 합병(Merge) : 정렬된 작은 배열들을 하나로 합병한다. 이때, 두 배열을 비교하여 정렬된 순서대로 합치는데, 작은 값부터 순서대로 병합

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’가 선택 ⇒ 두 데이터의 위치 서로 변경

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

1. 그 다음 다시 피벗보다 큰 데이터와 작은 데이터를 찾는다.

   1. 단, 현재 왼쪽에서부터 찾는 값과 오른쪽에서부터 찾는 값의 위치가 서로 엇갈릴 수도 있다.

   2. 이렇게 두 값이 엇갈린 경우에는 ‘작은 데이터’와 ‘피벗’의 위치를 서로 변경한다.

   3. 작은 데이터의 ‘1’과 피벗인 ‘5’의 위치를 서로 변경하여 분할 수행

1. 분할 완료 : 이와 같이 피벗이 이동한 상태에서 왼쪽 리스트와 오른쪽 리스트를 살펴보자

   1. 이제 ‘5’ 왼쪽에 있는 데이터는 모두 ‘5보다 작고, 오른쪽에 있는 데이터는 ‘5’보다 크다는 특징

   2. 분할 혹은 파티션 : 피벗의 왼쪽에는 피벗보다 작은 데이터가 위치, 피벗의 오른쪽에는 피벗보다 작은 데이터가 위치

✨ 2파트

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

✨ 3파트

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

퀵 정렬의 시간복잡도

• 평균적 시간복잡도 : $O(NlogN)$

• 최악의 경우 시간복잡도 : $O(N^2)$

  ⇒ 데이터가 이미 정렬되어 있는 경우 매우 느리게 작동

• 앞에 정렬 알고리즘들의 비해 엄청 빠른 편

• 분할이 이루어지는 횟수가 기하급수적으로 감소

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를 이용한 동작원리

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 기법 사용 안함