😊Today Learn

• 최대공약수를 구하는 알고리즘에 대해서 공부
• 주어진 숫자의 약수를 구하는 알고리즘에 대해서 공부.
• SQL쿼리문을 이용하여 데이터를 조회, 수정하는법에 대해 공부
• 다중 JOIN을 사용하여 원하는 결과값을 도출하는 것에 대해 공부.

느낀점이나 반성할점.

1. 코딩을 할때, 무조건 for문을 사용해서 해결하려고 하는 습관이 있음.
   for문으로 처음부터 끝까지 순회하여 모든것을 해결하려고 하는 경우 시간복잡도에 의해 결과를 도출하는데 시간이 오래 걸리기 때문에 시작복잡도를 고려하여 문제를 해결하는 것이 좋음.
2. 데이터베이스에서 정보를 빼올때, 즉 SQL 쿼리문을 작성할때는 어떻게 사용자가 원하는 정보가 무엇인지 먼저 생각하고 쿼리문을 작성하면 조금더 이해하기 쉬움.

최대공약수를 구하는 알고리즘

처음에는 최대공약수를 아래와 같이 입력받은 숫자를 1부터 입력받은 숫자까지 for문으로 순회하여 약수를 구하고 공통된 약수만 추려낸 다음 약수중 가장 큰값을 최대공약수로 사용하려고 하였지만..
시간복잡도에서 발목이 잡혀 문제가 풀리지 않았다.

최초로 시도해본 로직

//약수를 구하는 함수
function divisor(number){
    let arr = []
    for(let i =1 ; i<=number ; i++){
      if(number % i === 0){
        arr.push(i)
      }
    }
    return arr
  }

//약수가 담긴 두 배열에서 공통된 약수만 추려내는 함수.
function sameDivisor(mArr,nArr){
 
    let result = mArr.filter((el)=>{
       if(nArr.includes(el)) return true
    })
    return result
  }  

그러다가.. 유클리드호제법으로 아래와 같이 최대 공약수를 구하는 방법에 대해서 알게 되었고 아래와 같은 로직을 사용하여, 시간복잡도를 최소화 하여 최대공약수를 구할 수 있었다.

  function gcd(num1, num2){
   if(num1 % num2 === 0) return num2

    return gcd(num2,num1 % num2)
 
}

약수를 구하는 알고리즘

최대공약수를 구한다음, 최대 공약수의 약수를 구하는 알고리즘 또한..
처음에는 for문을 1부터 최대공약수까지 순회하여 구하려고 하였으나.. 이또한 역시 시간복잡도의 영향으로 인해.. 실패하였다..

그 다음 방법으로 구현하게 된것은 Math.sqrt()라는 메소드를 사용하여 제곱근을 이용하여 최대공약수의 약수를 구하는 방법을 사용하였다.

여기서 가장 어려웠던것은.. 제곱근을 이용할경우 제곱근보다 큰 약수를 어떻게 배열에 추가하는지를 엄청나게 고민했다..

결과적으로는 unshift와 push를 사용하여 해결이 가능하였다.
unshift: 제곱근보다 작은경우
push : 제곱근보다 큰경우

또한 for문을 1부터가 아닌 제곱근부터 시작하여 -1씩 해가며 약수를 구하는 것을 생각해 내는것도 어려웠다..

let bigGcd = 10
let divisor = []
 let sqrt = parseInt(Math.sqrt(bigGcd))
 for(let i = sqrt ; i>=1 ; i--){ // 4  1 2 4 
   if(bigGcd % i === 0){
      if(bigGcd / i === sqrt) {
        divisor.push(i)
      }else{
        divisor.unshift(i)
        divisor.push(bigGcd / i)
      }
       
   }
 }