문제
내 풀이
function solution(x, y, n) {
if(x===y) return 0;
let arr = [x];
let obj = {};
let count = 1;
while(arr.length){
let temp=[];
let res= 0;
for(let i = 0; i<arr.length; i++){
for(let j = 1; j<=3; j++){
if(j === 1) res = arr[i] * 2;
if(j === 2) res = arr[i] * 3;
if(j === 3) res = arr[i] + n;
if(res > y || obj[res]) continue;
if(res === y) return count;
obj[res]= count;
temp.push(res)
}
}
arr=temp;
count++;
}
return -1
}
기록 및 해설
- 여러가지 아이디어가 떠올랐는데, 재귀함수를 통한 완전탐색을 먼저 떠올렸다. x 부터 y까지 3가지 연산들을 중복을 포함한 순열로 푼다면 원하는 답을 찾을 수 있기 때문이다.
//첫번째 풀었던 답
function solution(x, y, n) {
let result = [];
if(x=== y) return 0;
const getP = (x, count) => {
if (x >= y) return;
for(let i = 1; i<=3; i= i+1){
let tempX = x
if(i === 1) tempX = x + n;//탐색의 순서를 바꾸어 보아도 효율성은 통과하지 못한다.
if(i === 2) tempX = x * 2;
if(i === 3) tempX = x * 3;
let tempCount = count + 1
if(tempCount > result[result.length-1]) return;
if (tempX === y) result.push(tempCount)
getP(tempX, tempCount)
}
}
getP(x,0);
if(result.length === 0) return -1;
return result[result.length-1]
}2.완전탐색의 효율성이 떨어지는 이유(1);
원하는 답은 구할 수 있다. 그러나 효율성 테스트를 통과하지 못한다. 모든 경우의 수를 확인하기 위한 완전탐색은 이전에도 말했지만 재귀함수 특유의 중복된 연산과, 불필요한 콜스택의 중첩을 막지 못한다.
게다가 문제는 '최소값'을 구하는 문제이지만, 문제와 같이 케이스가 많을 경우 최소를 구하는데에는 굉장히 비효율적이다. 완전탐색은 하나의 요소값의 조합이 중복으로 다 만들어 진 후에 그 다음 요소를 탐색하기 때문이다.
console.log(tempX) // 25, 30, 35, 40, ... 80 ... 95... 그렇다면 greedy알고리즘을 통해 x3을 먼저 탐색하며 구할 수 있는가? 없다. 이유는, 첫째로 n이 무슨수인지 모른다는 점. 둘째로 어떤수는 더하고 곱하는게 곱하고 더하는 것보다 더 빨리 도달할 수 있기 때문이다.
ex) x = 3, y = 8, n = 1 일때, '(3 + 1) x 2' 는 '(3 x 2) + 1 + 1' 보다 더 적은 연산을 한다.
3.재귀함수의 효율성이 떨어지는 이유(2);
재귀함수의 가장 큰 문제는, 가장 최근에 실행된 함수가 끝날때까지 함수들이 모두 콜스택에 쌓인다는 것이다. 이는 함수 내에 코드가 많을수록 기하급수적으로 늘어나는데, 심지어 위의 코드를 아래와 같이 바꿨을때는 콜스택이 꽉찼다는 오류로 문제를 통과하지 못했다.
아래의 정답은, 결과를 작은수부터 계산하여 불필요한 연산을 막기 위해, 그리고 연산 이후의 값이 중복되는 것을 막기 위해 코드를 수정해보았다.
//두번째로 수정한 답
function solution(x, y, n) {
if(x===y) return 0;
let result = -1;
let arr = [x];
const obj = {};
let count = 0;
const getP = (arr)=>{
let temp=[];
count++
for(let i = 0; i<arr.length; i++){
for(let j = 1; j<=3; j++){
let res = 0;
if(j === 1) res = arr[i] * 2;
if(j === 2) res = arr[i] * 3;
if(j === 3) res = arr[i] + n;
if(res > y || obj[res]) continue;
if(res === y) {
result = count;
return;
}
obj[res] = count;
temp.push(res)
}
}
getP(temp)
}
getP(arr)
return result;
}-
중복값은 객체의 키값을 넣어줌으로써 제거할 수 있었고, 최소값은 매 새로운 배열을 만들어 결과를 추가해줌으로써 dp식으로 만들어 구현해 보았다. 그러나 이러한 방식도 런타임 에러(스택초과)가 뜨는데, 그 원인을 생각해보니 결과가 나오기 전까지 모든 계산이나 연산들이 중첩스택으로 쌓일 생각을 하니 콜스택이 가득 차는 건 당연했다.
-
기존에 순열 문제를 접근할때, 4자리수일때 불필요한 연산을 포함한 40번의 함수실행정도가 있었다. 그 안에 코드까지 해서 약 최소 40 x f(n) 의 시간복잡도와 콜스택이 소요될 것으로 예상될 수 있지만, 이 함수블록 안쪽 마저도 간단하게 수들을 조합하는 정도에 그친다. 그러나 이 문제는 x 와 y의 차이가 클수록 효율은 급격하게 떨어지는데, 최소 수가 1, y가 100만일 경우는 최소 20번의 함수호출과 그 안의 2중 중첩문, 3의 제곱으로 늘어나는 temp까지 콜스택과 시간복잡도는 기하급수적으로 늘어나게 되기 때문이다.
- 사실 위의 코드는 바람직하지 못한 코드인데, 객체에 결과값들을 저장하는 방식이라고 한다면, 굳이 블록함수가 아니라, 메모제이션방식으로(결과로 덮어씌우는 방식) dp를 구현해도 되기 때문이다. 그렇다면 불필요한 스택제거는 물론, 가장 효율적인 방식으로 모든 경우의 수를 찾으며 결과에 도달할 수 있다.
function solution(x, y, n) {
if(x===y) return 0;
let arr = [x];
let obj = {};
let count = 1;
while(arr.length){
let temp=[];
let res= 0;
for(let i = 0; i<arr.length; i++){
for(let j = 1; j<=3; j++){
if(j === 1) res = arr[i] * 2;
if(j === 2) res = arr[i] * 3;
if(j === 3) res = arr[i] + n;
if(res > y || obj[res]) continue;
if(res === y) return count;
obj[res]= count;
temp.push(res)
}
}
arr=temp;
count++;
}
return -1
};7.이 처럼 전의 연산이 그 다음 연산의 결과에 영향을 미치는 알고리즘을 구현할 때, 그리고 탐욕법이 불가능 할 때, 객체와 같은 기전 값의 결과들을 저장해놓는 작업을 통해 dp로 구현할 수 있다. dp로 구현한다면 불필요한 콜스택의 중첩없이 원하는 값을 구할 수 있다.
