DP

동적 계획법이란 큰 문제를 작은 문제들로 풀어내는 것을 말한다. Bottom Up 방식이다. 작은 문제들부터 계산하여 큰 문제들을 해결한다.

조건
1️⃣ 작은 문제들의 반복인 경우

피보나치의 경우 F(5)를 구하기 위해선 F(4) F(3)이 필요하고, F(4)를 구하기 위해선 F(3), F(2)가 필요하다. 작은 문제들이 반복된다.

2️⃣ 같은 문제는 구할 때 마다 정답이 같다.

memoization
한번 계산한 작은 문제는 그 값을 찾을 수 있는 자료구조에 저장해둔다. 다시 계산하지 않도록 캐싱, 메모이제이션 해둔다.

TIP
가장 작은 문제부터 생각하고 나아가다보면 규칙을 발견하게되고, 점화식을 도출해낼 수 있게된다.

Fibonacci

n번째 항이 이전 항들로 값을 구할 수 있다.

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    let array = [...new Array(n+1)].map(()=>-1);
    array[0] = 0;
    array[1] = 1;
    for(let check=2;check<=n;check++){
        array[check] = array[check-1]+array[check-2];
    }
    return array[n];
};

Count Sorted Vowel Strings

/**
 * @param {number} n
 * @return {number}
 */
var countVowelStrings = function(n) {   
    let dp = [1,1,1,1,1];
    for(let i=1;i<n;i++){
        for(let j=0;j<dp.length;j++){
            dp[j] = dp[j] + (dp[j-1] || 0);
            
        }
    }
    return dp.reduce((a,b)=>a+b)
};

상상하기 쉽지가 않다...

주어진 n-1번만큼 반복한다. n-1 반복때는 dp배열에 정답 배열이 만들어 지게된다.

그림을 보면 현재 반복 횟수를 i라 check라 할때 check-1번의 dp[i] + check 번의 dp[i-1] 이 check 번의 dp[i]값이 된다.

dp[i] (check번의) = dp[i] (check-1번의) + dp[i-1] (check번의)

BFS

subway transfer nums

정류장 별로 어떤 라인으로 갈아탈 수 있는지를 저장한다

어떤 라인에 어떤 정류장이 있는지 인자로 온다.

이 두 가지 자료구조를 가지고 BFS 이용하여 풀 수 있다.

시간 초과

/**
* @param {number[][]} routes
* @param {number} source
* @param {number} target
* @return {number}
*/
var numBusesToDestination = function(routes, source, target) {
   let flag = false;

   routes.forEach((route)=>{
       if(route.includes(source) && route.includes(target)){
           flag = true;                    
       }
   })
   if(flag) return source === target ? 0 : 1;
   
   let answer = -1;    
   let busLine = {}
   let queue = [];
   let finish = [];
   let visited = [];
   routes.forEach((route,idx)=>{
       visited[idx] = false;
       route.forEach(sta=>{
           if(busLine[sta]){
               busLine[sta].push(idx);
           }else{
               busLine[sta] = [idx];
           }
       })  
   })
   // bus번호로 호선 번호를 만듬
   
   // 처음 시작 지점에서 탈 수 있는 호선들을 큐에 넣는다.
   busLine[source].forEach(possible=>{
       // 호선, 횟수, 갈아타는 버스 번호
       queue.push([possible,0,source]);
   })
   while(queue.length !== 0){
       // 호선 횟수 갈아타서 온 버스 번호를 받는다.
       const [possibleIdx,ans,station] = queue.shift();
       
       // 현재 호선 트루로 바꾼다.
       visited[possibleIdx] = true;
       // 현재 호선에서 갈 수 있는 버스 정류소 들을 알아둔다.
       const possibleBusStops = routes[possibleIdx]
       
       
       for(let i=0;i<possibleBusStops.length;i++){
           
           // 버스정류소가 [1,2,7] 이면 1번 버스일 때 갈 수 있는 호선들을 받아둔다.
           const possible = busLine[possibleBusStops[i]];
           
           
           // 갈 수 있는 호선 체크
           for(let j=0;j<possible.length;j++){
               
               // 호선이다.
               const line = possible[j];
               
               // 이미 방문한 호선이면 큐에 넣지 않는다.
               if(!visited[line]){
                   if(routes[line].includes(target)){
                       // 종료
                       return station === possibleBusStops[i] ? ans+1:ans+2;
                   }else{
                       // 큐에 푸시
                       queue.push([line,ans+1,possibleBusStops[i]]);
                   }
               }
           }
           
       }
   }
   return answer;

};

