자바스크립트 알고리즘 풀기!!

원래는 매일매일 배운 개념을 적는 블로깅을 할려고 했으나 시간낭비(?)라는 생각이 들어 어려웠던 문제나 까먹을만한 내용을 적을려고한다.

오늘의 문제
Math.sqrt()를 쓰지않고 제곱근구하기.

예를들어 
 9 -> 3
 4 -> 2
 5 -> 2.23
 2 -> 1.414...
 7 -> 2.xxxx

예를들어 5의 제곱근을 구한다고 가정을 하고 코딩을 시작해보자.

1. 일단 하나의 추측값(guess value)이 필요하다.
   -.5의 제곱근을 구한다고 가정할때 추측값(guuss value)은 2라고 두었다. 왜냐하면 2를 제곱하면 4가 나오고 5랑 근사치이기 때문에 2로 설정을 함.
   코드로 나타낸다면

 function computeSquareRoot(num) {
   let guess = Math.floor(num / 2); // num = 5라고 가정한다면 2라는 값이 나옴.
 }

2. 내가 제곱근을 구할려는 값(여기에선 5)이랑 guess 값을 나눈다.(여기에서 정확한 값을 구하기 위해서 소숫점이하 8자리까지 구한다.)

 function computeSquareRoot(num) {
   let guess = Math.floor(num / 2); // num = 5라고 가정한다면 2라는 값이 나옴.
   let divide = num / guess;
   let demicalEight = Number(divide.toFixed(8));// toFixed 메소드를 사용하면 소숫점 8번째 자리까지 구할 수 있고 return값이 문자열이기 때문에 Number를 써서 숫자로 형변환을 하였다.   
} 

3. 우리가 구한 추측값이랑 나눈값(demicalEight)의 평균값, 즉 중간값을 찾는다.

 function computeSquareRoot(num) {
   let guess = Math.floor(num / 2); // 
   let divide = num / guess;
   let demicalEight = Number(divide.toFixed(8));//
   let average = (demicalEight + divide) / 2;   
} 

4. 이렇게 3번을 반복한다면 정확한 제곱근은 구할 수 없지만 매우 근접한 값을 구할 수 있다. 그리고 알아두어야 할점은 추측값이 계속 바뀌므로 2,3번째 추측값으로는

average 값을 guess에 대입하면 된다.

 function computeSquareRoot(num) {
  let guess = Math.floor(num / 2);
  let n = 0; // while문 조건식
  while(n < 3) {
    n++;
    let divide = num / guess;
    let demicalEight = Number(divide.toFixed(8));//
    let average = (demicalEight + guess) / 2; // 추측값이랑 나눈값 중간값구하기
    guess = average;   
  }
console.log('Math.sqrt()의 값: ', Math.sqrt(num);// 구할려는 값과 비교용
return guess;

결과를 보면 알겠지만
구할려는 값이 거의 비슷하게 나왔지만 9하고 16값이 이상하다.
9 -> 3, 16 -> 4가 나와야 하지만 소숫점이 나온다. 25의 제곱근 36의 제곱근등등 정수로 딱딱 떨어지는값들은 결과값 뒤에 소숫점이 나온다. 이럴경우를 조건식을 써서 예외처리를 해주면 괜찮을것 같다.

function computeSquareRoot(num) {
  let guess = Math.floor(num / 2);
  let n = 0; // while문 조건식
  while(n < 3) {
    n++;
    let divide = num / guess;
    let demicalEight = Number(divide.toFixed(8));//
    let average = (demicalEight + guess) / 2; // 추측값이랑 나눈값 중간값구하기
    let checkNum = Math.floor(average)// Math.floor는 뒤에 소숫점을 내릴때 사용
    if(checkNum * checkNum === num) {
      return checkNum;
    }
    guess = average;   
  }
console.log('Math.sqrt()의 값: ', Math.sqrt(num);// 구할려는 값과 비교용
return guess;

10이하의 값을 구할땐 매우 근사치가 나오지만
오차값이 있으므로 값이 클수록 저 코드는 쓰면 안된다. 그래서 추가적으로 밑의 코드를 짜보았다.

function computeSquareRoot(num) {
  let guess = Math.floor(num / 2);
   // while문 조건식
  while(true) {
    let divide = num / guess;
    let demicalEight = Number(divide.toFixed(8));//
    let average = (demicalEight + guess) / 2; // 추측값이랑 나눈값 중간값구하기
    let checkNum = Math.floor(average)// Math.floor는 뒤에 소숫점을 내릴때 사용
    if(checkNum * checkNum === num) {
      return checkNum;
    }
    else if (average * average < num) {
      guess = average;
      break;   
    }
    guess = average;
}
console.log('Math.sqrt()의 값: ', Math.sqrt(num));// 구할려는 값과 비교용
return guess;
}

맘에 드는 코드는 아니지만 시간나면 다시 한번 생각을 해보아겠다./.