일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 |
- state
- 자바스크립트
- 백준
- 알고리즘
- 브루트포스
- 병합 정렬
- node.js
- 정규표현식
- JavaScript
- 딥다이브
- 코테
- useState
- 자료구조
- 리액트
- 최소공배수
- hash
- 연결리스트
- 프로그래머스
- 정렬
- sort
- react
- 해시
- 완전탐색
- 합병 정렬
- 기술면접
- 코딩테스트
- Node
- JS
- BOJ
- CSS
- Today
- Total
가치투자자
[BOJ] 2609번 : 최대공약수와 최소공배수 본문
백준 2609번 : 최대공약수와 최소공배수
🔗 문제 링크
https://www.acmicpc.net/problem/2609
2609번: 최대공약수와 최소공배수
첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.
www.acmicpc.net
💬 문제
최대공약수 와 최소공배수 에 대한 이해가 있다면, 충분히 풀 수 있는 문제다.
- 첫 번째 줄에 공백을 기준으로 두 개의 자연수(a, b)가 주어진다.
- 두 수의 최대 공약수와 최소 공배수를 구해 출력해준다.
- a의 약수면서 b의 약수인 수 중에서 가장 큰 수가 최대공약수 다
- a의 배수면서 b의 배수인 수 중에서 가장 작은 수가 최소공배수 다
💡 입력값 받아오기
JavaScript로 풀 경우, 입력값(input)을 어떻게 받아와야 할 지가 중요하다.
이 문제에서는 1번째 줄에 자연수 a와 b가 주어진다. 공백을 기준으로 두 수를 잘라주고 정수화해준다.
입력값을 받아오는 것과 관련해 더 자세한 내용은 아래 링크를 참고 바란다.
https://valueengine.tistory.com/2
[BOJ] Node.js로 백준(BOJ) 푸는 법 및 VSCode 환경 세팅
1. Node.js fs모듈 사용법 백준에서 JavaScript로 문제를 풀기 위해선 Node.js를 사용해야 하며, 이때 readline 모듈이나 fs 모듈로 입력값(input)을 받아와야 한다. 이 중 속도나 코드의 길이, 작성 편리성에
valueengine.tistory.com
💻 풀이
이 문제는 총 2가지 방식으로 풀 수 있다.
🔑 풀이1 : for문으로 구하기
- 두 자연수가 주어졌을 때, a < b 순으로 정렬해주고 시작한다.
- 2부터 a까지의 수로 a와 b를 나눠 최대 공약수를 찾아준다.
- 1은 모든 수의 공약수이므로, 변수 divisor에 1을 할당해주고 2부터 나눠준다 - 최소 공배수
1) a가 최대 공약수라면 b는 a의 배수다
2) 그렇지 않다면, a와 b를 최대 공약수로 나눠 최소 공배수를 구해준다
// input값 처리
const input = require('fs').readFileSync('/dev/stdin')
.toString().trim().split(' ').map(Number);
[a, b] = input.sort((a, b) => a - b); // a < b
console.log(solution(a, b));
function solution(a, b) {
let divisor = 1; // 약수
let multiple; // 배수
// 최대 공약수
for (let i=2; i <= a; i++) {
if (a % i === 0 && b % i === 0) {
divisor = i;
}
}
// 최소 공배수
if (a === divisor) { // a가 최대 공약수라면
multiple = (b / divisor) * divisor;
} else {
multiple = a * b / divisor;
}
return `${divisor}\n${multiple}`;
}
시간은 다음과 같이 걸렸다.
🔑 풀이2 : 유클리드 호제법
두 번째 방법은 최대공약수를 구하는 알고리즘인 유클리드 호제법을 이용하는 것이다.
더 자세한 내용은 아래 링크를 참고하길 바란다.
https://valueengine.tistory.com/30
[알고리즘] 유클리드 호제법
유클리드 호제법 (유클리드 알고리즘, Euclidean algorithm) 1. 유클리드 호제법이란? 유클리드 호제법 은 두 수 A와 B의 최대공약수를 구하는 알고리즘이다. 여기서 호제법 이란 두 수가 서로 상대방을
valueengine.tistory.com
- a를 b로 나눠야 하니 a > b 순으로 정렬해주고 시작한다.
- x를 y로 나눠주고, 나머지가 0이 될 때까지 while문을 돌려준다.
- 재할당해주면서 값이 바뀌므로 x, y로 해준다 - 만약 나머지가 0이 아니라면, x를 y로 바꿔주고, y는 새로운 나머지로 바꿔준다
- 나머지가 0이 되면 그때의 y가 최대공약수다
- 최소 공배수는 두 수의 곱을 최대공약수 y로 나눈 값이다
// input값 처리
const input = require('fs').readFileSync('/dev/stdin').toString().trim().split(' ').map(Number);
[a, b] = input.sort((a, b) => b - a); // a > b
console.log(solution(a, b));
function solution(x, y) {
while (x % y !== 0) {
let rest = x % y // 나머지
if (rest !== 0) { // 나머지가 0일때 그 나머지 출력
x = y; // 나머지를 나눈수에 재할당
y = rest; // 나머지에 새 나머지 할당
}
}
return `${y}\n${(a * b / y)}`;
}
시간은 다음과 같이 걸렸다.
'Problem Solving > BOJ' 카테고리의 다른 글
[BOJ] 1120번 : 문자열 (브루트포스) (1) | 2023.04.15 |
---|---|
[BOJ] 1934번 : 최소공배수 (0) | 2023.04.15 |
[BOJ] 5086번 : 배수와 약수 (0) | 2023.04.08 |
[BOJ] 9506번 : 약수들의 합 (0) | 2023.04.06 |
[BOJ] 2501번 : 약수 구하기 (0) | 2023.04.06 |