[프로그래머스] 숫자 변환하기

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

프로그래머스

---

숫자 x가 주어졌을 때, x에 2 또는 3을 곱하거나 n을 더해 y를 만들 수 있는 경우의 수 중 최소 연산 횟수를 구하는 문제이다. 뭔가 동적 계획법을 적용하면 좋을 것처럼 보인다.

하향식 방법

맨 처음에는 하향식 동적 계획법을 적용, 주어진 각각의 연산이 숫자에 대해 수행 가능한 경우, 해당 값들 중 최소값을 선택하여 캐시에 기록하며 처리하는 방식을 고려했다.

function solution(x, y, n) {
  const cache = new Map();
  
  function dyn(num) {
      if(num < x) return Infinity;
      if(num === x) return 0;

      const cached = cache.get(num);
      if(cached != undefined) return cached;
      
      const values = [];
      
      if(num % 3 === 0) values.push(dyn(num / 3) + 1);
      if(num % 2 === 0) values.push(dyn(num / 2) + 1);
      if(num - n >= x) values.push(dyn(num - n) + 1);
      else values.push(Infinity);
      
      const result = Math.min(...values);
      cache.set(num, result)
      return result;
  }
  const val = dyn(y);
  
  return val === Infinity ? -1 : val;
}
// x + n
// x * 2
// x * 3

// 연산의 최소 횟수

 이 방식의 경우 정확도가 62.5 %가 나왔다. 실패한 경우는 모두 런타임 에러였다. 분명 코드는 문제가 없는 것 같은데 왜 이럴까 생각해서 질문하기를 조금 참고하니, 재귀 스택 한계 때문에 에러가 발생한다는 이야기를 보게 되었다.

  정보를 찾아보니, 노드 기본 기준으로 함수 콜 스택의 크기가 1000을 넘지 않는다는 것을 알았다. 

node --v8-options | grep -B0 -A1 stack-size
# 984

# https://stackoverflow.com/questions/71237313/how-to-change-stack-size-limit-in-nodejs

위 명령을 리눅스 환경(또는 wsl)에서 입력하면 노드의 함수 콜 스택 크기를 알 수 있다. 나의 환경에서는 984가 출력되었는데, y = 1,000,000 와 n = 1 같은 최악의 상황에서는 대략 100만번의 콜 스택이 쌓일 수 있으므로 자바스크립트에서는  하향식 동적 계획법을 사용하지 않는 편이 좋아 보인다.

위 코드와 동등한 수준의 코드를 파이썬으로 작성하면 다음과 같다.

from sys import maxsize
from sys import setrecursionlimit
setrecursionlimit(1000001)
def solution(x, y, n):
    cache = {}
    def dyn(num):
        if num < x: return maxsize
        if num == x: return 0
        
        value = cache.get(num)
        if value != None: return value
    
        values = []
        if num % 3 == 0: values.append(dyn(num / 3) + 1);
        if num % 2 == 0: values.append(dyn(num / 2) + 1);
        if num - n >= x: values.append(dyn(num - n) + 1);
        else: values.append(maxsize);
        
        result = min(values)
        cache[num] = result
        return result
    
    answer = dyn(y)
    return -1 if answer >= maxsize else answer

두 코드는 큰 차이가 없고, 조금 다른 부분은 answer >= maxsize인 것이다. python의 maxsize는 javascript의 Infinity와 달리 값을 더하면 해당 값만큼 더 커진다. 스택 크기를 충분히 늘리니까 100점이 나왔다.

사실 파이썬 3부터는 정수에 대한 상한 / 하한이 없어서 maxsize는 표현 가능한 최대값을 의미하지는 않는다고 한다. 현재 기계 수준에서 한번에 제공할 수 있는 2^63 - 1 크기를 의미한다고. 해당 범위 이후는 현재 소프트웨어 수준에서 연산하여 제공한다고 한다.

https://stackoverflow.com/questions/3477283/what-is-the-maximum-float-in-python

 무한대를 표현하는 다른 방법으로 float('inf')가 있으며, 이 값을 사용하는 경우 node와 동일하게 ==으로 표현 가능하다.

---

상향식 동적 계획법

하향식 방법은 함수 콜 스택을 고갈시키므로, 현재 상황에 적합하지 않다. 따라서 상향식 방법으로 해결해보자.

function solution(x, y, n) {
  const arr = new Array(y+1);
  arr.fill(Infinity);
  arr[x] = 0;
  for(let i = x; i <=y; i++) {
      if(arr[x] != Infinity){
          if(2 * x <= y) arr[2 * x] = Math.min(arr[2 * x], arr[x] + 1);
          if(3 * x <= y) arr[3 * x] = Math.min(arr[3 * x], arr[x] + 1);
          if(x + n <= y) arr[x + n] = Math.min(arr[x + n], arr[x] + 1);
      }
  }
  console.log(arr);
  return arr[y] === Infinity ? -1 : arr[y];
}

숫자는 백만개, 연산은 한번 당 많아야 3개라 총 연산은 많아봤자 3백만으로, 시간 내로 해결 가능한 수준이다. 따라서 그냥 x 부터 y 전까지 계속 연산하면서 y 값을 갱신하는 방법을 생각해볼 수 있다. 코드도 짧고 좋은 것 같다.

 동적 계획법 문제를 풀 때마다 커다란 배열을 선언하는 것을 내가 꺼려하는 느낌이 있다. 범용성 측면에서 상향식 방식이 더 좋으니까, 최대한 상향식으로 문제를 푸는 방향으로 가야겠다.