12장. 동적 프로그래밍

Deah (김준희)·2024년 3월 29일
개발서적알고리즘자료구조
0

누구나 자료구조와 알고리즘 (개정2판)

목록 보기
12/15
post-thumbnail

12.1 불필요한 재귀 호출

function max(array) {
	if (array.length === 1) return array[0];
  
  	if (array[0] > max(array.slice(1))) return array[0]
  	else return max(array.slice(1));
}

위 재귀 함수는 배열에서 최댓값는 함수로, 각 재귀 호출의 핵심은 하나의 수(array[0])와 나머지 배열의 최댓값 간의 비교다. (나머지 배열의 최댓값을 계산하기 위해 함수 안에서 연속적으로 max 함수를 호출하므로 재귀 함수!)

if (array[0] > max(array.slice(1))) return array[0]
else return max(array.slice(1));

두 번째 조건문에서 하나의 수(array[0])가 나머지 배열에서 가장 큰 수(max(array.slice(1)))에 비해 크면 array[0]이 최댓값이므로 해당 원소를 반환한다는 의미이다.

else 문에서는 array[0]이 나머지 배열의 최댓값보다 크지 않으면 나머지 배열의 최댓값이 전체 배열의 최댓값이므로 해당 값을 반환한다는 의미이다.

이 코드는 잘 작동하지만 중복 코드가 발생한다. (max(array.slice(1)))

[1, 2, 3, 4]

위 예제를 통해 단계별로 살펴보면,

  • 1과 [2, 3, 4]를 비교한다.
  • 2와 [3, 4]를 비교한다.
  • 3과 [4]를 비교한다.
  • [4]로 재귀가 호출되지만 기저 조건이다.

하지만 코드가 어떻게 실행되는지 제대로 알기 위해서는 "바닥 호출"부터 분석해 호출 사슬(call chain)을 따라 올라가야 한다.

max 재귀 분석

max([4])를 호출하면 해당 함수는 숫자 4를 반환한다.
왜냐하면 배열에 원소가 하나일 때가 기저 조건이기 때문이다.

max([4])

호출 사슬 위로 올라가며 max([3, 4])를 호출하면, 조건문 앞 부분인 if (array[0] > max(array.slice(1)))에서 3과 max([4])를 비교한다. max([4])는 재귀 호출이다.

max([3, 4])
↓ 1st
max([4])

1st 라벨을 붙여 이 재귀 호출이 max([3, 4])의 조건문 앞 부분에서 발생했음을 표시한다.

여기까지 끝나면 코드는 3과 max([4])의 결과인 4를 비교한다. 3은 4보다 크지 않으므로 조건문 뒤, 즉 else문을 실행한다. 따라서 여기에서도 다시 max([4])를 반환한다. 하지만 max([4])를 반환하면 실제로 해당 함수를 호출하게 된다. 이 때, 두 번째로 max([4])가 호출된다.

max([3, 4])
↓ 1stㅤㅤ↘︎ 2nd
max([4]) max([4])

max([3, 4])는 max([4])를 2번 호출한다.

max([2, 3, 4])에서도 마찬가지로 max([3, 4])를 다시 호출한다.

max([2, 3, 4])
↓ 1st
max([3, 4])
↓ 1stㅤㅤ↘︎ 2nd
max([4])ㅤmax([4])

max([2, 3, 4])
↓ 1stㅤㅤㅤㅤㅤㅤㅤㅤ↘︎ 2nd
max([3, 4])ㅤㅤㅤㅤㅤㅤmax([3, 4])
↓ 1stㅤㅤ↘︎ 2ndㅤㅤㅤㅤ↓ 1stㅤㅤ↘︎ 2nd
max([4])ㅤmax([4])ㅤㅤmax([4])ㅤmax([4])

.
.
.

즉, max([1, 2, 3, 4])를 호출하면 실제로 max 함수를 15번 호출한다.

함수 맨 앞에 명령문을 추가해 확인해보자.

