[2023-10-02] TIL - 동적계획법

동적계획법

- 해결한 작은 문제로 큰 문제를 해결하는 문제 풀이 방식

-> 두가지 방법론이 있다.

• 메모이제이션
• 타뷸레이션

 

메모이제이션

- 하향식 접근법

- 동적 계획법에서작은 문제들의 결과는 항상 같다.

- 결과들을 메모리에 저장해 필요할 때 꺼내 쓰는 것이 메모이제이션

ex) 기존 백트래킹을 통한 피보나치 수열에서 중복되는 인자의 함수를 메모이제이션으로 미리 저장해 값을 빠르게 반환

f(n) = f(n-1) + f(n+1) -> 이처럼 규칙이 있다면 가능!

 

타뷸레이션

- 상향식 접근법

- 필요한 값들을 미리 계산해두는 것

- 메모이제이션은 필요할 때 계산하는 것, 타뷸레이션은 미리 계산하는 것

 

 

동적계획법 코딩테스트

https://programmers.co.kr/learn/courses/30/lessons/12983

프로그래머스

 

 

 

 

 

 

💢어려웠던 점

1. 효율성 테스트에서의 시간초과 - 문제의 조건

function solution(strs, t) {
    var answer = 0;


    let ans=Array(t.length+1).fill(0);
    for(let i=1;i<t.length+1;i++){
        ans[i]=Infinity
        for(let j=1;j<i+1;j++){
            let word = t.slice(i-j,i);
            if(strs.indexOf(word)!==-1){
                ans[i]=Math.min(ans[i],ans[i-j]+1)
            }
        }
    }
    console.log(ans)
    
    return ans[ans.length - 1] === Infinity ? -1 : ans[ans.length - 1];
}

- 이는 문제에서 주어지는 "모든 단어 조각의 길이는 1이상 5이하입니다."를 잘 봐야한다.

...
 
 for(let i=1;i<t.length+1;i++){
        ans[i]=Infinity
        for(let j=1;j<i+1;j++){
        	...
            
        ...

- slice를 위한 j 변수를 그저 i +1을 하는 것이 아닌 그 이상 커질 경우 6으로 고정 시키는 명령어가 필요하다.

- 아래와 같이 해결하면 효율성 테스트에서 성공할 수 있다.

for(let j=1;j<Math.min(i + 1, 6);j++){ ... }

2. 효율성 문제 - 문자열 검색

- 이는 주어진 문자열 strs에서 해당 문자가 존재하는지에 대해 검사하는 코드에서 효율성이 떨어지게 된다.

if(strs.indexOf(word)!==-1){
    ans[i]=Math.min(ans[i],ans[i-j]+1)
}

- 이 코드를 다른 방식으로 바꿔줘야한다.

- 그래서 문자열을 검색할 때 빠른 효율을 위한 Set()을 사용해야한다.

const strsSet = new Set(strs);

...


if (strsSet.has(word)) {

    ans[i] = Math.min(ans[i], ans[i - j] + 1);
}

3. 문제 도식화