본문 바로가기

전체 글196

[C#] 4134번: 다음 소수 목차백준 단계별로 풀어보기25.11.0915단계: 약수, 배수와 소수 24134번: 다음 소수문제 링크 : https://www.acmicpc.net/problem/4134 문제를 풀기 위해 알아야 할 개념>> 합성수의 특성: 합성수 N에 대하여 N = a × b 라고 하면, a와 b 둘 중 하나는 √N 보다 작거나 같다.--> 이를 활용하면 N이 소수인지 확인할 때, 1부터 √N까지만 반복하여 N을 나눈 나머지가 0이 아니라면 N이 소수임을 알 수 있다. - 증명: 만약 a와 b 둘다 √N 보다 크다면? 'a × b > √N × √N = N' 이 성립되어야 한다. 하지만 a × b = N 이기 때문에 a × b > N 라는 건 성립할 수 없다. 따라서 a와 b 둘 중 하나는 √N 보다 작거나 같다.ex.. 2025. 11. 9.
[C#] 2485번: 가로수 목차백준 단계별로 풀어보기25.11.0815단계: 약수, 배수와 소수 22485번: 가로수문제 링크 : https://www.acmicpc.net/problem/2485 문제를 풀기 위해 알아야 할 개념>> 유클리드 호제법 (Euclidean Algorithm): 아래 글에 정리해두었다. 두 자연" data-og-host="mobics.tistory.com" data-og-source-url="https://mobics.tistory.com/209" data-og-url="https://mobics.tistory.com/209" data-og-image="https://blog.kakaocdn.net/dna/989Jl/hyZMyQoKXI/AAAAAAAAAAAAAAAAAAAAABmQTvMcIzEjkjpnSFXW8Mrvrs4qT2ycadpiNv3iFbOO/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&expires=1764514799&allow_ip=&allow_referer=&signature=8fbK2JIPew%2B1pGmPZINzdgtCJbs%3D 2025. 11. 8.
[C#] 1735번: 분수 합 목차백준 단계별로 풀어보기25.11.0715단계: 약수, 배수와 소수 21735번: 분수 합문제 링크 : https://www.acmicpc.net/problem/1735 문제를 풀기 위해 알아야 할 개념>> 유클리드 호제법 (Euclidean Algorithm): 아래 글에 정리해두었다. 두 자연" data-og-host="mobics.tistory.com" data-og-source-url="https://mobics.tistory.com/209" data-og-url="https://mobics.tistory.com/209" data-og-image="https://blog.kakaocdn.net/dna/ciZ1fo/hyZMB0sWKl/AAAAAAAAAAAAAAAAAAAAADZG5swo61Kn1Gz_KMEgJRkSydxeK_cVoHUiligx4osL/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&expires=1764514799&allow_ip=&allow_referer=&signature=GFUKozptXuc7zfAkzLGjqyZttnQ%3D 2025. 11. 7.
유클리드 호제법을 활용하여 최대공약수, 최소공배수 구하기 목차유클리드 호제법 (Euclidean Algorithm): 두 자연수의 최대공약수를 구하는 알고리즘. 이때 호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 뜻한다.--> 두 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a > b) a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. - 반복문을 활용한 코드 (C#)// a > bint GCD(int a, int b){ while (b != 0) { int temp = a % b; a = b.. 2025. 11. 6.
[C#] 13241번: 최소공배수 목차백준 단계별로 풀어보기25.11.0615단계: 약수, 배수와 소수 213241번: 최소공배수문제 링크 : https://www.acmicpc.net/problem/13241 문제를 풀기 위해 알아야 할 개념>> 유클리드 호제법: 아래 링크에 정리해두었다. 두 자연" data-og-host="mobics.tistory.com" data-og-source-url="https://mobics.tistory.com/209" data-og-url="https://mobics.tistory.com/209" data-og-image="https://blog.kakaocdn.net/dna/5hYQo/hyZM1rao6G/AAAAAAAAAAAAAAAAAAAAAJNewD7iKG4VwhiQ5Yf2dCXU4rxcoX253rWsrkzogO-1/img.png?credential=yqXZFxpELC7KVnFOS48ylbz2pIh7yKj8&expires=1764514799&allow_ip=&allow_referer=&signature=4Re5Xnpu0lHM%2Bvcj%2FTYV54QqbEg%3D 2025. 11. 6.
[C#] 1934번: 최소공배수 목차백준 단계별로 풀어보기25.11.0515단계: 약수, 배수와 소수 21934번: 최소공배수문제 링크 : https://www.acmicpc.net/problem/1934 문제를 풀기 위해 알아야 할 개념>> 유클리드 호제법 (Euclidean Algorithm): 두 자연수의 최대공약수를 구하는 알고리즘. 이때 호제법이란 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 뜻한다.--> 두 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a > b) a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라 b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대.. 2025. 11. 5.

티스토리툴바