function max(array) {
  	console.log("재귀가 실행됐어요!")
	if (array.length === 1) return array[0];
  
  	if (array[0] > max(array.slice(1))) return array[0]
  	else return max(array.slice(1));
}
max([1, 2, 3, 4]);

// 재귀가 실행됐어요!
// 재귀가 실행됐어요!
// 재귀가 실행됐어요!
// 재귀가 실행됐어요!
// 재귀가 실행됐어요!
// 재귀가 실행됐어요!
// 재귀가 실행됐어요!
// 재귀가 실행됐어요!
// 재귀가 실행됐어요!
// 재귀가 실행됐어요!
// 재귀가 실행됐어요!
// 재귀가 실행됐어요!
// 재귀가 실행됐어요!
// 재귀가 실행됐어요!
// 재귀가 실행됐어요!

이 중 어떤 호출은 정말 필요하지만, 또 어떤 호출은 필요 없기도 하다.
가령 max([4])는 꼭 호출되어야 하지만, 그 결과를 한 번만 계산해도 충분하다.
그러나 위 예제에서는 8번이나 호출된다.


12.2 빅 오를 위한 작은 개선

추가 재귀 호출을 전부 없앨 수 있는 방법은 코드에서 max 함수를 딱 한 번만 호출하고,
그 결과를 변수에 저장하여 함수를 재호출하지 않도록 수정하여 해결할 수 있다.

function max(array) {
	if (array.length === 1) return array[0];
  
  	let maxOfRemainder = max(array.slice(1));
  
  	if (array[0] > maxOfRemainder) return array[0];
  	else return maxOfRemainder;
}

이렇게 수정한다면 max 함수를 단 4번 호출한다.

function max(array) {
  	console.log("수정된 재귀 호출!");
	if (array.length === 1) return array[0];
  
  	let maxOfRemainder = max(array.slice(1));
  
  	if (array[0] > maxOfRemainder) return array[0];
  	else return maxOfRemainder;
}
max([1, 2, 3, 4]);

// 수정된 재귀 호출!
// 수정된 재귀 호출!
// 수정된 재귀 호출!
// 수정된 재귀 호출!

12.3 재귀의 효율성

개선된 두 번째 max 함수는 배열 내 요소의 개수만큼 재귀 호출이 일어난다. 이는 O(N)O(N)이다.
이전까지 배웠던 O(N)O(N)은 루프가 있었고, 해당 루프를 NN번 실행했지만 같은 빅 오 원리를 재귀에도 적용할 수 있다.

개선된 max 함수는 배열 내 값이 NN개 일 때 NN번 실행되므로 시간 복잡도가 O(N)O(N)이다.
함수 자체에 여러 단계가 포함되어 있다고 하더라도, 빅 오에서 지수를 제외한 상수는 무시되기 때문에 결국 O(N)O(N)이 된다.

하지만 첫 번째 max 함수는 함수를 실행할 때마다 자신을 두 번 호출했다. (기저조건 제외)
이 함수가 배열의 크기가 달라질 때 어떻게 될까?

원소 갯수 (NN)함수 호출 횟수
11
23
37
415
531

데이터가 1씩 증가할 때마다 알고리즘에 필요한 단계 수는 약 2배씩 증가한다.
7.9-암호 크래커에서 설명했듯 이 패턴은 O(2N)O(2^N) 패턴이다. 현저히 느린 알고리즘이다.
그러나 개선된 두 번째 max 함수는 배열 내 원소 수만큼만 자기 자신을 호출한다. (O(N)O(N))

  • O(2N)O(2^N) vs O(N)O(N)

불필요한 재귀 호출을 피하는 것이 재귀를 빠르게 만드는 핵심 비결이다.


12.4 하위 문제 중첩

피보나치 수열(Fibonacci Sequence)이란?
피보나치 수는 첫째 및 둘째 항이 1이며 그 뒤의 모든 항은 바로 앞 두 항의 합인 수열이다.
편의상 0번째 항을 0으로 두기도 한다.
(0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55...)

