JAVA - 백준 [BAEK JOON]
[백준] 2438번 : 별 찍기 - 1 - JAVA [자바]
[백준] 2438번 : 별 찍기 - 1 - JAVA [자바]
2020.10.25
[백준] 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); }..
[백준] 11653번 : 소인수분해 - JAVA [자바]
[백준] 11653번 : 소인수분해 - JAVA [자바]
2020.10.18www.acmicpc.net/problem/11653 11653번: 소인수분해 첫째 줄에 정수 N (1 ≤ N ≤ 10,000,000)이 주어진다. www.acmicpc.net 문제 소인수 분해 문제다. 찾아보니 중학교 교과과정에서 배운다고 하니 아마 다들 쉽게 풀 수 있을 듯 하다. 알고리즘 [접근 방법] 소인수분해 문제 자체는 어렵지 않으니 잠깐 소인수분해에 대해 알아보면 좋을 것 같다. 소인수분해가 어릴 때 부터 배우면서 약수와 배수를 구하기 위해 쓰이면서 자연스럽게 많이 쓰기 때문에 어떤 것인지는 대강 알고있으나 정확한 정의나 왜 소인수분해인지는 모르고 가는 경우가 많다. 사실 수학용어를 번역하면서 한자 뜻을 빌려와 쓰기 때문에 그렇기도 하다. 오히려 영어 뜻을 그대로 번역하는게 이해하기 쉬울 때..
[백준] 1037번 : 약수 - JAVA [자바]
[백준] 1037번 : 약수 - JAVA [자바]
2020.10.15www.acmicpc.net/problem/1037 1037번: 약수 첫째 줄에 N의 진짜 약수의 개수가 주어진다. 이 개수는 50보다 작거나 같은 자연수이다. 둘째 줄에는 N의 진짜 약수가 주어진다. 1,000,000보다 작거나 같고, 2보다 크거나 같은 자연수이고, 중복되� www.acmicpc.net 문제 알고리즘 [접근 방법] 이 문제는 그리 어렵지 않은 문제지만, 한가지 주의해야 할 점이 있다. "최소공배수로 구하면 틀린다." 이유는 문제에서 보면 이렇게 쓰여 있다. "어떤 수 N의 진짜 약수가 모두 주어질 때" 이 부분 때문에 단순히 최소공배수로 구하면 오답이 된다. 예로 들어보자. N = 30 이라고 가정하면 입력은 다음과 같이 들어올 것이다. 2, 3, 5, 6, 10, 15 그 외의 입력..
[백준] 5086번 : 배수와 약수 - JAVA [자바]
[백준] 5086번 : 배수와 약수 - JAVA [자바]
2020.10.14www.acmicpc.net/problem/5086 5086번: 배수와 약수 각 테스트 케이스마다 첫 번째 숫자가 두 번째 숫자의 약수라면 factor를, 배수라면 multiple을, 둘 다 아니라면 neither를 출력한다. www.acmicpc.net 문제 수학 3 카테고리의 첫 문제다! 알고리즘 [접근 방법] 이번 문제는 워낙 쉬운 문제라 크게 설명 할 것이 없다. 두 수가 주어질 때 다음 조건 아래 만족하는 것에 따라 출력을 해주면 된다. 1. 첫 번째 수가 두 번째 수의 약수일 때 (= 두 번째 수가 첫 번째 수의 배수일 때) 2. 첫 번째 수가 두 번째 수의 배수일 때 (= 두 번째 수가 첫 번째 수의 약수일 때) 3. 첫 번째 수와 두 번째 수가 서로 약수와 배수의 관계가 아닐 때 // 첫 ..
[백준] 1541번 : 잃어버린 괄호 - JAVA [자바]
[백준] 1541번 : 잃어버린 괄호 - JAVA [자바]
2020.10.08www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 문제 이 번 문제 또한 그리 어렵지 않게 풀 수 있는 문제다. 문제만 잘 이해한다면 금방 이해할 수 있을 것이다. 알고리즘 [접근 방법] 위 문제에서 주어지는 예제는 다음과 같다. 55-50+40 그럼 여러분들은 아주 쉽게 괄호를 쳐서 '최솟값'을 다음과 같이 만들 수 있다. 55-(50+40) 그럼 정답은 -35가 된다. 다른 예시들을 보자. 30-70-20+40-10+100+30-35 가 있다고 생각해..
[백준] 11399번 : ATM - JAVA [자바]
[백준] 11399번 : ATM - JAVA [자바]
2020.10.07www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 이 또한 활동 선택 문제(Activity Selection Problem) 문제로 볼 수 있다. 조금만 이해하면 쉽게 풀 수 있는 문제다. 알고리즘 [접근 방법] 앞서 포스팅 했던 문제인 회의실배정과 유사한 문제다. 문제를 잘 이해해야 하는 것이 '종료 시간'이 아니라 '대기 시간의 총합'을 구하는 문제라는 점. 즉, 어떻게 배치하던 총 걸리는 같더라도, 한 사람이 대기하는 시간은 달라질 수 있다. 상식적으로 대기시간을 줄이려면 앞 사..
[백준] 1931번 : 회의실배정 - JAVA [자바]
[백준] 1931번 : 회의실배정 - JAVA [자바]
2020.10.05www.acmicpc.net/problem/1931 1931번: 회의실배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 문제 그리디 알고리즘의 대표적인 문제 중 하나다. 알고리즘 [접근 방법] 위와 같이 시간표를 최대한 많이 배정하거나 선택하는 문제를 '활동 선택 문제(Activity Selection problem)'라고 한다. 간단하게 설명하자면, 한 사람이 하나의 활동에 대해서만 작업할 수 있을 때 최대한 많은 활동을 할 수 있는 수를 선택하는 문제다. 위에서는 각 회의가 겹치지 않게 최대한 많은 회의를 배정하는 것으로 나와있다. 이러한 문제들의 특징은 '한 사람이 하나의 활동에 대해서만 작업할 수 있다'라는 점이다. 즉, 하나의 활동을 완..