[프로그래머스] 숫자 변환하기(Java), DP & BFS 알고리즘

DP(Dynamic Programming) 알고리즘

다이나믹 프로그래밍이란?

- 하나의 큰 문제를 여러 작은 문제로 나누어 그 결과를 저장하고, 다시 큰 문제를 사용할 때 사용하는 것
- 앞에서 계산한 식을 배열에 미리 저장해 연산속도를 증가시키는 프로그래밍
 

DP 구현 단계

1. 문제를 하위 문제로 쪼갬
2. 하위 문제를 재귀적으로 해결함
3. 결과를 저장함 : 메모이제이션
4. 저장된 결과를 이용해 큰 문제를 해결함
 

메모이제이션이란?

동적 계획법에서 사용되는 저장 공간으로, 이전에 계산한 값을 저장해두었다가 나중에 같은 값을 계산할 때 다시 계산하지 않고 이전에 계산한 값을 활용함으로써 계산 속도를 높인다. -> 해시 테이블, 배열 등으로 구현
 

동적 계획법의 종류

1. 탑다운(Top-Down) 방식

: 큰 문제를 해결하기 위해 작은 문제를 호출하는 방식
+) 작은 문제들의 결과값을 저장해 동일한 계산을 반복하지 않아 시간 복잡도가 감소함
-) 스택 오버플로우 발생 가능성이 있음
 

2. 바텀업(Bottom-Up) 방식

: 작은 문제부터 차례대로 해결해 나가는 방식
+) 부분 문제의 해를 저장하고 이를 활용해 다음 문제를 해결함으로써 시간 복잡도가 감소함
-) 초기값을 설정해줘야 하고, 작은 문제들의 결과값을 임시적으로 저장해 둘 공간이 필요함

---

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

---

문제 풀이

1. 동적 계획법을 사용한 풀이 사용

class Solution {
    public int solution(int x, int y, int n) {
        int answer = 0;
        int[] dp = new int[y+1];
        
        for(int i=x; i<=y; i++) {
            
            if(i != x && dp[i] == 0) {
                dp[i] = -1;
            } else {
                if(n + i <= y) {
                    // 1. x에 n을 더함
                    if(dp[n+i] == 0) {
                        dp[n+i] = dp[i] + 1;
                    } else {
                        dp[n+i] = Math.min(dp[i] + 1, dp[n+i]);
                    }
                }
            
                if(i * 2 <= y) {
                    // 2. x에 2를 곱함
                    if(dp[i*2] == 0) {
                        dp[i*2] = dp[i] + 1;
                    } else {
                        dp[i*2] = Math.min(dp[i] + 1, dp[i*2]);
                    }
                }

                if(i * 3 <= y) {
                    // 3. x에 3을 곱함
                    if(dp[i*3] == 0) {
                        dp[i*3] = dp[i] + 1;
                    } else {
                        dp[i*3] = Math.min(dp[i] + 1, dp[i*3]);
                    }
                }
            }
        }    
            
        return dp[y];
    }
}

 

2. bfs 사용

import java.util.*;

class Solution {
    public int solution(int x, int y, int n) {
        Queue<Integer> q = new LinkedList<>();
        Map<Integer, Integer> visited = new HashMap<>(); // 방문 여부와 방문 횟수 체크용
        Integer[] arr = new Integer[3];
        q.add(x);
        visited.put(x, 0);
        
        int cnt = 0;
        while(!q.isEmpty()) {
            for(int i=0; i<q.size(); i++) {
                int num = q.poll();
	            cnt = visited.get(num) + 1; // 방문 횟수 추가

                if(num == y) {
                    return visited.get(num);
                }
                
                arr[0] = num * 3;
                arr[1] = num * 2;
                arr[2] = num + n;

                for(int j=0; j<3; j++) {
                    int maxNum = arr[j];
                    
                    if((!visited.containsKey(maxNum)) && maxNum <= y) {
                        q.add(maxNum);
                        visited.put(maxNum, cnt);
                    }
                }
                
            }
        }
        return -1;
    }
}