피보나치 수열에서 이어지는 수는 수열의 앞 두 수의 합이다. (55 = 21 + 34)

function fib(n) {
	if (n === 0 || n === 1) return n;
  	return fib(n - 2) + fib(n - 1);     // 피보나치 함수의 핵심!
}

이 코드는 피보나치 수열에서 앞의 두 수를 합하는 간결한 재귀 함수다.
하지만 함수가 자기 자신을 2번 호출하므로 이 부분에서 위험을 감지해야 한다.

위 예제에서는 간단하게 최적화를 할 수 있었지만 피보나치 수열에서 변수에서는 간단하지 않다. 피보나치 수는 앞선 두 수의 합이므로 두 번의 재귀 호출이 일어나고 그 결과를 모두 계산해야 하는데, 그 중 하나의 결과만 저장해서는 나머지 결과를 얻지 못하기 때문이다.

컴퓨터 과학에서 이를 일컬어 하위 문제 중첩(overlapping subproblems)이라고 부른다.

하위 문제가 중첩되는 이유는 fib(n - 2)와 fib(n - 1)이 결과적으로 같은 함수를 중복하여 여러 번 호출하기 때문이다. 즉 fib(n - 1)은 fib(n - 2)가 먼저 했던 계산을 수차례 똑같이 반복한다.


12.5 메모이제이션을 통한 동적 프로그래밍

하위 중첩 문제는 동적 프로그래밍을 통해 해결할 수 있다.
동적 프로그래밍은 하위 문제가 중첩되는 재귀 문제를 최적화하는 절차이다.

동적 프로그래밍(Dynamic Programming)이란?
복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

메모이제이션이란?
컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술. 동적 계획법의 핵심이다.

동적 프로그래밍을 통한 알고리즘 최적화에는 일반적으로 두 가지 중 하나를 사용한다.

1. 메모이제이션(memoization)

메모이제이션은 먼저 계산한 함수 결과를 기억해 재귀 호출을 감소시킨다.

피보나치 예제에서 fib(3)을 처음 호출하면 함수는 이를 계산하고 2를 반환한다.
다만, 반환하기 전에 함수 결과를 해시 테이블에 저장한다.

{
  3: 2  // fib(3)의 결과가 2라는 의미
}

같은 방식으로 코드는 새로 계산한 결과를 모두 메모이징(memorize)한다.
fib(4)와 fib(5)를 호출한 뒤 해시 테이블은 아래와 같이 저장된다.

{
  3: 2,
  4: 3,
  5: 5,
  6: 8
}

해시 테이블을 통해 다음 재귀 호출을 피할 수 있는 방법은 하위 함수를 호출해야 할 때, 호출 전 해시 테이블을 확인하여 해당 결과가 미리 계산되어 있는지 확인하면 된다. 그리고 해시 테이블에 없을 때에만 재귀 함수를 호출한다.

메모이제이션은 하위 문제 중첩의 핵심을 제대로 파고든다. 하위 문제가 중첩되면 결국 동일한 재귀 호출을 반복해서 계산하게 되는데, 메모이제이션을 사용하면 새로운 계산을 할 때 마다 해시 테이블에 저장하고 추후 사용이 가능하다. 그러므로 하지 않았던 계산만 수행한다.

🤓 그럼 재귀 함수는 해시 테이블에 어떻게 접근하나요?

함수의 두 번째 인자로 해시 테이블을 전달하면 된다.
해시 테이블은 메모리 내 객체이므로 함수 호출 중 수정되더라도 한 재귀 호출에서 다음 재귀 호출로 바로 전달할 수 있다.

메모이제이션 구현

해시 테이블을 함께 전달하기 위해서는 인수를 추가하여 두 개의 인수를 받을 수 있도록 수정해야 한다.

function fib(n, memo) {
	
}

함수를 처음 호출할 때는 빈 해시 테이블을 전달한다.

fib(6, {})

그리고 fib 함수가 자신을 호출할 때마다 해시 테이블도 함께 전달되고 그 과정에서 해시테이블이 채워진다.

기본 코드

