다이나믹 프로그래밍

🗓️ 2023-01-09(월) ~ 2023-01-15(일)
KOALA 9기 코딩테스트반

🚀 최적화 문제를 푸는 방법은 두 가지가 있다.
1. 모든 상황을 고려해 최적의 방법을 찾는 것 → DP
2. 그때 그때 가장 최선의 방법을 선택해 답을 구하는 방법 → Greedy

🔍 다이나믹 프로그래밍

---

다이나믹 프로그래밍은 문제의 일부분을 풀고 그 결과를 재활용하는 방법이다.
한 번 계산했던 값은 저장한다는 점에서 (Memoization, 메모이제이션) 분할정복 알고리즘과 다르다.

1. 반복되는 서브 문제 (Overlapping Subproblem)
   메인과 서브 문제를 같은 방법으로 해결할 수 있어야 한다.

2. 최적 부분 구조 (Optimal Substructure)
   메인 문제 해결 방법을 서브 문제에서 구하여 재사용하는 구조여야 한다.

Top Down

• 재귀함수를 사용해서 DP를 구현하는 방법이다.
• 큰 문제를 쪼개며 작은 문제로 만들고 다시 합쳐서 원래 문제를 푸는 방식이다.

Bottom Up

• 반복문을 사용해서 DP를 구현하는 방법이다.
• 작은 문제들을 모아서 큰 문제를 만들어 쌓아 올려가는 방식이다.

🔐 문제를 풀 때
1. 주어진 문제를 보고 규칙이나 일반화시킬 수 있는 것을 찾아서 점화식으로 만든다.
2. 점화식을 바탕으로 Top-down이나 Bottom-up 방식 중 하나를 선택해서 구현한다.

💬 적용 가능한 문제
가장 긴 증가하는 부분 수열 : LIS (Longest Increasing Subsequence)
최장 공통 부분 수열 : LCS (Longest Common Subsequence)
배낭 문제 : knapsack problem

🪄 N으로 표현

function solution(N, number) {
    const dp = new Array(9).fill(0).map(() => new Set());
    
    for(let i = 1; i < 9; i++){
        dp[i].add('1'.repeat(i) * N);
        for (let j = 1; j < i; j++) {
            for(const first of dp[j]){
                for(const second of dp[i-j]){
                    dp[i].add(first + second);
                    dp[i].add(first - second);
                    dp[i].add(first * second);
                    dp[i].add(first / second);
                }
            }
        }
        if(dp[i].has(number)) return i; 
    }
    return -1;
}

🔍 Greedy

---

그리디 알고리즘은 선택의 순간마다 최적이라고 생각되는 것을 선택해 나가는 방식이다.
최적의 해를 보장하지 않지만, 계산 속도가 빨라 근사 알고리즘으로 사용하기도 한다.

1. 탐욕적 선택 속성 (Greedy Choice Property)
   앞의 선택이 이후의 선택에 영향을 주지 않아야 한다.

2. 최적 부분 구조 (Optimal Substructure)
   메인 문제 해결 방법은 서브 문제에 최적 결과로 구성되야 한다.

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

🪄 체육복

function solution(n, lost, reserve) {
    let lostStudent = lost.sort((a,b) => a-b).filter(student => !reserve.includes(student));
    let reserveStudent = reserve.sort((a,b) => a-b).filter(student => !lost.includes(student));

    const missStudent = lostStudent.filter(lostNum => {
        const borrow = reserveStudent.find(reserveNum => Math.abs(reserveNum - lostNum) === 1);
        if(!borrow) return lostNum;
        reserveStudent = reserveStudent.filter(student => student !== borrow);
    })
  
    const attendStudent = n - missStudent.length;
    return attendStudent;
}