코딩 정복 가즈아~
Home
  • 분류 전체보기 (159)
    • 알고리즘 풀이 (149)
      • 프로그래머스 (89)
      • 백준 (59)
    • 취준 일기 (6)
    • 네트워크 정리 (1)
Home
  • 분류 전체보기 (159)
    • 알고리즘 풀이 (149)
      • 프로그래머스 (89)
      • 백준 (59)
    • 취준 일기 (6)
    • 네트워크 정리 (1)
블로그 내 검색

코딩 정복 가즈아~

(っ◔◡◔)っ ♥ 2021 취뽀하자!! ♥

  • 알고리즘 풀이/프로그래머스

    [level1] 프로그래머스 - 최대공약수와 최소공배수(JAVA)

    2021. 8. 31.

    by. 데롱디롱

    728x90

    - 최대공약수 gcd(a, b) 구하기    => 유클리드 호제법을 이용

    임의의 두 자연수 a, b(a > b)가 주어지고
    a를 b로 나눈 나머지를 r(r = a % b)로 이라고 하자.

    a = b가되고 b = r이 되는데, 이때 b가 0이 될 때의 a가 최대공약수이다.

     

    - 최소 공배수

    최소 공배수 * 최대 공약수 = a * b 임을 이용
    따라서 최소 공배수 = a * b / 최대 공약수

     

     

    class Solution {
        public int[] solution(int n, int m) {
            // 최대 공약수
            int a = Math.max(n, m);
            int b = Math.min(n, m);
            while (b != 0) {
                int r = a % b;
                a = b;
                b = r;
            }
    
            // 최대 공배수 = 두 수의 곱 / 최대공약수
            return new int[] { a, n * m / a };
        }
    }

     

    저작자표시 (새창열림)

    '알고리즘 풀이 > 프로그래머스' 카테고리의 다른 글

    [level1] 프로그래머스 - 평균 구하기(JAVA)  (0) 2021.08.31
    [level1] 프로그래머스 - 콜라츠 추측(JAVA)  (0) 2021.08.31
    [level1] 프로그래머스 - 짝수와 홀수(JAVA)  (0) 2021.08.31
    [level1] 프로그래머스 - 제일 작은 수 제거하기(JAVA)  (0) 2021.08.31
    [level1] 프로그래머스 - 정수 제곱근 판별(JAVA)  (0) 2021.08.31

    댓글

    관련글

    • [level1] 프로그래머스 - 평균 구하기(JAVA) 2021.08.31
    • [level1] 프로그래머스 - 콜라츠 추측(JAVA) 2021.08.31
    • [level1] 프로그래머스 - 짝수와 홀수(JAVA) 2021.08.31
    • [level1] 프로그래머스 - 제일 작은 수 제거하기(JAVA) 2021.08.31
    맨 위로
전체 글 보기
Tistory 로그인
Tistory 로그아웃
로그아웃 글쓰기 관리

Today

Total

피할 수 없다면, 순간을 즐겨라

Designed by Nana
블로그 이미지
데롱디롱
희희.. (๑′ᴗ‵๑)

티스토리툴바