function fib(n, memo) {
    if (n === 0 || n === 1) return n;

    if (!memo.hasOwnProperty(n)) {
        memo[n] = fib(n - 2, memo) + fib(n - 1, memo);
    }
    return memo[n];
}

해설

function fib(n, memo) {
  	// 0이거나 1일 때, 해당 수를 반환 (기저 조건)
    if (n === 0 || n === 1) return n;

  	// memo가 해시 테이블에 존재하는지를 확인
  	// 없을 경우 해시 테이블에 계산한 값을 저장
    if (!memo.hasOwnProperty(n)) {
        memo[n] = fib(n - 2, memo) + fib(n - 1, memo);
    }
  
  	// 해당 값을 반환
    return memo[n];
}

이 코드는 계산 결과를 memo 해시 테이블에 저장하므로 같은 함수를 다시 계산할 필요가 없다.

알고리즘의 핵심은 바뀌지 않았으며 여전히 재귀를 통해 문제를 해결하고 있다.
그러나 계산하는 수가 처음 나오는 수라면 그 결과를 해시 테이블에 저장하고, 이 전에 한 번 계산된 수라면 다시 계산하지 않고 해시 테이블에서 그 값을 가져온다.

🧐 그럼 이 함수의 빅 오는 무엇인가요?

원소 갯수 (NN)함수 호출 횟수
11
23
35
47
59
611

NN에 대해 (2N)−1번(2N) - 1번 함수가 호출되는 것을 알 수 있다.
빅 오는 상수를 버리므로 O(N)O(N) 알고리즘이다.

O(2N)O(2^N)에 비해 엄청나게 향상된 것을 알 수 있다.


12.6 상향식을 통한 동적 프로그래밍

2. 상향식

동적 프로그래밍을 통한 알고리즘 최적화의 두 번째 방법은 상향식이다. 이 방법은 메모이제이션보다 덜 세련되고 기법이라 부르기도 애매하다. 그저 같은 문제를 재귀 대신 루프 등의 다른 방식으로 해결한다는 뜻이다.

상향식이 동적 프로그래밍의 하나로 간주되는 이유는, 재귀적으로 풀 수 있는 문제에 대해 중첩되는 하위 문제를 중복 호출하지 않게 하기 때문이다. 재귀 대신 반복(루프)를 사용하는 것도 이렇게 하는 방법 중 하나이다.

피보나치 수열은 재귀로 깔끔하고 간결하게 풀리는 예시다.
반복적 방식은 덜 직관적이기 때문에 같은 문제를 반복해서 풀기 위해서는 머리를 많이 써야한다.
가령, 11장의 계단 문제를 반복문으로 푼다면...? 🤮

상향식 피보나치

상향식에서는 처음 두 피보나치 수인 0과 1로 시작한다. 그리고 반복 기법을 사용해 수열을 만들어 간다.

기본 코드

function fib(n) {
	if (n === 0) return 0;
  
  	let a = 0;
  	let b = 1;
  
  	for (let i = 1; i <= n; i++) {
    	let temp = a;
      	a = b;
       	b = temp + a;
    }
}

해설

function fib(n) {
	if (n === 0) return 0;
  
  	// 피보나치 수열의 처음 두 수가 0과 1이므로 a와 b는 각각 0과 1로 시작
  	let a = 0;
  	let b = 1;
  
  	// n까지 수열의 각 수를 계산하는 루프
  	// 수열의 다음 수를 계산하려면 앞의 두 수를 더해야 하므로
  	// 가장 최근 값은 a, 두 번째로 최근 값은 temp에 할당
  	// 두 수를 합한 수열의 새로운 수를 b에 할당
  	for (let i = 1; i <= n; i++) {
    	let temp = a;
      	a = b;
       	b = temp + a;
    }
}

이 코드는 1부터 NN까지 돌아가는 간단한 루프이므로 NN단계가 걸리며, 메모이제이션과 같이 O(N)O(N)이다.

메모이제이션 vs 상향식

🥸 둘 중 어떤 기법이 더 나은가요?

