리액트 심화 프로젝트 (6)

신나는 알고리즘 풀이 시간 

문제 설명

두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.

제한 사항

• arr은 길이 1이상, 15이하인 배열입니다.
• arr의 원소는 100 이하인 자연수입니다.

문제 접근

1. 두 수의 최소공배수를 구하는 공식

최소공배수(LCM)를 구하려면, 두 수의 **최대공약수(GCD)**를 이용할 수 있다:
LCM(a,b)=a×bGCD(a,b)\text{LCM}(a, b) = \frac{a \times b}{\text{GCD}(a, b)}LCM(a,b)=GCD(a,b)a×b​

2. n개의 수에 적용

• 배열에서 첫 두 수의 최소공배수를 계산.
• 구한 최소공배수를 배열에 다시 추가.
• 배열이 하나의 숫자만 남을 때까지 반복.

유틸 함수

function gcd(a, b) {
  while (b != 0) {
    let r = a % b;
    a = b;
    b = r;
  }
  return a;
}

function lcm(a, b) {
  return (a * b) / gcd(a, b);
}

 

 

• gcd(a, b): 유클리드 호제법을 사용해 두 수의 최대공약수를 계산.
• lcm(a, b): 두 수의 최소공배수를 반환.

정답 코드

function solution(arr) {
  // 배열의 최소공배수 계산
  while (arr.length > 1) {
    const first = arr.shift(); // 배열의 첫 번째 요소 제거
    const second = arr.shift(); // 배열의 두 번째 요소 제거
    const LCM = lcm(first, second); // 최소공배수 계산
    arr.unshift(LCM); // 최소공배수를 배열의 첫 번째에 추가
  }
  return arr[0]; // 배열에 남은 유일한 요소 반환
}

// 테스트 실행
console.log(solution([2, 6, 8, 14])); // 출력: 168

 

 

풀이 과정

1. 초기 값:
   배열: [2, 6, 8, 14].
2. 첫 번째 루프:
   • first = 2, second = 6
   • lcm(2, 6) = (2 × 6) / gcd(2, 6) = 12
   • 배열: [12, 8, 14].
3. 두 번째 루프:
   • first = 12, second = 8
   • lcm(12, 8) = (12 × 8) / gcd(12, 8) = 24
   • 배열: [24, 14].
4. 세 번째 루프:
   • first = 24, second = 14
   • lcm(24, 14) = (24 × 14) / gcd(24, 14) = 168
   • 배열: [168].
5. 결과 반환:
   • 배열에 남은 유일한 값 168이 최소공배수.

배운 점

1. 유클리드 호제법

• 최대공약수를 구할 때 효율적으로 사용할 수 있는 수학적 방법.

2. 반복적 접근

• n개의 숫자에 대한 최소공배수를 구할 때, 두 수씩 계산하여 배열을 축소하는 방식이 유용.

3. 배열 메서드 활용

• shift와 unshift를 사용해 배열을 동적으로 수정하며 계산을 진행.

원래 두 수의 최소공배수를 구하는 법은 알고 있으나, n개의 수의 최소공배수를 마주쳤을 때 조금 벙쪘던 면이 있었다.

 

하지만 따지고 보면 간단한데, n개의 최소공배수를 구하려면, 배열 안에서 두 개의 숫자를 뽑아 그것의 최소공배수를 구한 다음, 배열에서 두 수를 제거. 그 다음 그 최소공배수를 배열에 더해주는 식으로 계속해서 최소공배수를 구해나가면, n개의 숫자에 대한 최소공배수를 구할 수 있다. 

 

그래서 먼저, 유틸 함수로 따로 gcd와 lcm을 구하는 로직을 밖에 빼놓은 다음, solution 안에서는 첫 번째 숫자와 두 번째 숫자를 mutable 메소드인 shift를 통해서 배열에서 제거함과 동시에, 변수에 해당하는 값을 담았다. 

 

그렇게 해서 배열에서 두 수를 추출하고, 최소 공배수를 구한 다음, 그렇게 구한 공배수를 unshift를 이용해 배열의 첫 번쨰에 다시 넣어주고, while 문을 이용해 arr의 길이가 1이 될 때까지 반복. 정답으로 arr의 0번째 요소를 반환함으로서 답을 구할 수 있었다.