이진수 함수 dfs로 구현하기

dfs를 활용해서 10진수를 => 2진수로 변환하는 함수 구현해보자. 

 

내가 틀린 코드까지 작성한 이유는, 

완전히 깊은 이해를 하길 바라서다. 

 

01. undefined 가 나와버린다. 

let answer = []; 
  function dfs(num){
      if(num <= 0) return answer.join(''); 
      else{
         return dfs(parseInt(num/2));  
          answer.push(num%2); 
    
      }
  }
    console.log(dfs(20))

 

문제는 return 문이 재귀 호출 이전에 위치하고 있기 때문에 발생합니다. return 문은 함수를 즉시 종료시키고 값을 반환하기 때문에, 재귀 호출 이후의 코드는 실행되지 않습니다. 따라서 answer.push(num % 2);가 실행되지 않고 함수가 종료되어 answer 배열에 값이 추가되지 않고 빈 배열 상태로 유지됩니다. 이로 인해 undefined가 반환됩니다.

해결 방법은 return 문을 올바른 위치로 이동하여 재귀 호출 이후에 실행되도록 해야 합니다. 아래는 수정된 코드입니다.

 

02. gpt가 알려준 방식 

 

let answer = [];

function dfs(num) {
    if (num <= 0) return answer.join('');
    else {
        dfs(parseInt(num / 2));
        answer.push(num % 2);
        return answer; // 재귀 호출 이후에 return 문을 추가
    }
}

console.log(dfs(20));

answer.join('')삭제해도 된다. 

이건 배열로 반환

이건 문자열로 반환

 

 

과정 

1. dfs(18)를 호출합니다.
2. num이 0보다 크므로 else 블록으로 들어가게 됩니다.
3. dfs(parseInt(18/2))를 호출하여 dfs(9)를 실행합니다.
4. dfs(9)에서도 마찬가지로 num이 0보다 크므로 다시 dfs(parseInt(9/2))를 호출하여 dfs(4)를 실행합니다.
5. dfs(4)에서도 마찬가지로 num이 0보다 크므로 다시 dfs(parseInt(4/2))를 호출하여 dfs(2)를 실행합니다.
6. dfs(2)에서도 num이 0보다 크므로 다시 dfs(parseInt(2/2))를 호출하여 dfs(1)를 실행합니다.
7. dfs(1)에서도 num이 0보다 크므로 다시 dfs(parseInt(1/2))를 호출하여 dfs(0)를 실행합니다.
8. dfs(0)에서는 num이 0이므로 return하여 재귀 호출을 종료합니다.
9. 이제 각 호출에서 스택으로부터 순차적으로 빠져나가며 answer 배열에 값을 추가합니다.

   • dfs(1)에서 answer.push(1 % 2) 실행: answer = [1]
   • dfs(2)에서 answer.push(2 % 2) 실행: answer = [0, 1]
   • dfs(4)에서 answer.push(4 % 2) 실행: answer = [0, 0, 1]
   • dfs(9)에서 answer.push(9 % 2) 실행: answer = [1, 0, 0, 1]
   • dfs(18)에서 answer.push(18 % 2) 실행: answer = [0, 1, 0, 0, 1]
10. 마지막으로 answer.join('')를 호출하여 101001을 반환합니다.
11. 따라서 console.log(dfs(18))는 101001을 출력합니다.

 

03. 선생님의 풀이 

 

    let answer = ''
  function dfs(num){
      if(num === 0) return; 
      else{
         dfs(parseInt(num/2));  
          answer+=String(num%2) 
      }
  }
    dfs(18)
    console.log(answer)

 

04. 아까 내 코드도 수정할 수 있지 않을까? 

 let answer = []; 
  function dfs(num){
      if(num <= 0) return //0이 되는순간 함수 종료시켜
      else{
         dfs(parseInt(num/2));  
          answer.push(num%2); //그럼 이게 실행된다. 
      }
  }
    dfs(20)
    console.log(answer.join('')) //answer에 다 저장된거 join 시켜