탐욕알고리즘(Greedy)

Greedy의 사전적 정의는 "탐욕스러운, 욕심 많은" 이란 뜻을 지니고 있습니다. 말 그대로 탐욕 알고리즘은 결정의 순간마다 당장 눈앞에 보이는 최적의 상황만을 선택하여 해답에 도달하는 방법입니다. 대표적인 예시로는 거스름돈을 나눠주는 방법이 있습니다. 이를 로직으로 적어보면

1. 동전의 개수를 줄이기 위해 가장 가치가 있는 동전부터 먼저 거슬러 줍니다.
2. 가장 가치있는 동전으로 거슬러 줄 금액을 초과한다면 한단계 작은 동전을 선택하여 다시 거슬러 주는 방식을 반복합니다.

탐욕알고리즘(Greedy) 로직

코드스테이츠에서 나온 탐욕알고리즘(Greedy) 문제로 짐나르기 코플릿에서의 저의 로직을 적어보겠습니다. 용량제한이 있는 박스를 최대한 덜 쓰고 짐을 나눌 때 박스의 개수를 구해야 합니다. 해당 함수의 받는 인자로 짐의 무게를 적은 배열, 용량제한 값입니다.

1. 짐의 무게를 무거운 것 부터 작은 것으로 정렬하기 위해 내림차순으로 정렬한다.
2. 첫번째 짐과 두번째짐을 비교하여 둘의 합이 무게가 용량제한보다 작다면 같이 넣어주고 박스개수를 카운트 해주고 남은 짐에 대해서 다시 함수를 돌린다.(재귀함수 사용)
3. 첫번째 짐과 두번째짐을 비교하여 둘의 합이 무게가 용량제한보다 크다면 첫번째 짐만 박스에 넣고 카운트를 하고 남은 짐 배열에 대해서 다시 함수를 돌린다.

Dynamic Programming(DP)

동적계획법이라고 불리는 Dynamic Programming은 모든 경우의 수를 따져본 후에 이를 조합해 최적의 해법을 찾는 방식입니다. 주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 문제 해결 방식에서 하위 문제를 계산한 뒤 그 해결책을 저장하여, 후에 같은 하위 문제가 나왔을 경우 저장된 해결책을 이용하여 계산 횟수를 줄임으로써 비효율적인 알고리즘을 개선하는 방법입니다. 즉, 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이 바로 이 다이내믹 프로그래밍입니다.

주어진 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합하여 최종 문제를 해결하는 대표적인 예시로는 피보나치가 있습니다.

function fibonacci(num) {
  if(num === 0){
    return 0;
  }
  if(num === 1){
    return 1;
  }
  return fibonacci(num - 1) + fibonacci(num - 2);
}

여기서
fibonacci(5)를 하게되면 fibonacci(4) + fibonacci(3) = fibonacci(3) + fibonacci(2) +fibonacci(3)... 이런식으로 같은 값이 반복되어 나옵니다. 만약 num의 값이 5가 아니라 100, 1000, 10000이면 중복되는 함수실행이 더욱 늘어나게 되고 매우 비효율적인 계산 방식이라고 생각합니다. 그렇기 때문에 기존에 값이 나왔던 적이 있다면 그 값을 저장하여 값을 바로 활용할 수 있게 만든는 것이 Dynamic Programming입니다.

Dynamic Programming(DP) 로직

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);
    memo[n] = res;
    
    return res;
}

메모 배열을 추가해 줌으로써 값을 저장할 공간을 설정한뒤 기존에 한번 나왔던 값이면 그 값을 메모 배열에 저장함으로써 반복되는 계산을 줄일 수 있습니다.