Dynamic Programming

💡 다이나믹 프로그래밍은 어떤 상황에서 사용하나요?

→ 컴퓨터는 빠르지만, 무한대로 빠른 것은 아닙니다. 컴퓨터에도 연산 속도에 한계가 있습니다. 또한, 메모리 공간도 한정적이죠.
    이로인해 개발자들은 연산 속도와 메모리 공간을 최대한 활용할 수 있는 알고리즘을 작성해야합니다. 이를 위한 대표적인 방법이
    다이나믹 프로그래밍입니다. 동적 계획법이라고도 불리며, 1) 큰 문제를 작은 문제로 나눌 수 있으며, 나눈 작은 문제를 풀면 큰 문제
    를 풀 수 있을 때 2) 그 작은 문제들이 중복 되는 문제일 때. 다이나믹 프로그래밍을 사용합니다.

 

 

 

💡 왜 다이나믹 프로그래밍 인가요? 다른 알고리즘으로는 불가능한가요?

→ 아니요, 다른 알고리즘으로도 가능합니다. 겹치는 하위 문제들이 있는 경우에도 재귀적으로 호출하는 재귀 알고리즘이나 
     최적의 답을 찾는 그리디 알고리즘, 모든 조합을 찾는 조합적인 방법까지 다양한 알고리즘을 사용할 수 있지만, 하위 문제들이

     겹치고, 경우의 수가 많을 경우 제대로 해결되지 않는 경우가 발생할 수 있습니다. 따라서 겹치는 하위문제들이 있는 경우에는
     다른 알고리즘으로도 해결 할 수 있겠지만, 다이나믹 프로그래밍으로 해결했을 때가 가장 효율적입니다.

 

 

 

 

[DP] 금고를 털어라

 

 

자신이 감옥에 간 사이 연인이었던 줄리아를 앤디에게 빼앗겨 화가 난 조지는 브레드, 맷과 함께 앤디 소유의 카지노 지하에 있는 금고를 털기로 합니다. 온갖 트랩을 뚫고 드디어 금고에 진입한 조지와 일행들. 조지는 이와중에 감옥에서 틈틈이 공부한 알고리즘을 이용해 target 금액을 훔칠 수 있는 방법의 경우의 수를 계산하기 시작합니다.

예를 들어 $50 을 훔칠 때 $10, $20, $50 이 있다면 다음과 같이 4 가지 방법으로 $50을 훔칠 수 있습니다.

• $50 한 장을 훔친다
• $20 두 장, $10 한 장을 훔친다
• $20 한 장, $10 세 장을 훔친다
• $10 다섯 장을 훔친다

훔치고 싶은 target 금액과 금고에 있는 돈의 종류 type 을 입력받아, 조지가 target 을 훔칠 수 있는 방법의 수를 리턴하세요.

 

 

function ocean(target, type){ // (훔칠 수 있는 금액, 돈의 종류의 type 배열)
	
    let bag = [1];
    // bag은 target 금액을 만들 수 있는 경우의 수를 기록 하는 것. 
    // 초기화 하려고 bag[0] = 1 >> 0원을 만들기 위해 아무것도 선택하지않는 선택 하나를 해야함.
    // 예를 들어, bag[3] = 은 type이 [1,2,5]인 경우 1 1개, 2 1개 를 선택하는 것 / 1 3개를 선택하는 것 2가지의 경우가 있기에
    // bag[3]=2 , 이런식으로 이용할 것.
    
    
    // i는 만드려는 금액, 따라서 경우의 수 기록을  target 금액 만큼의 길이를 가진 배열로 만듦. (초기화 시킴 === 0)
    // 제일 끝자리를 만들기 위한 경우의 수, 두번째 자리를 만들기 위한 경우의 수 이렇게 나누려고하는 것.
    for(let i = 1; i <= target; i++) bag[i] = 0;
    
    
    //돈의 종류가 담겨있는 배열 type을 순차적 탐색
    for(let i = 0; i < type.length; i++){
    
    // target 금액까지 순차적으로 1씩 증가
    	for(let j = 1; j <= target; j++){
        
        //bag의 인덱스가 type[i] 보다 크면 (작으면 금액이 더 작은것이므로 만들 수가 없음 그래서 따로 확인하지 않음)
        	if(type[i] <= j){
            
            //기존 경우의 수에 type[i]를 뺀 금액을 만들 수 있는 경우의 수를 더해줌 (type[i]는 갖고 있는 돈의 종류이고,
            //이걸 추가하면 target의 돈이 되니 경우의 수로 추가할 수 있음)
            	bag[j] += bag[j - type[i]];
            }
        }
    }
    // 쌓인 경우의 수를 리턴
    return bag[target]
}

 

💡 다른 알고리즘보다 다이나믹 프로그래밍 코드가 더 이해가 되지 않는다.

→ 어떻게 코드를 진행해야할 지 감이 잘 안잡히는 것 같다. 개념으로는 이해가 되고, 작은 부분의 공통된 점을 찾아서 이를 해결시키면
    되는 것 같은데 큰 문제의 최적해가 작은 문제의 최적해들로 구성되게 코드를 짜야한다는 것에서 잘 모르겠다. 
    위의 경우를 생각해보자, 훔치고 싶은 금액을 몇가지 방법으로 훔칠 수 있는지가 큰 문제이다.
    작은 문제는 그 금액을 달성하는데 필요한 동전의 개수를 제한 해서 경우의 수를 하나씩 구해가는 것이다.

    1) 10 달러로 금액을 달성하는 경우
    2) 10, 20 달러로 금액을 달성하는 경우 (무조건 20이 있어야 한다.)

    3) 10, 20, 50 달러로 금액을 달성하는 경우 (무조건 50이 있어야 한다.)

    1) + 2) + 3)을 합하면 큰 문제를 해결할 수 있다. 

    문제 안에서 큰 문제와 작은 문제를 분류해서 작은 문제를 어떻게 합치면 큰 문제를 해결할 지 반복해보는 것이 중요할 것 같다.