속도 상승

/**
 * @param {number[][]} routes
 * @param {number} source
 * @param {number} target
 * @return {number}
 */
var numBusesToDestination = function(routes, source, target) {
    let flag = false;

    routes.forEach((route)=>{
        if(route.includes(source) && route.includes(target)){
            flag = true;                    
        }
    })
    if(flag) return source === target ? 0 : 1;
    
    let answer = -1;    
    let busLine = {}
    let queue = [];
    let visited = [];
    routes.forEach((route,idx)=>{
        visited[idx] = false;
        route.forEach(sta=>{
            if(busLine[sta]){
                busLine[sta].push(idx);
            }else{
                busLine[sta] = [idx];
            }
        })  
    })
    busLine[source].forEach(possible=>{
        visited[possible] = true;
        queue.push([possible,0]);
    })
    while(queue.length !== 0){
        const [갈수있는라인,ans] = queue.shift();
        const 현재호선에서탈수있는버스 = routes[갈수있는라인]
        
        
        for(let i=0;i<현재호선에서탈수있는버스.length;i++){
            const 현재호선에서갈수있는호선 = busLine[현재호선에서탈수있는버스[i]];
            for(let j=0;j<현재호선에서갈수있는호선.length;j++){
                const line = 현재호선에서갈수있는호선[j];
                if(!visited[line]){
                    if(routes[line].includes(target)){
                      // 만약 다음라인에 목적지 있다면 ans+2해주면된다. (버스를 타고 갈아타는 버스로 가서 또 도착버스까지 이동해야함) 
                      // 갈아타는 버스가 목적지이게되면 이전에 이미 답이 도출되었다. 
                        return ans+2;
                    }else{
                        visited[line] = true;
                        queue.push([line,ans+1]);
                    }
                }
            }
            
        }
    }
    return answer;

};

diff

큐에 넣을 때 방문을 찍는다. 그렇게 되면 큐에서 아직 나오지 않았음에도 중복된 노드는 큐에 들어가지 않는다.

큐에 나올 때 방문을 찍게되면. 큐에서 나오기 전까지 중복된 노드들은 모두 큐에들어가 큐를 전부 탐색하는데 시간이 오래 걸리게 된다.

...

   busLine[source].forEach(possible=>{
        visited[possible] = true; // <- diff
        queue.push([possible,0]);
    })
    while(queue.length !== 0){
        const [갈수있는라인,ans] = queue.shift();
        const 현재호선에서탈수있는버스 = routes[갈수있는라인]
        
        
        for(let i=0;i<현재호선에서탈수있는버스.length;i++){
            const 현재호선에서갈수있는호선 = busLine[현재호선에서탈수있는버스[i]];
            for(let j=0;j<현재호선에서갈수있는호선.length;j++){
                const line = 현재호선에서갈수있는호선[j];
                if(!visited[line]){
                    if(routes[line].includes(target)){
                        return ans+2;
                    }else{
        				visited[possible] = true; // <- diff
                        queue.push([line,ans+1]);
                    }
                }
            }
            
        }
    }
...

시간 초과 : 큐에 나올 때 방문을 찍었음 (중복된 노드들이 큐에 들어가게됨)

1105ms : BFS 도중에 큐에들어가는건 방문을 찍고 큐에 집어넣었음 (처음 큐에 넣는 거를 제외하곤 방문이 찍히고 큐에 들어가게됨)

689ms : 처음 큐에 넣는 거도 방문을 찍고 큐에 집어넣음

Description

버스로 갈 수 있는 호선들을 조사해 큐에 넣는 것이다. 이를 위해 두개의 자료구조를 만들었다. 하나는 인자로 오는 routes 나머지 하나는 버스 번호 - 갈수있는 호선배열로 되어있는 해쉬 자료구조이다.

처음 시작점에서 갈 수 있는 호선들을 큐에 집어넣는다. 이 때 버스 번호를 넣어주어야