[자료구조/알고리즘] 탐욕 알고리즘 / 동적 계획법

hosik kim·2021년 12월 27일

algorithm greedy 알고리즘 자료구조 코드스테이츠 탐욕알고리즘

With CodeStates

목록 보기

22/45

💡탐욕 알고리즘 (Greedy Algorithm)

Greedy Algorithm(탐욕 알고리즘)은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.

탐욕 알고리즘으로 문제를 해결하는 방법은 다음과 같이 단계적으로 구분할 수 있다.

선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

탐욕 알고리즘을 우리가 흔히 겪을 수 있는 사례는 무엇이 있을까?

35kg까지 담을 수 있는 가방이 있는데, 담아야할 물건은 총 4가지가 있다.

그림 🖼 : 30kg, $3,000

티비 📺 : 25kg, $2,500

컴퓨터 🖥 : 20kg, $2,000

반지 💍 : 15kg, $1,500

탐욕 알고리즘을 사용한다면 문제는 다음과 같이 간단해진다

가방에 넣을 수 있는 물건 중 가장 비싼 물건을 넣는다.
그다음으로 넣을 수 있는 물건중 가장 비싼 물건을 넣는다.

가방은 35kg까지 담을 수 있고, 그림이 가장 비싸니 그림을 먼저 가방에 담을 수 있다. 남는 공간이 5kg밖에 남지 않아 담을 수 있는 물건이 없다. 그리고 이 때, 총 가치는 그림 하나의 가치와 같은 $3,000이다.

만약 그림 대신 컴퓨터와 반지를 가방에 담는다면 어떨까? 35kg이 넘지 않으면서 총 가치는 $3,500으로 그림 하나만 담을 때보다 더 많은 가치의 물건을 담을 수 있다.

탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식이다.
그러나 위 예시와 같이 항상 최적의 결과를 보장하지 못한다는 점을 알아야한다.

따라서 두 가지의 조건을 만족하는 "특정한 상황"이 아니라면 탐욕 알고리즘은 최적의 해를 보장하지 못한다. 탐욕 알고리즘을 적용하려면 해결하려는 문제가 다음의 2가지 조건을 성립해야한다.

