본문 바로가기

분류 전체보기

 (90)
[백준 JAVA] 2824. 최대공약수 문제 링크https://www.acmicpc.net/problem/2824접근 방법큰 수 연산을 해야 하므로 BigInteger를 사용합니다. 소스 코드import java.util.*;import java.io.*;import java.math.BigInteger;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); br.readLine(); BigInteger a = Arrays.stream(br.readLine().split(" ")) .map(BigInteger:..
[백준 JAVA] 14232. 보석 도둑 문제 링크https://www.acmicpc.net/problem/14232접근 방법2부터 시작해서 효빈이가 들 수 있는 무게까지 반복문을 돌립니다. 소스 코드import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;public class Main { public static void main(String[] args) throws NumberFormatException, IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBui..
[백준 JAVA] 1456. 거의 소수 문제 링크https://www.acmicpc.net/problem/1456접근 방법에라토스테네스의 체를 이용하여 소수를 구합니다.b의 제곱근 보다 큰 소수는 제곱했을 때 b 보다 커지므로 b의 제곱근으로 for 문을 돌립니다.제곱할 때 오버플로우가 날 수 있기 때문에 Math.pow함수를 사용합니다.소스 코드import java.util.*;import java.io.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st..
[알고리즘] 오일러 피 오일러 피오일러의 피 함수는 𝜙(𝑁) 또는 P[N] 으로 표시되며, 자연수 N 이하의 양의 정수 중에서 N과 서로소인 수의 개수를 나타내는 함수입니다. 두 수가 서로소라는 것은 공약수가 1 뿐인 경우를 말합니다.  오일러 피 알고리즘'2' 부터 구하고자 하는 값의 제곱근까지의 소인수를 구합니다.결괏값을 갱신합니다.N값에서 소인수를 나눠줍니다.N이 1보다 크면 결괏값을 최종 조정합니다.오일러 피 구현int N; // 구하고자 하는 수int result = N;for (int k = 2; k 1) { // 소인수가 남아있을 때 result -= result / N;}오일러 피 시간복잡도오일러 피의 시간복잡도는 O(Φn logn)입니다. 여기서 Φn 은 서로소 개수 입니다. 증명은 생략하겠..
[프로그래머스 JAVA] 181832. 정수를 나선형으로 배치하기 문제 링크 프로그래머스코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.programmers.co.kr 접근 방법나선형으로 배열을 채우기 위해 오른쪽, 아래, 왼쪽, 위 4방향으로 순차적으로 채워야 합니다.따라서 각 방향마다 출발지점을 만들고 채워줍니다.소스 코드class Solution { public int[][] solution(int n) { int[][] answer = new int[n][n], a = {{0, 0}, {0, n - 1}, {n - 1, n - 1}, {n - 1, 0}}; int[] d = {0, 1, 2, 3}; boolean fl..
[알고리즘] 소수 구하기 소수소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수입니다. 예를 들어, 5는 1 ×5 또는 5 ×1로 수를 곱한 결과를 적는 유일한 방법이 그 수 자신을 포함하기 때문에 5는 소수입니다. 그러나 6은 자신보다 작은 두 숫자의 곱(2 ×3)이므로 소수가 아닌데, 이렇듯 1보다 큰 자연수 중 소수가 아닌 것은 합성수나 비소수라고 합니다. 에라토스테네스의 체소수를 구하는 대표적인 방법으로 에라토스테네스의 체가 있습니다.에라토스테네스의 체 알고리즘은 다음과 같습니다.구하고자 하는 소수의 범위만큼 1차원 배열을 생성합니다.'2'부터 시작해 특정 수의 배수에 해당하는 수를 모두 지웁니다. 이때 특정 수 자신은 지우지 않습니다.배열의 끝까지 2를 반복합니다. 에라토스테네스의 체 구현boolean[]..
[알고리즘] LCM LCM최소공배수(LCM, Least Common Multiple)는 두 개 이상의 정수의 공통 배수 중 가장 작은 수를 의미합니다.LCM을 구하는 방법에는 여러 방법이 있지만, 가장 흔히 알려진 방법은 GCD를 이용하는 방법입니다. GCD [알고리즘] GCD - 유클리드 호제법유클리드 호제법이란유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수(Greatest Common Divisor, GCD)를 구하는 알고리즘입니다. 호제법이란 말은 두 수가 서로 상대방tkxxls.tistory.com  LCM 알고리즘두 수 a와 b의 최소 공배수 lcm(a, b)는 다음과 같이 계산됩니다lcm(a, b) = a × b / gcd(a, b)​LCM 구현int gcd(int a, int b)..
[알고리즘] GCD - 유클리드 호제법 유클리드 호제법이란유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수(Greatest Common Divisor, GCD)를 구하는 알고리즘입니다. 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘이라는 뜻입니다. GCD 알고리즘 두 개의 정수 a와 b (단, a ≥ b)가 주어집니다.a를 b로 나눈 나머지를 구합니다. 즉, r = a mod  b.r이 0이라면, b가 a와 b의 최대 공약수이며, 알고리즘을 종료합니다.r이 0이 아니라면, a는 이전의 b가 되고, b는 이전의 r이 되어 위 과정을 반복합니다.GCD 구현int gcd(int a, int b) { if (b == 0) return a; retu..

티스토리툴바