**주의 : 이 포스팅에는 코드스테이츠 이머시브코스와 관련된 문제가 있습니다. 문제해결을 위해 충분히 고민해보고 도전해보지 않으신 분들에게는 스포일러가 될 수 있습니다.

Greedy Algorithm

이름부터가 탐욕스러운 이 알고리즘은 눈 앞에 보이는 최적의 상황만을 탐욕적으로 쫓아 최종적인 해답에 도달하는 방법이다. Greedy Algorithm의 문제 해결법을 단계적으로 나누어 본다면 아래와 같다.

1. 선택절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다.

2. 적절성 검사(Feasibillity Check) : 선택된 해가 문제의 조건을 만족하는지 검사합니다.

3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가 반복합니다.

일반적으로 Greedy Algorithm을 설명할 때 가장 많이 나오는 것이 거스름돈의 사례인 것 같다. 거스름돈을 줄 때는 기본적으로 가장 큰 단위의 동전을 최대한 사용한 다음 그 다음 단위의 동전을 최대한 사용하는 식으로 해야 거슬러주는 동전의 수를 최적화시킬 수 있다.
예를 들어 970원을 거슬러 주려고 할 때에는 특정 단위의 동전이 부족한게 아니라면 아래와 같이 거슬러 주게 될 것이다.

500원 짜리 1개, 100원짜리 4개, 50원짜리 1개, 10원짜리 2개

  1. 선택절차 : 가장 큰 단위의 동전을 선택한다. 가장 큰 단위의 동전을 선택하는 것이 탐욕!
    a. 500원 선택 (a-1로)
    b. 100원 선택 (b-1로)
    c. 50원 선택 (c-1로)
    d. 10원 선택 (d-1로)
    e. 선택할 동전 없음(e-1로)
  2. 적절성검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러줄 금액을 초과하는지 확인한다.
    a-1. 500원 2개를 선택하면 거슬러줄 금액을 초과하므로 마지막에 추가한 동전을 빼고 1번으로 돌아가 한 단계 낮은 단위의 동전을 선택한다. (b로)
    b-1. 100원짜리를 5개째 추가하다 보니 또 거슬러줄 금액을 초과했다. 마지막에 추가한 100원짜리 동전을 다시 빼고 한 단계 낮은 단위의 동전을 선택한다. (c로)
    c-1. (중략) (d로)
    d-1. 10원짜리 동전을 2개 3개 추가했을 때 거슬러줄 금액을 초과했다. 마지막에 추가한 동전을 내려 놓고 한 단계 낮은 단위의 동전을 선택하려 했으나 더 이상 없다. (e로)
    e-1. 더 이상 초과하지 않으므로 3번 단계로 넘어 간다.
  3. 해답 검사: 선택된 동전들의 합이 거슬러줄 금액과 일치한다. 여기서 종결.

Greedy Algorithm 문제 : 짐 나르기

박스에 짐을 2개를 묶어 넣기 위해 시도하려면 크게 3가지로 시도해 볼 수 있다.

  1. 가장 무거운 짐과 두 번째로 무거운 짐을 묶기 위해 시도한다.
  2. 가장 가벼운 짐과 두 번째로 가벼운 짐을 묶기 위해 시도한다.
  3. 가장 무거운 짐과 가장 가벼운 짐을 묶기 위해 시도한다.

1번 방법 가장 무거운 짐들끼리 묶어도 limit을 초과하지 않는 상황이라면 stuff는 어떤 조합으로도 묶는 것이 가능할 것이다. 그 다음 무거운 짐을 다시 선택해서 묶기 위해 시도해 본다. 묶어지지 않는 다면 다시 그 다음 무거운 짐으로... 문제는 이러다가 limit이 넘지 않는 조합을 찾았다고 하더라도 가장 무거운 짐과 조합한 짐이 배열의 중간에 있기 때문에 묶은 짐들을 제외하는 작업에서 어려움을 겪게 된다. (이걸 구현하기 위해 시도하다가 몇 시간 동안 제자리 뛰기를 했다.)

2번 방법 가장 가벼운 짐들끼리 묶었을 때 limit를 초과한다면, 이 stuff에는 그 어떤 조합도 나올 수 없다. 만약 묶인다고 해도, 아래의 예를 보면 효율적으로 묶었다고 판단하기는 어려울 것이다.

stuff = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
limit = 11
가벼운 순서대로 앞에서 부터 묶어 보기 [1, 2][3, 4] [5, 6][7] [8][9] [10]

