TIL 23.04.05 - DP(동적계획법)

오늘은 동적계획법(dp)에 대해서 배웠고 관련 문제를 풀었다.

 

DP라고 하는 알고리즘은,

탐욕 알고리즘과 같이 작은 문제에서 출발한다는 점은 같지만,

DP는 모든 경우의 수를 조합해 최적의 해법을 찾음

두 가지 가정이 만족하는 조건에서 사용

• Overlapping Sub-problems : 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견
• Optimal Substructure : 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답을 큰 문제에서도 사용 가능

 

DP 문제 예시

문제

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

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

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

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

입력

인자 1: target

• Number 타입의 100,000 이하의 자연수

인자 2: type

• Number 타입을 요소로 갖는 100 이하의 자연수를 담은 배열

출력

• Number 타입을 리턴해야 합니다.
• 조지가 target을 훔칠 수 있는 방법의 수를 숫자로 반환합니다.

---

function ocean(target, type) {
  // TODO: 여기에 코드를 작성합니다.
  let dp = []
  type.sort((a,b)=>a-b)

  //dp 초기화
  for(let i=0;i<=target;i++){
    dp.push(0)
  }

  for(let i of type){
    //dp[i]에 1을 더해주기
    dp[i]+=1
    for(let j=i;j<=target;j++){
        //현재dp[j-i]에서 i를 추가했을 경우를 더해주기
        dp[j] += dp[j-i]
    }

  }
  return dp[target]
}

 

 

해당 문제는 type에 있는 돈을 이용하여 target 금액을 조합하는 방법의 수를 구하는 것이다.

 

dp배열을 target의 크기+1 만큼 생성하여 , 금액을 조합하여 가장 마지막 값인 dp[target]을 구하는 문제이다.

1. 우선 dp의 값을 모두 0으로 초기화 해준다.

 

2. type을 순회 하면서 type의 원소인 i를 받고, dp[i]를 1증가 시켜준다.(i를 조합하여 i를 만드는 수=1 추가)

 

3. i부터 target까지 j를 순회하면서 기존 dp[j]값에 dp[j-i]를 더해준다.

(j-i와 i를 조합하여 j를 만드는수는 dp[j-i]와 같음)

 

4. 해당 방식으로  2,3을 반복한 뒤 dp[target]을 출력한다.