알고리즘/수학
-
[백준 11050] - [수학] - 이항계수 1 (Java)알고리즘/수학 2018. 12. 14. 17:12
문제 링크 : https://www.acmicpc.net/problem/11050 이문제는 간단한 조합 문제이다. 입력받는 형식을 식으로 풀이하면 아래와 같이 나온다. 이 문제는 제일 간단한 문제이기때문에 그냥 각 수 별로 {n!, k!, (n-k)! } 팩토리얼 을 구한다음 계산하면 된다. 소스 1234567891011121314151617181920212223242526import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int K = sc.nextInt(); int a = getFactorial..
-
[백준 3036] - [수학 최대공약수] - 링 (JAVA)알고리즘/수학 2018. 12. 4. 11:14
문제 링크 : https://www.acmicpc.net/problem/3036 이문제는 높은 정답률을 자랑한다.그렇다는건 너무 쉽다는 거고 깊은 생각을 할 필요가 없는 문제다. 4 12 3 8 4 예제와 같이 12 3 8 4가 입력이 되고 첫번째 링인 12가 한바퀴 돌았을때 다른 링들은 볓바퀴 돌것이냐 라는 말이다. 그럼 12와 각 링들의 최대 공약수를 구해서 나눠 주면 되겠구나 생각했다. 최대공약수 나눈다면 자연스럽게 기약분수로 만들어 질것이다. 12와 3의 최대 공약수는 3 -> 12 / 3 + "/" +3 / 3 하면 4/112와 8의 최대 공약수는 4 -> 12 / 4 + "/" + 8/4 하면 3/212와 4의 최대 공약수는 4 -> 12 / 4 + "/" + 4/4 하면 3/1 다 구했다 아..
-
[백준 2981] - [수학 최대공약수] - 검문 (JAVA)알고리즘/수학 2018. 12. 4. 11:07
문제 링크 : https://www.acmicpc.net/problem/2981 이 문제는 정답률에서도 나오듯이 극악의 문제이다. 왜 극악이라 하냐면 쓸데없는데서 시간을 낭비 했기에 극악의 문제로 생각한다. 6 34 38 총 3개의 수가 주어지고 종이에 적은수 M으로 나누었을때 나머지가 모두 같게 되는 모든 M을 찾아 보기위해 노력 해봤다. 처음에는 시간초과가 발생했다. 시간초과를 발생하게한 방식은 다음과 같다. 입력 받은 수의 배열 arr에서 인덱스 1번부터 arr.length-2 까지 반복하면서 i 기준 arr[i] - arr[i-1] , arr[i+1] - arr[i] 두 수의 최대 공약수를 구하고 그 최대 공약수중에서 제일 작은 최대 공약수의 약수를 반환했다. 결과는 제대로 나왔다. 하지만 시간 ..
-
[백준 1850] - [ 수학 최대공약수 ] - 최대공약수 (JAVA)알고리즘/수학 2018. 12. 4. 01:42
문제 링크 : https://www.acmicpc.net/problem/1850 이 문제는 어려움을 가장한 쉬운 문제이다. 낮은 정답률에 겁을 먹고 다들 시도를 하지 못한거 같다. 예제 입력 3번의 값이 이 문제는 변태적인 문제다 겁을 먹어라 하는거 같다. 500000000000000000 500000000000000002예제 입력 1번의3 4로 보면 111과 1111의 최대 공약수를 구하면 되겠구나!! 하겠지만 예제 입력 3번은 어떻게 하라고.. 1을 저만치 쓰라고?? 하면서 겁을 먹게 하는거 같다. 그냥 단번에 아 낚시구나 생각했고 두 수의 최대 공약수를 구해보았다. 예제 입력 1 의 입력값 3 4의 최대 공약수는 1예제 입력 2 의 입력값 3, 6의 최대 공약수는 3예제 입력 3의 입력값 무진장 큰..
-
[백준 13241] - [수학] - 최소공배수 (JAVA)알고리즘/수학 2018. 12. 4. 01:33
문제링크 : https://www.acmicpc.net/problem/13241 이 문제는 쉬운 문제이므로 이전글을 첨부하면서 설명을 마친다.아래 두 문제를 푼다면 이문제는 너무 쉬워서 심지어 눈감고 풀 수도 있겠다. 2018/12/03 - [알고리즘/수학] - [백준 2609] - [수학 최소공배수 최대공약수] - 최대공약수와 최소공배수(JAVA) 2018/12/04 - [알고리즘/수학] - [백준 1934] - [수학] - 최소공배수 (JAVA) 소스 123456789101112131415161718192021222324import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = ne..
-
[백준 1934] - [수학] - 최소공배수 (JAVA)알고리즘/수학 2018. 12. 4. 01:30
문제 링크 : https://www.acmicpc.net/problem/1934 이 문제는 백준 2609문제를 먼저 풀었다면 문제 푸는데 걸리는 시간은 금방일 것이다. 이번문제에 대한 설명 최소 공배수와 최대 공약수에 대한 설명은 백준 2609번 문제 링크와 풀이 링크로 대체하겠다. 백준 2609 문제 2018/12/03 - [알고리즘/수학] - [백준 2609] - [수학 최소공배수 최대공약수] - 최대공약수와 최소공배수(JAVA) 소스123456789101112131415161718192021222324252627282930313233343536import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReade..
-
[백준 2609] - [수학 최소공배수 최대공약수] - 최대공약수와 최소공배수(JAVA)알고리즘/수학 2018. 12. 3. 15:35
문제 링크 : https://www.acmicpc.net/problem/2609 이문제는 입력 받는 두 수의 최대 공약수와 최소 공배수를 구하는 문제이다. 최대 공약수는 두 개 이상의 수가 공통으로 가지는 약수 중 가장 큰 수를 말한다. 두 수 18과 24가 있다 하면 각각의 약수는 다음과 같다.18의 약수 : 1, 2, 3, 6, 9, 1824의 약수 : 1, 2, 3, 4, 6, 8, 12, 24이들 약수중에 공통으로 가지는 약수는 {1, 2, 3, 6}이고 이들 중 가장 큰 수는 6이 된다. 먼저 18의 약수를 구하고 24의 약수를 구한다음 각 각 의 약수중에서 공통 약수를 추려낸 뒤 그중 제일 큰 수를 찾았다. 수의 크기가 작은 경우 빠르게 구할 수 있겠지만 만약 수가 큰 수라면 어떻게 될까?각각..
-
[백준 9020]-[수학] - 골드바흐의 추측알고리즘/수학 2018. 11. 27. 15:14
문제링크 : https://www.acmicpc.net/problem/9020 이 문제는 에라토스테네스의 체의 확장 문제이다. 에라토스테네스의 체 문제는 이전글에서 확인하면 된다. 2018/11/27 - [알고리즘/수학] - [백준 1929]-[수학]-[에라토스테네스의 체] - 소수 구하기 (java) 이 문제를 접근하는 방법은 입력받은 수 N을 구성하는 두 소수의 합을 구하면 된다. 두 소수의 합이 여러가지가 있다면 두 수의 차가 제일 적을 수를 구하면 된다. 그럼 N 보다 작은 모든 소수들을 찾아서 합해야하나 하지만 그렇지 않아도 된다. N 의 절반인 수를 기준으로 하나의 수는 1씩 감소하고 다른 하나는 1씩 증가하면서 두 수가 실수 인경우를 찾으면 위의 조건을 모두 만족한다. 입력받은 수가 16인 ..