알고리즘 문제풀이 9

hyunju-song·2020년 10월 18일
0

ALGORITHM

목록 보기
10/14
post-thumbnail

주어진 소수점을 분수의 형태로 바꾸는 알고리즘 문제였다.
여기서 가장 유용하게 사용된, 메소드는

  • Math.pow(a,b) : a를 b만큼 곱하는 제곱메소드
  • Math.floor() : 주어진 수를 소수점 이하로 버림한 수를 반환
    -> Math.floor(10.1) = 10
    -> Math.floor(10.9) = 10
  • Match.ceil() : 주어진 수를 소수점 이하로 버리고 올림한 수를 반환
    -> Math.floor(10.1) = 11
    -> Math.floor(10.9) = 11
  • Math.round() : 소수점 이하로 버리고 반올림한 수
    -> Math.round(10.1) = 10
    -> Math.round(10.9) = 11
  • parseFloat() : 주어진 수를 실수로 바꾸기(소수점 나오게)
  • pareInt(): 주어진 수를 정수로 바꾸기
  • Math.max(a,b) : a,b 중에서 큰 수
  • Math.min(a,b) : a,b 중에서 작은 수
var toFraction = function (number) {
  let strNum = number.toString();
  //let numLength = strNum.length - 1; //왜냐면 소수점부분을 빼야 진짜 숫자의 갯수이므로 -1을 해준 것.
  let inputNum = number;
  if (strNum[0] === '-') {
    //주어진 인자가 음수라면
    //numLength = strNum.length - 2; //실제 숫자의 갯수는 소수점과, 마이너스 기호를 뺀 갯수이므로 -2 이다.
    //let minus = strNum.slice(1, strNum.length); //마이너스 기호를 뺀 숫자 부분을 발라냄(소수점자체는 포함)
    strNum = strNum.slice(1, strNum.length);
    inputNum = parseFloat(minus);
  }
  //위의 조건문 자체는 음수가 주어졌을때, 마이너스라는 기호를 배제하고 우선 수를 변환시키기 위한 작업을 위해 필요.

  //let ten = Math.pow(10, numLength - 1);
  //위의 변수는 소수점을 분수로 만들기 위해, 필요한 10의 제곱 수를 구하기 위함이다.
  //가령 2.5인 경우에는 10^1을 곱하고 그 분모로 들어가게 된다.
  
  //->이 부분은 미스였다. 10.2 같이 소수점 위의 정수 부분이 두자리 이상인 경우를 인지하지 못했다.
  let float = strNum.slice(strNum.indexOf('.')+1, strNum.length);
  //slice메소드는 앞에 위치한 인덱스(포함) 끝의 인덱스-1의 값만을 뽑아내서 새로운 배열을 만들어준다.
  let floatLength = float.length;

  let ten = Math.pow(10, floatLength);

  // 소수점이 0인 경우
  if (inputNum - Math.floor(inputNum) === 0) {
    return `${Math.floor(inputNum)}/1`;
  } else {
    // 소수점이 0이 아닌 경우 + 5로 나눠지는 경우

    let newNum = parseInt(inputNum * ten);
    // 주어진 수를 분수로 만들기 위해 10의 제곱 수 중 하나를 곱하고 나서 parseInt를 써주지 않으면, 소수점 이하의 0까지 같이 불린다.

    //두수의 최대공약수 구하기(소수점이 0이 아닌 수에 필요하다)
    let max = 1;
    // 우선 최대공약수는 최초로는 1로 선언. 공약수가 없는 두수가 있을 수도 있으므로
    //가령 number 0.88 일경우, 최대공약수 구해야 하는 수는 88과 100이된다. 두 수의 공약수 구할때는 비교하는 두수 중에
    //작은 수 까지만 비교하면 되므로, 88까지 반복문 돌린다
    // 아래의 경우에서 분자가 분모보다 큰 경우를 고려한 조건문을 넣어줘야한다.
    let small = Math.min(newNum, ten)
    
    for (let i = 1; i <= small; i++) {
      if (newNum % i === 0 && ten % i === 0) {
        max = i;
      }
    }
    if (number < 0) {
      return `-${newNum / max}/${ten / max}`;
    }
    return `${newNum / max}/${ten / max}`;
  }
};

해당 문제의 핵심은 최대공약수와 최소공배수에 대해 이해하고 알고리즘을 구현하는 것이 아닐까하는 생각이 들었다.

유클리드 호제법(최대공약수, 최소공배수 구하기)을 구현하는 알고리즘

  • 최대공약수를 구하는 알고리즘 코드
let originA = A;
let originB = B;
let GCD;

while (1) {
    let r = A % B;
    if (r === 0) {
      GCD = B;
      break;
    }
    A = B;
    B = r;
}
  • 최소공배수를 구하는 알고리즘 코드
    -> 이는 참고 블로그를 보면 알수있겠지만 구현하기 매우 쉽다.
    (한 10몇년 전에 학교에서 배운듯한 최소공배수의 원리는 결국
    최소공배수 = (A*B)/최대공약수이다.
    -> 따라서 위의 알고리즘 코드로 최대공약수를 구하면 쉽게 최소공배수도 구할 수 있다.
profile
코드 한 줄로, 세상의 가치를 만들자🌟

0개의 댓글