[BOJ알고리즘, C++]#2609_최대 공약수와 최소 공배수, 유클리드 호제법

2022. 9. 4. 14:44· 문제 풀이/BOJ 문제 풀이
목차
  1. [BOJ 알고리즘, C++] #2609_최대 공약수와 최소 공배수, 유클리드 호제법

[BOJ 알고리즘, C++] #2609_최대 공약수와 최소 공배수, 유클리드 호제법

 

BOJ 알고리즘 문제 풀이, 2609_최대 공약수와 최소 공배수

유클리드 호제법 알고리즘을 통해 두 자연수의 최대 공약수와 최소 공배수를 구하는 문제

 

 


 

문제

 

풀이

 

1. 유클리드 호제법

A = 106, B = 16

1.

C = A % B = 106 % 16 = 10

A <- B, A가 16이 된다.

B <- C, B가 10이 된다.

2.

C = A % B = 16 % 10 = 6

A <- B, A가 10이 된다.

B <- C, B가 6이 된다.

3.

C = A % B = 10 % 6 = 4

A <- B, A가 6이 된다.

B <- C, B가 4가 된다.

4.

C = A % B = 6 % 4 = 2

A <- B, A가 4이 된다.

B <- C, B가 2가 된다.

5.

C = A % B = 4 % 2 = 0

끝, 106과 16의 GCD는 'B'값, 즉 2가 된다.
유클리드 호제법은 2개의 자연수의 최대공약수를 구하는 알고리즘의 하나입니다.
A와 B를 나눈 나머지 값을 R이라고 한다면, A와 B의 최대 공약수는 B와 R의 최대 공약수와 같습니다!
이 성질을 이용하여, B(혹은 Determinant)를 이전의 나머지 값으로 나누는 작업을 반복합니다.
최종적으로, 나머지 값이 0이 되었을 때, "마지막 B" 값이 A와 B의 최대 공약수가 되는 것입니다.

 

2. 최소공배수 공식

A와 B의 최소 공배수 = (A * B) / gcd(A, B)

 

결과 코드
#include <iostream>
using namespace std;

int N, M;

/* 1. 최대 공약수 : 유클리드 호제법
    a % b = c
    b % c = d
    d % c = e
    .
    .
    .
    q % r = 0
    gcd = r !
*/
int gcd(int a, int b)
{
    int c = a % b;
    while(c != 0)
    {
        a = b;
        b = c;
        c = a % b;
    }
    return b;
}

// 2. 최소 공배수 : a * b / (a와 b의 최대공약수)
int lcm(int a, int b)
{
    return (a * b)/ gcd(a, b);
}

int main()
{
    // 수행 시간 감소를 위한 라인
    ios_base::sync_with_stdio(false); cout.tie(NULL); cin.tie(NULL);

    cin >> N >> M;

    cout << gcd(N, M) << '\n' << lcm(N, M) << endl;

}

 

 

 

'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글

[BOJ알고리즘, C++]#25305_커트 라인, 정렬 알고리즘, STL, 내림차순  (0) 2022.09.04
[BOJ알고리즘, C++]#11050_이항 계수 1, 이항 계수 공식, 재귀문 활용  (0) 2022.09.04
[BOJ알고리즘, C++]#11660_구간 합 구하기 5  (0) 2022.08.14
[BOJ알고리즘, C++]#2559_수열의 최대 구간 합, 누적 합 알고리즘  (0) 2022.07.12
[BOJ알고리즘, C++]#11659_구간 합 구하기, Prefix Sum(누적 합) 알고리즘  (0) 2022.06.29
  1. [BOJ 알고리즘, C++] #2609_최대 공약수와 최소 공배수, 유클리드 호제법
'문제 풀이/BOJ 문제 풀이' 카테고리의 다른 글
  • [BOJ알고리즘, C++]#25305_커트 라인, 정렬 알고리즘, STL, 내림차순
  • [BOJ알고리즘, C++]#11050_이항 계수 1, 이항 계수 공식, 재귀문 활용
  • [BOJ알고리즘, C++]#11660_구간 합 구하기 5
  • [BOJ알고리즘, C++]#2559_수열의 최대 구간 합, 누적 합 알고리즘
Hardii2
Hardii2
Hardii2
개발 블로그
Hardii2
전체
오늘
어제
  • 분류 전체보기
    • 알고리즘
    • 웹 개발
      • Node.js
      • React
    • 게임개발
      • DirectX12
      • 관련 지식
      • Unreal C++
      • Unreal 블루프린트
    • 언어
      • Effective C++
      • Basic C++
      • 디자인 패턴
      • 자료구조
      • 기술 질문
    • 문제 풀이
      • BOJ 문제 풀이
      • Programmers 문제 풀이
      • geeksForgeeks 문제 풀이
    • 수학
      • 확률과 통계
      • 게임수학
    • 개인프로젝트
    • 그룹프로젝트
      • PM
      • Dev
    • Github

블로그 메뉴

  • 홈
  • 글쓰기

공지사항

인기 글

태그

  • Effective C++
  • dfs
  • 정렬
  • BOJ
  • unreal
  • 그래프
  • 디자인 패턴
  • 개발
  • DP
  • programmers
  • 최단 경로
  • 트리
  • C++
  • Unreal Blueprint
  • 우선순위 큐
  • stl
  • 기술 질문
  • 알고리즘
  • set
  • BFS

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
Hardii2
[BOJ알고리즘, C++]#2609_최대 공약수와 최소 공배수, 유클리드 호제법
상단으로

티스토리툴바

개인정보

  • 티스토리 홈
  • 포럼
  • 로그인

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.