위와 같이 초반에 순조롭게 묶이는 것 같지만 뒤로 가면 갈 수록 비효율적인 조합이 된다. 실제로 저렇게 짐을 포장하면, 어떤 박스는 짐이 2개 들어가고도 텅텅 비어 있을 것이다.

3번 방법 이 방법이 가장 효율적이라는 것을 찾는 데만 엄청나게 오랜 시간이 걸렸다. 이 방법을 사용하니 묶은 짐들을 제거하기에도 용이했다. 이제 Greedy Algorithm의 3단계로 넘어가 보자.

  1. 선택 절차 : 가장 무거운 짐과 가장 가벼운 짐을 선택한다.
  2. 적절성 검사 : 선택한 짐들의 무게의 합이 limit을 초과하는지 확인한다. 초과하지 않는다면 둘을 묶어서 한 박스에 넣은 후, 1로 돌아가 그 다음 무거운 짐과 그 다음 가벼운 짐을 선택한다. 초과한다면, 가장 무거운 짐은 어차피 다른 짐과 조합이 불가능하다. 따로 빼놓고 1번으로 돌아가 그 다음 무거운 짐을 선택한다.
  3. 해답 검사 : 위 과정을 반복하다 보면 묶인 조합들이 나오게 될 것이다. 몇 개의 조합이 나왔는지 파악한 후, stuff의 요소의 갯수에서 조합의 수를 빼주면 된다.

짐 나르기

function movingStuff(stuff, limit) {
  let package = 0; // package 변수를 선언하고 0할당. limit을 넘지 않는 조합이 나오면 pakage++를 해줄 것이다.
  let sorted = stuff.sort((a, b) => a - b) // stuff를 오름차순으로 정렬하는 방법이다. 그냥 암기해두면 유용하다. 
  let largeIdx = sorted.length - 1 // 가장 무거운 짐의 인덱스
  // 처음에는 인덱스가 아니라 sorted[sorted.length - 1]을 할당했다. 만약 양쪽 끝에 있는 짐들의 조합이 가능 하면 pop()과 shift()를 사용하면 되는데 가장 무거운 짐을 조합하지 못해서 그 다음 무거운 짐을 선택하는 순간 조합이 되었을 때 그 짐을 제외할 방법이 너무 복잡해진다. 인덱스를 할당하면 된다는 것을 깨닫는데 또 어마어마한 시간의 제자리 걸음이 있었다.
  let smallIdx = 0 // 가장 가벼운 짐의 인덱스는 당연히 0

    while (largeIdx > smallIdx) { // while 반복문을 사용하는 것은 가장 마지막에 떠올린 퍼즐조각이었다. '반복문 = for'를 머리에 두고 있으니 가끔 끝날 것 같은 상황에 끝나지 않는 답답한 상황이 생긴다. 그럴 때는 while을 간과하고 있지 않은지 점검하자.
    if (sorted[smallIdx] + sorted[largeIdx] <= limit) { //가장 무거운 + 가장 가벼운 <= limit인지 확인한다.
        //참일 경우
        package++ // package로 묶어 주고
        smallIdx++ // 그 다음 가벼운 짐을 선택
        largeIdx--; // 그 다음으로 무거운 짐을 선택
        // pop(), shift()따위...
      } else {
        //거짓일 경우
        largeIdx--; // 그 다음으로 무거운 짐을 선택 
      }
    }
  return stuff.length - package; //짐을 한개씩 나르는 경우의 수에서 count빼준다.
}

Dynamic Programming

Greedy Algorithm과 늘 함께 언급된다고 한다.산 너머 산...
동일하게 작은 문제에서 출발하지만, Greedy Algorithm이 순간의 최적의 방법으로 시작하는 방법이라면, Dynamic Programming은 모든 경우의 수를 따져본 후 이를 조합해 최적의 방법을 찾는다.
_mbti로 치면 Greedy Algorithm은 P들이 할만한 방법이고, Dynamic Programming은 J들이 생각할 만한 방법이군.

주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 무제들의 해결 방법을 결합하여 최종 문제를 해결한다.

사용하기 위한 조건도 있다.

Overlapping Sub-problem: 큰 문제들을 작은 문제로 나눌 수 있고, 이 작은 문제들은 중복된다.
Optional Substruction: 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용할 수 있다.

이 말 어디서 많이 본 말이다. 가만 생각해보니 재귀에 대해서 배울 때 본 내용과 99% 일치하는 것 같다. 아니나 다를까 주요 예제는 피보나치였다.

