분류 전체보기403 [백준] 1124번 : 언더프라임 – JAVA [자바] https://www.acmicpc.net/problem/1124 문제 해결 방법이 문제는 소수 판별 및 소인수분해를 활용한 수 카운팅 문제이다. 다음과 같은 방식으로 해결할 수 있다. 1. B까지의 소수를 구한다.- 에라토스테네스의 체를 이용하여 B 이하의 모든 소수를 구한다. 에라토스테네스의 체의 대한 자세한 정보는 여기서 확인할 수 있다. 2. 각 숫자의 소인수 개수를 구한다.- B 이하의 모든 수에 대해 소인수분해를 수행하여 소수 개수를 센다. 3. 소인수 개수가 소수인지 확인하여 카운트한다.- A부터 B까지의 숫자 중에서 소인수 개수가 소수인 경우를 센다. 이 방법을 사용하면 O(N log log N + N log N)의 시간 복잡도로 문제를 해결할 수 있다. 코드 import jav.. 2025. 3. 17. [백준] 1145번 : 적어도 대부분의 배수 – JAVA [자바] https://www.acmicpc.net/problem/1145 문제 해결 방법 이 문제는 최소 공배수(LCM, Least Common Multiple) 개념을 활용하여 해결할 수 있다. 다섯 개의 수 중에서 적어도 세 개로 나누어지는 가장 작은 자연수를 찾아야 하므로, 세 개의 숫자를 조합하여 최소 공배수를 구하고, 그중 최솟값을 선택하면 된다. 문제 해결 과정 1. 다섯 개의 자연수를 입력받는다. 2. 다섯 개 중 세 개를 선택하는 모든 조합을 찾는다. 3. 선택한 세 개의 수의 최소 공배수(LCM)를 구한다. 4. 모든 조합의 LCM 중에서 최솟값을 출력한다. 최대 공약수(GCD, Greatest Common Divisor)는 두 수의 공통된 약수 중 가장 큰 값을 의미하며, 유클리드 호제법을.. 2025. 3. 14. [백준] 12852번 : 1로 만들기 2 – JAVA [자바] https://www.acmicpc.net/problem/12852 문제 해결 방법 이 문제는 DP 방법을 이용하여 해결할 수 있다. 1. dp[i]를 i를 1로 만들기 위한 최소 연산 횟수 라고 정의한다. 2. 초기값을 설정한다: dp[1] = 0 (1은 연산 없이 1이므로 연산 횟수가 0) 3. dp[i] 값을 dp[i-1], dp[i/2], dp[i/3] 중 최소값 +1로 설정한다. 4. dp[n]을 통해 최소 연산 횟수를 구한 후, 역추적(backtracking)을 이용하여 경로를 출력한다. 코드 import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOEx.. 2025. 3. 14. [백준] 1439번 : 뒤집기 – JAVA [자바] https://www.acmicpc.net/problem/1439 문제 해결 방법 이 문제는 그리디 알고리즘(Greedy Algorithm)을 사용하여 해결할 수 있다. 1. 0과 1이 각각 몇 번 그룹으로 나뉘는지 계산한다. 예를 들어 0001100의 경우, 000 / 11 / 00으로 0 그룹 2개, 1 그룹 1개가 된다. 11001100110011000001의 경우, 11 / 00 / 11 / 00 / 11 / 00 / 11 / 00000 / 1로 0 그룹 4개, 1 그룹 4개가 된다. 2. 0과 1의 그룹 수 중 작은 값을 선택하면 최소 뒤집기 횟수가 된다. 예를 들어 0001100의 경우 0 그룹 2개, 1 그룹 1개이므로 최소 1번 뒤집으면 해결 가능하다. 110011001100110000.. 2025. 3. 13. 이전 1 2 3 4 5 6 7 ··· 101 다음 반응형
