평범한 연구소

N은 두 소수의 합이다. 이 N을 골드바흐 파티션이라고 한다. 골드바흐 파티션의 개수를 구하는 문제이다. 정수 N의 범위가 커서 일반적인 소수 구하는 로직으로 짜면.. 안된다. 소수를 구하는 알고리즘인 에라토스테네스의 체 를 사용해야한다. 관련 개념을 읽어보자. 2022.12.17 - [JAVA/알고리즘 공부] - [JAVA] 에라토스테네스의 체 (소수 판별 알고리즘) 1. 에라토스테네스의 체 알고리즘으로 1~1,000,000 까지 수 중 소수를 판별한다. 2. 테스트 케이스마다 골드바흐 파티션 개수를 출력한다. package boj; import java.io.BufferedReader; import java.io.InputStreamReader; public class Ex17103 { public ..

매 선택에서 지금 이 순간 당장의 최적인 선택을 하여 적합한 결과를 도출하는 알고리즘 기법이다. 기본적으로 무조건 큰 경우, 무조건 작은 경우, 무조건 짧은 경우 등 극단적으로 문제에 접근하므로 정렬(Sort)이 함께 이용되는 경우가 많다. 특수한 조건 2가지를 만족해야 사용할 수 있다. 1) 탐욕 선택 속성 (Greedy Choice Property) 이전의 선택이 이후에 영향을 주지 않는다. 2) 최적 부분 구조 (Optimal Substructure) 부분 문제의 최적 결과가 전체에도 그대로 적용될 수 있어야한다. 그리디 알고리즘을 활용한 백준 문제를 풀어보자. 2022.11.27 - [JAVA/알고리즘 공부] - [백준 JAVA] 2839번: 설탕 배달

더 적은 갯수의 봉지를 배달해야한다. 그리디 알고리즘을 사용하여 풀어보자. package boj; import java.io.BufferedReader; import java.io.InputStreamReader; public class Ex2839 { public static void main(String[] args) { try { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int sugar = Integer.parseInt(br.readLine()); int cnt = 0; while (true) { if (sugar % 5 == 0) { cnt += sugar / 5; sugar %= 5; break; } e..

라고 답변하였지 출력에 대해 이리저리 고민해보았다. 이 부분만 StringBuilder의 setLength()를 이용하여 4개씩 빼서 출력하는 방법으로 작성했다. package boj; import java.io.BufferedReader; import java.io.InputStreamReader; public class Ex17478 { static StringBuilder underbar = new StringBuilder(""); public static void main(String[] args) { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); try { int cnt = Integer.parseInt(br...

주어진 nums 배열에서 두 인덱스 값의 합이 target인 인덱스 2개를 찾으면 된다. 풀이 방법은 2가지. 2중for문을 사용하면 간단하지만 시간복잡도가 높다는 단점이 있다. HashMap을 사용하여 9(target)=2+7 → 9(target)-2=7 원리로 찾는 방법 package leetcode; import java.util.Arrays; import java.util.HashMap; public class TwoSum { public int[] twoSum(int[] nums, int target) { /* for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[i] + nums[j..

public static int[] twoSum(int[] nums, int target) { int[] result = null; Map map = new HashMap(); for(int i=0; i