[알고리즘] 동적 계획법 & 분할 정복

SeongWon Oh·2021년 9월 1일

Divide and conquer Java dynamic programming 알고리즘

알고리즘

목록 보기

6/12

동적 계획법 (Dynamic Programming)

문제를 해결하기 위해 문제를 하위문제로 나누어, 가장 최하위의 답을 구한 후, 그 결과값을 이용하여 상위 문제를 풀어가며 최종적으로 전체 문제를 해결하는 알고리즘이다.
문제를 상향식 접근법으로 해결하는 방법이다.
즉, 작은 문제부터 풀어서 큰 문제로 이어가며 문제를 해결하는 방법이다.
문제를 쪼개서 중복된 문제에 대해서는 Memorization기법을 활용한다.
최단 경로 문제, 행렬의 제곱 문제 등의 최적화에 사용된다.
(모든 방법을 검토하고, 최적의 풀이법을 찾아내기 때문)
대표적인 예시로는 피보나치 수열이 있다.

Memorization기법이란?
프로그램을 실행할 때 이전에 계산을 값들을 저장하고, 추후 동일 계산이 있을 때 앞서 저장된 결과값을 사용하여 중복된 계산을 줄이는 방법이다.
중복된 계산을 줄임으로써 프로그램 전체 실행속도가 빨라진다.

Dynamic programming예시 (피보나치 수열에 적용)

Dynamic programming적용 전

	public static int fibo(int num) {
		if (num <= 1) 
			return num;
		else 
			return fibo(num-1) + fibo(num-2);
	}

Dynamic programming적용 후

	public static int fibo(int num) {
		int[] cache = new int[num+1]; 
		// ex) fibo 10을 한다면 fibo(0)부터 fibo(10)까지의 값이 모두 필요하기 때문
		
		cache[0] = 0;
		cache[1] = 1;
		
		for (int i=2; i< num+1; i++) {
			cache[i] = cache[i-1] + cache[i-2];
		}
		return cache[num];
	}

Dynamic programming적용 전/후 코드를 비교해보면 적용 전 코드의 경우는 fibo메서드를 recursive하게 호출하여 계산을 하였던 연산들도 다시 호출되면 새롭게 연산해야하는 낭비가 있었다. 하지만 적용 후의 코드는 cache에 결과값을 저장하여두고 계산을 중복하게 하는 낭비를 없앤 것을 볼 수 있다.

분할정복 (Divide and Conquer)

하양식 접근법으로 상위 문제를 분할하며 문제를 나눌 수 없을 때까지 나누어서 문제를 풀고 다시 합치며 문제의 답을 얻는 알고리즘이다.
일반적으로 재귀함수로 구현을 한다.
문제를 나눔으로써 어려운 문제를 나누어 병렬적으로 해결할 수 있다는 장점이 있으나 함수를 재귀적으로 호출하여 오버헤드가 발생하여 과도한 메모리를 사용하게 되는 단점이 있다.
동적 계획법과는 다르게 부분 문제가 중복되지 않아 Memorization기법을 사용하지 않는다.
대표적인 예시로는 병합정렬, 퀵정렬등이 있다.

Divide and Conquer예시 (Quick sort)

	public static List<Integer> quickSort(List<Integer> arr) {
		List<Integer> leftList = new ArrayList<>();
		List<Integer> rightList = new ArrayList<>();
		
		// 크기가 1보다 작거나 같으면 그대로 반환
		if (arr.size() <= 1)
			return arr;
		
		int pivot = arr.remove(0);
		
		// data가 pivot보다 작으면 왼쪽으로, 크면 오른쪽으로 봔환
		for (int data: arr) {
			if (pivot > data)
				leftList.add(data);
			
			else rightList.add(data);
		}
		
		// 왼쪽, 오른쪽 list를 다시 quick sort한 후
		// 왼쪽 list + pivot + 오른쪽 list를 반환
		quickSort(leftList).add(pivot);
		leftList.addAll(quickSort(rightList));
		return leftList;
		
	}