탐욕적 선택 속성(Greedy Choice Property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.
최적 부분 구조(Optimal Substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다.
이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.

💡Implementation(구현)

구현 능력을 보는 대표적인 사례에는 완전 탐색(brute force)과 시물레이션(simulation)이 있다.
완적 탐색이란 가능한 모든 경우의 수를 전부 확인하여 문제를 푸는 방식을 뜻하고, 시뮬레이션은 문제에서 요구하는 복잡한 구현 요구 사항을 하나도 빠트리지 않고 코드로 옮겨, 마치 시뮬레이션을 하는 것과 동일한 모습을 그린다.

🔸완전 탐색

모든 문제는 완전 탐색으로 풀 수 있다. 이 방법은 굉장히 단순하고 무식하지만 "답이 무조건 있다"는 강력함이 있다.

예를 들어, 양의 정수 1부터 100까지의 임의의 요소가 오름차순으로 하나씩 담긴 배열 중, 원하는 값 N을 찾기 위해서는 배열의 첫 요소부터 마지막 요소까지 전부 확인을 한다면 최대 100번의 탐색 끝에 원하는 값을 찾을 수 있다.

그렇지만, 문제 해결을 할 때에는 기본적으로 두가지 규칙이 붙는다.

문제를 해결할 수 있는가?
효율적으로 동작하는가?

완전 탐색은 첫 번째 규칙을 만족시킬 수 있는 강력한 무기이지만 두 번째 규칙은 만족할 수 없는 경우가 있다.

양의 정수 1부터 100까지의 임의의 요소가 오름차순으로 하나씩 담긴 배열 중, 원하는 값 N을 찾으시오. 단, 시간 복자도가 O(N)보다 낮아야합니다.

이 경우, 최악의 경우 100번을 시도해야 하는 완전 탐색은 두 번째 규칙을 만족할 수 없다.

완전 탐색은 단순히 모든 경우의 수를 탐색하는 모든 경우를 통칭한다. 완전히 탐색하는 방법에는 brute Force(조건/반복을 사용하여 해결), 재귀, 순열, DFS/BFS 등 여러 가지가 있다.

🔸시뮬레이션

시뮬레이션은 모든 과정과 조건이 제시되어, 그 과정을 거친 결과가 무엇인지 확인하는 유형이다. 보통 문제에서 설명해 준 로직 그대로 코드로 작성하면 되어서 문제 해결을 떠올리는 것 자체는 쉬울 수 있으나 길고 자세하여 코드로 옮기는 작업이 까다로울 수 있다.

문제에 대한 이해를 바탕으로 제시하는 조건을 하나도 빠짐 없이 처리해야 정답을 받을 수 있으며, 하나라도 놓친다면 통과할 수 없게 되고, 길어진 코드 때문에 헷갈릴 수도 있으니 주의해야한다.

💡Dynamic Programming(동적 계획법)

동적 계획법 알고리즘은, 탐욕 알고리즘과 같이 작은 문제에서부터 출발한다는 점은 같다.

그러나 탐욕 알고리즘이 매순간 최적의 선택을 찾는 방식이라면, Dynamic Programming은 모든 경우의 수를 조합해 최적의 해법을 찾는 방식이다.

Dynamic Programming의 원리는 주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해곃나늠 누제 해결 방식이다.

하위 문제를 계산한 뒤 그 해결책을 저장하고, 나중에 동일한 하위 문제를 만날 경우 저장된 해결책을 적용해 계산 횟수를 줄인다. 다시 말해, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다.

두 가지 가정이 만족하는 조건에서 동적 계획법을 사용할 수 있다.

큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견된다(Overlapping Sub-problems)는 큰 문제로부터 나누어진 작은 문제는 큰 문제를 해결할 때 여러 번 반복해서 사용될 수 있어야한다.는 말과 같다.
이를 확인하기 위해서 피보나치 수열을 예로 살펴보자.

function fib(n) {
 if(n <= 2) return 1;
  return fib(n - 1) + fib(n - 2);
}
// 1, 1, 2, 3, 5, 8 ...

7번째 피보나치 수 fib(7)을 구하는 과정은 다음과 같다.

fib(7) = fib(6) + fib(5)
fib(7) = (fiv(5) + fib(4)) + fib(5) // fib(6) = fib(5) + fib(4)
fib(7) = ((fib(4) + fib(3)) + fib(4)) + (fib(4) + fib(3)) // fib(5) = fib(4) + fib(3)....

피보나치 수열은 위 예시처럼 동일한 계산을 반복적으로 수행해야 한다. 이 과정에서 fib(5)는 두 번, fib(4)는 세 번, fib(3)은 다섯 번의 동일한 계산을 반복한다. 이렇게 작은 문제의 결과를 큰 문제를 해결하기 위해 여러 번 반복하여 사용할 수 있을 때, 부분 문제의 반복(Overlapping Sub-problems)이라는 조건을 만족한다.

그러나 이 조건을 만족하는지 확인하기 전에, 한 가지 주의해야 할 점이 있다. __주어진 문제를 단순히 반복 계산하여 해결하는 것이 아니라, 작은 문제의 결과가 큰 문제를 해결하는 데에 여러번 사용될 수 있어야 한다.

두 번째 조건인 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다(Optimal Substructure)에 대해 살펴보자.

이 조건에서 말하는 정답은 최적의 해결 방법(Optimal solution)을 의미한다. 따라서 두 번째 조건을 달리 표현하면, __주어진 문제에 대한 최적의 해법을 구할 때, 주어진 문제의 작은 문제들의 최적의 해법(Optimal solution of Sub-problems)을 찾아야 한다. 그리고 작은 문제들의 최적의 해법을 결합하면, 결국 전체 문제의 최적의 해법(Optimal solution)을 구할 수 있다.

🔸Recursion + Memoization

다이내믹 프로그래밍은 하위 문제의 해결책을 저장한 뒤, 동일한 하위 문제가 나왔을 경우 저장해 놓은 해결책을 이용한다.

이때 결과를 저장하는 방법을 Memoization이라고 한다. Memoization의 정의는 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다.

재귀 함수에 Memoization을 어떻게 적용할지 다음의 예시를 통해 확인해보자

function fibMemo(n, memo = []) {
		// 이미 해결한 하위 문제인지 찾아본다
    if(memo[n] !== undefined) return memo[n];
    if(n <= 2) return 1;
		// 없다면 재귀로 결괏값을 도출하여 res 에 할당
    let res = fibMemo(n-1, memo) + fibMemo(n-2, memo);
		// 추후 동일한 문제를 만났을 때 사용하기 위해 리턴 전에 memo 에 저장
    memo[n] = res;
    return res;
}

먼저 fibMemo 함수의 파라미터로 n과 빈 배열을 전달한다. 이 빈 배열은 하위 문제와 결괏값을 저장하는 데에 사용한다.
memo 라는 빈 배열의 n번째 인덱스가 undefined 이 아니라면, 다시 말해 n번째 인덱스에 어떤 값이 저장되어 있다면, 저장되어 있는 값을 그대로 사용한다.
undefined라면, 즉 처음 계산하는 수라면 fibMemo(n-1, memo) + fibMemo(n-2, memo)를 이용하여 값을 계산하고, 그 결괏값을 res라는 변수에 할당한다.
마지막으로 res를 리턴하기 전에 memo의 n번째 인텍스에 res 값을 저장한다. 이렇게 하면 (n+1)번째의 값을 구하고 싶을 때, n번째 값을 memo에서 확인해 사용할 수 있다.

fib(7)을 구하기 위해서는 이전의 작업으로 저장해 놓은 하위 문제의 결괏값을 사용한다. n이 커질수록 계산해야 할 과정은 선형으로 늘어나기 때문에 시간 복잡도는 O(N)이된다.

Memorization을 사용하지 않고 재귀 함수로만 문제를 풀 경우, n이 커질수록 계산해야 할 과정이 두 배씩 늘어나 시간복잡도가 O(2ᴺ)이 되는 것과 비교하였을 때, 다이내믹 프로그래밍의 강점을 확인 할 수 있다.

피보나치 수열에서 fib(7)을 구하기 위해 fib(6)을, fib(6)을 구하기 위해 fib(5)을 호출한다.

이런 풀이 과정이 마치, 위에서 아래로 내려가는 것과 같다.

큰 문제를 해결하기 위해 작은 문제를 호출한다고 하여, 이 방식을 Top-down 방식이라 부르기도 한다.

🔸Iteration + Tabulation

재귀가 아닌 반복문을 이용하여 다이나믹 프로그래밍을 구현할 수 있다.

하위 문제의 결괏값을 배열에 저장하고, 필요할 때 조회하여 사용하는 것은 재귀 함수를 이용한 방법과 같다.

그러나 재귀 함수를 이용한 방법이 문제를 해결하귀 위해 큰 문제부터 시작하여 작은 문제로 옮아가며 문제를 해결하였다면,

반복문을 이용한 방법은 작은 문제에서부터 시작하여 큰 문제를 해결해 나가는 방법이다. 따라서 이 방식을 Bottom-up 방식이라 부르기도 한다.

function fibTab(n) {
    if(n <= 2) return 1;
    let fibNum = [0, 1, 1];
		// n 이 1 & 2일 때의 값을 미리 배열에 저장해 놓는다
    for(let i = 3; i <= n; i++) {
        fibNum[i] = fibNum[i-1] + fibNum[i-2];
		// n >= 3 부터는 앞서 배열에 저장해 놓은 값들을 이용하여
		// n번째 피보나치 수를 구한 뒤 배열에 저장 후 리턴한다 
    }
    return fibNum[n];
}