<div id="readability-page-1" class="page">
                
                
                


<div id="wrap">
	
	<hr>
	<section>
		
		<article id="content">
			

			

			

			

			<div>
				

				            
                
	
	
		<div>
			<p>운동하는 개발자/알고리즘, 코딩테스트</p>
			
			<p>
				<span>2023. 12. 28. 22:20</span>
				
			</p>
		</div>
		<div><hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style5">
<h3 data-ke-size="size23"><br>🅰️문제주소 :<span> <a href="https://www.acmicpc.net/problem/1934" target="_blank" rel="noopener&nbsp;noreferrer">https://www.acmicpc.net/problem/1934</a></span></h3>

<h3 data-ke-size="size23"><br>🚩문제&nbsp;</h3>
<figure data-ke-mobilestyle="widthOrigin" data-origin-width="994" data-origin-height="195"><span data-url="https://blog.kakaocdn.net/dn/ttbOx/btsCMzLbAUd/IzAZlk7l9iRiqkFHgp4vvK/img.png" data-lightbox="lightbox"><img src="https://blog.kakaocdn.net/dn/ttbOx/btsCMzLbAUd/IzAZlk7l9iRiqkFHgp4vvK/img.png" onerror="this.onerror=null; this.src='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png'; this.srcset='//t1.daumcdn.net/tistory_admin/static/images/no-image-v1.png';" data-origin-width="994" data-origin-height="195"></span></figure>



<h3 data-ke-size="size23">🪡풀이&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- 우선 유클리드 호제법으로 최대공약수를 구해야한다&nbsp;<br>&nbsp;- 최소공배수 = 'A*B / 최대공약수'&nbsp; 공식에 대입한다 끝</p>

<h3 data-ke-size="size23">☕코드는 아래 숨김</h3>
<div data-text-less="닫기" data-text-more="더보기" data-ke-type="moreLess"><p><a>더보기</a></p><div>
<pre id="code_1701091944942" data-ke-language="cpp" data-ke-type="codeblock"><code>#include &lt;iostream&gt;

int main()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(0);
	std::cin.tie(0);
	int T, A, B;

	std::cin &gt;&gt; T;

	for (int i = 0; i &lt; T; ++i) {
		std::cin &gt;&gt; A &gt;&gt; B;

		int big, small;
		if (A &lt;= B) {		//A가 B보다 작다는 표현이 명확하지 않아서 조건넣음
			big = B;
			small = A;
		}
		else {
			big = A;
			small = B;
		}

		while (small != 0) { //재귀 함수로 더 깔끔하게 구현가능
			int temp_mod = big % small;
			big = small;
			small = temp_mod;
		}
		std::cout &lt;&lt; A * B / big &lt;&lt; "\n";
	}
	return 0;
}</code></pre>
</div>
</div>

<h3 data-ke-size="size23">💡알게 된 것&nbsp;</h3>
<p data-ke-size="size18">&nbsp;- 유클리드 호제법 <br>&nbsp; &nbsp;1) A와 B의 최대공약수를 구하려면 큰수/작은수의 나머지값을 구한다<br>&nbsp; &nbsp;2) '기존 작은수'가 '다음번 큰수'가 되고 '구했던 나머지 값'이 '다음번 작은수'가 된다.<br>&nbsp; &nbsp;3) 나머지가 0이될때까지 반복해서 나머지가 0일때 '작은수' 값이 최대 공약수이다</p>
<p data-ke-size="size18">- 최소 공배수는 'A*B/최대 공약수'</p>
<hr contenteditable="false" data-ke-type="horizontalRule" data-ke-style="style5">
</div>
		

		
			<div>
				<h2><strong>'운동하는 개발자/알고리즘, 코딩테스트'</strong> Related Articles</h2>
				
			</div>
		

		



	

                
            
			</div>

			

			

			

		</article>
	</section>
	<hr>
	
	
</div>







                




        
        











  


        

                
                







                
                


                

</div>

운동하는 개발자

️문제주소 : https://www.acmicpc.net/problem/1934
 
 문제 
 
 
 풀이 
 - 우선 유클리드 호제법으로 최대공약수를 구해야한다 
 - 최소공배수 = 'A*B / 최대공약수'  공식에 대입한다 끝
 
☕코드는 아래 숨김
더보기
#include <iostream>
int main()
{
	std::ios::sync_with_stdio(false);
	std::cout.tie(0);
	std::cin.tie(0);
	int T, A, B;
	std::cin >> T;
	for (int i = 0; i < T; ++i) {
		std::cin >> A >> B;
		int big, small;
		if (A <= B) {		//A가 B보다 작다는 표현이 명확하지 않아서 조건넣음
			big = B;
			small = A;
		}
		else {
			big = A;
			small = B;
		}
		while (small != 0) { //재귀 함수로 더 깔끔하게 구현가능
			int temp_mod = big % small;
			big = small;
			small = temp_mod;
		}
		std::cout << A * B / big << "\n";
	}
	return 0;
}
 
 알게 된 것 
 - 유클리드 호제법 
   1) A와 B의 최대공약수를 구하려면 큰수/작은수의 나머지값을 구한다
   2) '기존 작은수'가 '다음번 큰수'가 되고 '구했던 나머지 값'이 '다음번 작은수'가 된다.
   3) 나머지가 0이될때까지 반복해서 나머지가 0일때 '작은수' 값이 최대 공약수이다
- 최소 공배수는 'A*B/최대 공약수'

Beakjoon] 최소공배수 (백준 1934코테) - 정수론 (C++)

댓글