const fibonacci = (n) => {
  if (n <= 2) { // 멈춤 조건은 n이 계속 작아지다가 2와 같거나 작아졌을 때
    return 1; // n이 2라는 것은 두 번째 피보나치를 리턴하면 된다는 뜻이다.
  }
  
  return fibonacci(n - 1) + fibonacci(n - 2);
  // 입력된 n에서 1을 뺀 값과 2를 뺀 값을 각각 재귀한 후 더 해준다.
}

// 이렇게 코드를 구현했을 때 구하는 과정은 아래와 같다.
fibonacci(7) = fibonacci(6) + fibonacci(5)
fibonacci(6) = fibonacci(5) + fibonacci(4)
fibonacci(5) = fibonacci(4) + fibonacci(3)
.....

위 그림과 같이 같은 값을 계속해서 반복해서 구하게 된다. 안 그래도 재귀를 사용해서 작업이 복잡한데, 같은 값을 반복해서 구하다 보니 시간이 오래 걸리게 된다. 콘솔창에 입력해보니 32정도부터 눈에 띄게 딜레이가 생겼다

Dynamic Programming은 하위 문제의 해결책을 저장한 뒤 동일한 하위 문제가 나왔을 경우 저장해 놓은 해결책을 이용한다.

Recursion + Memoization

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

저장되어 있는 값을 가져다 쓰기 시작하면서 시간복잡도가 O(2^N)에서 O(N)로 변했다. 이 방법을 사용하면 n에 큰 수를 할당해도 전과 같은 딜레이가 발생하지 않는다. 아래 그림처럼 내려가면서 문제를 해결한다고 해서 Top-down방식이라고 부르기도 한다.

Iteration + Tabulation

Top-down이 있다면 당연히 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];
}

이 방법도 n이 1, 2일 때의 값을 미리 저장해 놓음으로써 불필요한 딜레이를 없앨 수 있는 방법이다.

금고를 털어라

이 문제는 거스름돈을 거슬러 주기 위해 동전을 조합하는 경우의 수를 구하는 문제와 동일하다고 생각했다. 그렇다고 문제가 쉽게 풀리진 않았다. 아무리 고민해도 문제를 해결할 방향조차 잡지 못해서 '거스름돈 자바스크립트'를 검색해서 나온 코드를 약간 수정해서 정답인 것을 확인한 후 debugger를 수차례 돌려보면서 주석을 달았다.
왜 이게 Dynamic Programming인지 이해가 안됐었는데 방금 블로그 정리하다 보니 납득이 좀 되었다.

function ocean(target, type) {
    // 1단계: 배열을 하나 만들어 준다. 길이는 target보다 1이 크고, 요소는 첫 요소를 제외하고 모두 0으로 채워준다. [1, 0, 0, 0, 0, 0, 0, 0, 0,........ , 0] 
    // 이 배열의 각 요소는 type의 요소들(화폐 단위)을 사용해서 0부터 target+1까지 수들을 만들 수 있는 경우의 수이다. 0은 아무것도 고르지 않았을 때의 경우의 수인 1이 미리 할당되어 있고, 나머지 요소들도 경우의 수를 차차 채워 나갈 것이다.
    let arr = [1];
    for(let i = 0; i < target; i++) {
      arr.push(0); 
    }
    // arr를 1을 넣은 배열로 할당해 준 후, 반복문을 돌려서 0을 target만큼 push해주었다.

    type.map(function(ele) { // ele = 10, 20, 50
        arr[ele] += 1; // [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1....1, .... , 1]
        // 여기까지가 type에 있는 요소들을 arr에 표시하는 작업이다.
        // 화폐 단위가 있으니 그 화폐 1장만을 선택했을 경우가 1로 표시된다.
        for (let i = ele + 1 ; i <= target ; i++) { 
            arr[i] += arr[i - ele];
            // arr에 표시를 해주는 방법:
            // map을 통한 이 작업은 type의 요소의 갯수만큼 반복한다.
            // ele가 10일 때 : i가 10부터 50까지 돌면서 표시를 한다.
            // debugger를 돌려서 과정을 꼭 살펴보자.
        }
    });
    return arr[target]; // 굉장히 긴 과정을 지나다보면 어느새 target번째에는 경우의 수가 target을 만드는 경우의 수가 들어와 있다.
}

위와 같은 풀이처럼 하나의 '저장 배열'을 만든 다음 반복되는 작업을 진행하는 것을 Dynamic Programming이라고 기억해 두자. 위의 문제를 다른 방법으로 풀 수 있는 예제를 찾는다면 더 잘 이해가 될 것 같다.

profile
새로운 도전을 멈추지 않는편👊 / 주어진 상황에 최선을 다하는 편🏋 / 아는 것을 전달하는 것에 보람을 느끼는 편💪

0개의 댓글