JAVA - 백준 [BAEK JOON]/정수론 및 조합론
[백준] 1010번 : 다리 놓기 - JAVA [자바]
[백준] 1010번 : 다리 놓기 - JAVA [자바]
2021.01.18www.acmicpc.net/problem/1010 1010번: 다리 놓기 입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다. www.acmicpc.net 문제 문제만 제대로 이해한다면 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 문제는 매우 간단하다. 우선 문제에서 두 가지 포인트를 짚고 넘어가보자. 1. 한 사이트에는 한 개의 다리만 놓일 수 있다. 2. 서로 다른 다리가 겹치면 안된다. 즉, 위 그림처럼 첫 번째 같이 서로 겹치지 않게 다리를 놓는 경우 외엔 한 사이트에 두개의 다리가 놓이거나, 서로 다른 다리가 가로지르면 안된다. 그럼 무엇을 생각할 ..
[백준] 1934번 : 최소공배수 - JAVA [자바]
[백준] 1934번 : 최소공배수 - JAVA [자바]
2021.01.17www.acmicpc.net/problem/1934 1934번: 최소공배수 두 자연수 A와 B에 대해서, A의 배수이면서 B의 배수인 자연수를 A와 B의 공배수라고 한다. 이런 공배수 중에서 가장 작은 수를 최소공배수라고 한다. 예를 들어, 6과 15의 공배수는 30, 60, 90등이 있 www.acmicpc.net 문제 바로 직전 문제인 '최대공약수와 최소공배수' 문제를 풀었다면 그리 어렵지 않게 풀 수 있었을 것이다. 알고리즘 [접근 방법] 이 문제는 유클리드 알고리즘으로 풀라고 나온 문제다. 즉, 유클리드 호제법(Euclidean algorithm)을 사용하라는 것인데, 앞서 필자가 이미 '최대공약수와 최소공배수' 문제를 풀이하면서 설명했다. '꼭 아래 포스팅을 먼저 보고 오시길 바란다' http:..
[백준] 2004번 : 조합 0의 개수 - JAVA [자바]
[백준] 2004번 : 조합 0의 개수 - JAVA [자바]
2020.11.07www.acmicpc.net/problem/2004 2004번: 조합 0의 개수 첫째 줄에 정수 n, m (0 ≤ m ≤ n ≤ 2,000,000,000, n ≠ 0)이 들어온다. www.acmicpc.net 문제 이전의 팩토리얼 0의 개수를 정확히 이해하고 풀었다면 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 먼저 이 문제를 풀기 전에 아래 글에서 다루고 있는 0의 개수를 세는 방식을 이해하기 위해 보는 것을 추천한다. st-lab.tistory.com/165 [백준] 1676번 : 팩토리얼 0의 개수 - JAVA [자바] www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하..
[백준] 1676번 : 팩토리얼 0의 개수 - JAVA [자바]
[백준] 1676번 : 팩토리얼 0의 개수 - JAVA [자바]
2020.11.05www.acmicpc.net/problem/1676 1676번: 팩토리얼 0의 개수 N!에서 뒤에서부터 처음 0이 아닌 숫자가 나올 때까지 0의 개수를 구하는 프로그램을 작성하시오. www.acmicpc.net 문제 정말 정말 쉬운 문제다. 알고리즘 [접근 방법] 이러한 문제는 직감상 어떤 규칙이 있겠구나라고 생각하면 더욱 좋다. 물론, 그러지 않고 입력값에 대하여 factorial 값을 구하고, 뒤의 0의 개수를 구하는 것도 방법일 수는 있다. 그러나 입력값이 최대 500, 즉 500! 을 구해야 하는지라 BigInteger 클래스를 써서 구해야 하거니와 값도 매우 크다. 참고로 500! 의 값은 다음과 같다. 500! = 12201368259911100687012387854230469262535743..
[백준] 9375번 : 패션왕 신해빈 - JAVA [자바]
[백준] 9375번 : 패션왕 신해빈 - JAVA [자바]
2020.11.04www.acmicpc.net/problem/9375 9375번: 패션왕 신해빈 첫 번째 테스트 케이스는 headgear에 해당하는 의상이 hat, turban이며 eyewear에 해당하는 의상이 sunglasses이므로 (hat), (turban), (sunglasses), (hat,sunglasses), (turban,sunglasses)로 총 5가지 이다. www.acmicpc.net 문제 이 번 문제도 조합과 관련된 문제다. 그리 어렵지 않으니 쉽게 풀 수 있을 것이다. 알고리즘 [접근 방법] 밑에 있는 힌트란을 읽어보았다면 문제는 금방 이해가 갈 것이다. 의상 이름과 의상 종류가 주어지고, 한 번 입었던 '조합'은 다시 입지 않는다는 것과, 옷의 종류가 중복되게 입을 수 없다는 것이 중요한 포인트..
[백준] 11051번 : 이항 계수 2 - JAVA [자바]
[백준] 11051번 : 이항 계수 2 - JAVA [자바]
2020.10.30www.acmicpc.net/problem/11051 11051번: 이항 계수 2 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 1,000, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제 이전의 이항 계수 1 문제와 같은 문제다. 다만 출력할 때 이항 계수 값에 10,007로 나눈 나머지를 출력해야 한다는 점이다. 알고리즘 [접근 방법] 일단 이 문제를 풀기 전에 이전에 풀었던 3가지 방식으로 이항 계수를 풀이하는 법을 보고오셨으면 한다. st-lab.tistory.com/159 [백준] 11050번 : 이항 계수 1 - JAVA [자바] www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어..
[백준] 11050번 : 이항 계수 1 - JAVA [자바]
[백준] 11050번 : 이항 계수 1 - JAVA [자바]
2020.10.27www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제 알고리즘 [접근 방법] 이항 계수(Binomial coefficient) 문제 자체는 매우매우 쉽다. 지금은 배우는지는 모르겠지만 고교과정에서 조합을 배웠다면 쉽게 풀었을 것이다. en.wikipedia.org/wiki/Binomial_coefficient Binomial coefficient - Wikipedia The binomial coefficients can be arranged to form Pascal's triangle, in which each entry is th..
[백준] 3036번 : 링 - JAVA [자바]
[백준] 3036번 : 링 - JAVA [자바]
2020.10.23www.acmicpc.net/problem/3036 3036번: 링 출력은 총 N-1줄을 해야 한다. 첫 번째 링을 제외한 각각의 링에 대해서, 첫 번째 링을 한 바퀴 돌리면 그 링은 몇 바퀴 도는지 기약 분수 형태 A/B로 출력한다. www.acmicpc.net 문제 알고리즘 [접근 방법] 음.. 달리 설명 할 필요가 없는 문제다. 위 예제를 보면 첫 번째 링의 반지름이 12이고, 이 링이 한 바퀴 돌 때 나머지 링이 몇 바퀴가 도는지를 '기약 분수'로 출력하는 문제다. 어? 그러면 둘레를 구해야 하나? 라고 생각해서 둘레로 구하는 경우도 봤는데, 모든 도형이 모두 원이기 때문에 둘레를 구할 필요가 없다. 왜 그런지 감이 안온다면 위 예제를 갖고 한 번 적용해보자. 첫 번째 링의 둘레 : R1 = 2π..
[백준] 2981번 : 검문 - JAVA [자바]
[백준] 2981번 : 검문 - JAVA [자바]
2020.10.22www.acmicpc.net/problem/2981 2981번: 검문 트럭을 타고 이동하던 상근이는 경찰의 검문을 받게 되었다. 경찰은 상근이가 운반하던 화물을 하나하나 모두 확인할 것이기 때문에, 검문하는데 엄청나게 오랜 시간이 걸린다. 상근이는 시간 www.acmicpc.net 문제 생각보다 정답비율이 엄청 낮은 문제다.. 필자도 작성과정에 실수한 것이 있어서 한 번 틀렸다만, 진짜 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 이 문제를 풀이하기 전에 먼저 최대공약수를 어떻게 풀이하는지, '유클리드 호제법'이 무엇인지를 알아야 할 필요가 있다. 한 번 아래의 포스팅 글을 보고 오면 좋을 것 같다. 최대공약수 알고리즘 [백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바] www.ac..
[백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바]
[백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바]
2020.10.20www.acmicpc.net/problem/2609 2609번: 최대공약수와 최소공배수 첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다. www.acmicpc.net 문제 알고리즘 [접근 방법] 아마 알고리즘을 많이 접해본 사람들은 GCD를 사용하여 풀었거나 한 번쯤은 들어봤을 것이다. 일단 간단한 알고리즘 코드로 보자면 이렇다. [GCD] // 반복문 방식 int gcd(int a, int b) { while(b != 0) { int r = a % b; a = b; b = r; } return a; } // 재귀 방식 int gcd(int a, int b) { if(b == 0) return a; return gcd(b, a % b); }..