[99club/TIL] 6주차 - 월요일 TIL(Today I Learned)

안녕하세요. delay100 입니다!

---

미들러 문제

---

1번. N개의 최소공배수

https://school.programmers.co.kr/learn/courses/30/lessons/12953

프로그래머스

이 문제는 유클리드 호제법을 사용하면 됩니다.

그러나 필자는 유클리드 호제법에 대해 말만 들어봤지 실제로는 잘 몰랐습니다.

그래서 유클리드 호제법을 먼저 검색해보았고, 최대 공약수(+ 최소공배수)를 구해야하는 문제에서 쓰는 방식인 것을 알게 되었습니다.

유클리드 호제법은 최대 공약수를 구할때 쓰는데, 이렇게 구한 최대 공약수로 최소공배수까지 구할 수 있습니다.

최대 공약수(gcd)를 구한 후에 최소 공배수(lcm)를 구해줍니다.

 

먼저, 최대공약수를 구해줍니다.

최대공약수 = 2개의 숫자(a, b)를 나눴을 때 0이 되는 숫자

만약, 2개의 숫자를 나눴을 때 0이 되지 않는다면 나눈수(b)와 2개의 숫자를 나눈 값의 "나머지"를 가지고 또 한번 계산해줍니다. 나머지가 0이 될 때까지 계속 반복해주고, 나머지가 0이될 때 몫을 반환해줍니다.

 

다음으로 최소공배수를 구해줍니다.

최소공배수 = 2개의 숫자(a, b)를 곱하고 최대공약수로 나눈 숫자

 

그리고 다음 arr[i]에 가기 전에 a값을 최소공배수로 바꿔줍니다. 그럼 계속해서 현재까지의 최소공배수가 만들어집니다.

class Solution {
    public int solution(int[] arr) {
        int a = arr[0];
        int lcm = arr[0];
        
        for(int i=1; i<arr.length; i++) {
            lcm = a*arr[i]/gcd(a, arr[i]);
            a = lcm;
        }
        
        return lcm;
    }

    // 최대 공약수 구하기 -> 유클리드 호제법
    public static int gcd(int a, int b) {
        if(a % b == 0) {
            return b;
        }
        return gcd(b, a%b);
    }
}

[유클리드 호제법 알기]

 

https://hstory0208.tistory.com/91

[알고리즘] 유클리드 호제법 - 최소공배수, 최대공약수 구하기

 

[현재 문제에 대한 참고 설명 본 블로그]

https://hstory0208.tistory.com/entry/Java%EC%9E%90%EB%B0%94-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-Lv2-N%EA%B0%9C%EC%9D%98-%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98-%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C-%ED%98%B8%EC%9E%AC%EB%B2%95

[Java/자바] 프로그래머스 Lv2 - N개의 최소공배수 (유클리드 호재법)

 

---

2번. 연속 부분 수열 합의 개수

https://school.programmers.co.kr/learn/courses/30/lessons/131701

프로그래머스

이 문제는 내일(화요일) TIL에 작성해보겠습니다. 

---

+ 비기너 문제

1번.

https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

2번.

https://school.programmers.co.kr/learn/courses/30/lessons/68935

프로그래머스

+ 챌린저 문제

1번.

https://school.programmers.co.kr/learn/courses/30/lessons/12946

프로그래머스

2번.

https://school.programmers.co.kr/learn/courses/30/lessons/150368

프로그래머스

---

봐주셔서 감사합니다. 피드백 환영합니다.