보통은 문제에 따라, 왜 재귀를 사용하는지에 따라 다르다.

재귀가 주어진 문제를 푸는 간결하고 직관적인 해법이라면 재귀로 풀면서 메모이제이션으로 하위 중첩 문제를 해결할 수 있다. 하지만 반복 루프를 사용하는 방식도 충분히 직관적이면 그렇게 해결하고 싶을 수도 있다.

메모이제이션을 사용하더라도 재귀가 반복에 비해 오버헤드가 더 든다는 사실을 간과해서는 안 된다.

구체적으로 말하면 재귀를 어떻게 사용하더라도 컴퓨터는 호출 스택에 모든 호출을 기록해야 하므로 메모리를 소모하게 된다. 메모이제이션 자체도 해시 테이블을 사용하므로 마찬가지로 컴퓨터 공간을 추가로 소모한다.

재귀가 매우 직관적이지 않은 이상 일반적으로 상향식을 택하는 편이 더 낫다.
재귀가 직관적이고 편리하다면 재귀를 사용하되, 메모이제이션으로 빠르게 최적화를 해야 한다.


실습

  1. 다음 함수는 수 배열을 받아 그 합을 반환하되 100을 초과하게 만드는 수는 제외한다. 어떤 수를 더해 합이 100이 넘으면 그 수는 무시한다. 하지만 함수에서 불필요한 재귀 호출이 일어나고 있다. 코드를 수정해 불필요한 재귀를 없애자.

기존 코드

function addUntil100(arr) {
    if (arr.length === 0) return 0;

    if (arr[0] + addUntil100(arr.slice(1)) > 100) {
        return addUntil100(arr.slice(1));
    } else {
        return arr[0] + addUntil100(arr.slice(1));
    }
}

수정 코드

function addUntil100(arr) {
    if (arr.length === 0) return 0;

    let recursion = addUntil100(arr.slice(1));

    if (arr[0] + recursion > 100) {
        return recursion;
    } else {
        return arr[0] + recursion;
    }
}

  1. 다음의 함수는 재귀를 사용해 "골롬수열"이라는 수학적 수열의 N번째 수를 계산한다. 하지만 형편없이 비효율적이다. 메모이제이션으로 최적화하자. (골롬 수열이 실제로 어떻게 동작하는지 몰라도 문제를 충분히 풀 수 있다).

기존 코드

function golomb(n) {
    if (n === 1) return 1;
    return 1 + golomb(n - golomb(golomb(n - 1))); 
}

수정 코드

function golomb(n, memo = {}) {
    if (n === 1) return 1;
    
  if (!memo[n]) {
  	memo[n] = 1 + golomb(n - golomb(golomb(n - 1, memo), memo), memo); 
  }
  
  return memo[n];
}

  1. 다음은 11장 연습 문제에 나왔던 "유일 경로" 문제의 해법이다. 메모이제이션으로 효율성을 개
    선하자.

기존 코드

function uniquePaths(rows, columns) {
	if (rows === 1 || columns === 1) return 1;
  	return uniquePaths(rows - 1, columns) * uniquePaths(rows, columns - 1);
}

수정 코드

function uniquePaths(rolws, columns, memo = {}) {
	if (rows === 1 || columns === 1) return 1;
  
  	if (!memo[[rows, columns]] {
    	memo[[rows, columns]] = uniquePaths(rows - 1, columns, memo) + uniquePaths(rows, columns - 1, memo);
    }

	return memo[[rows, columns]];
}

요약

  • 재귀는 호출 스택에 모든 재귀 호출을 기록하므로 메모리 소비량이 많다.
  • 재귀를 사용할 때에는 메모이제이션, 또는 상향식의 방법을 사용하여 재귀 함수를 최적화하는 습관이 필요하다.
profile
Deah (김준희)
기록 중독 개발자의 기록하는 습관
이전 포스트

11장. 재귀적으로 작성하는 법

다음 포스트

13장. 속도를 높이는 재귀 알고리즘

0개의 댓글