Hello, There

https://www.acmicpc.net/problem/1850 1850번: 최대공약수 모든 자리가 1로만 이루어져있는 두 자연수 A와 B가 주어진다. 이때, A와 B의 최대 공약수를 구하는 프로그램을 작성하시오. 예를 들어, A가 111이고, B가 1111인 경우에 A와 B의 최대공약수는 1이고, A www.acmicpc.net 자리수를 입력받아 모든 자리수가 1로만 이루어진 두 수의 최대 공약수를 구하는 문제. 최대 공약수를 구하면 되는 문제이므로 유클리드 호제법을 적용하면 된다는 것을 바로 알 수있다. 하지만 문제에서 자리수의 범위가 2의 63제곱 -1 까지 주어졌으므로 직접 두 자연수 A, B를 구해서 문제를 풀 수는 없다. 힌트는 자리수가 3, 4인 수, 즉 자리수의 최대 공약수가 1인 두 수..

https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 에라토스테네스의 체를 활용하는 문제 https://namu.wiki/w/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98%20%EC%B2%B4 에라토스테네스의 체 - 나무위키 임의의 자연수 n에 대해 그 이하의 소수를 모두 찾는, 가장 간단하고 빠른[2] 방법이다. 예를 들어 1~100까지 숫자 중 소수를 찾는다 하자. 일단 1부터 100까지 숫자를..

https://www.acmicpc.net/problem/1541 1541번: 잃어버린 괄호 첫째 줄에 식이 주어진다. 식은 ‘0’~‘9’, ‘+’, 그리고 ‘-’만으로 이루어져 있고, 가장 처음과 마지막 문자는 숫자이다. 그리고 연속해서 두 개 이상의 연산자가 나타나지 않고, 5자리보다 www.acmicpc.net 수식이 주어지고 괄호를 어떻게 쳐야 수식의 결과가 최소가 나오는지 묻는 문제. 10+20+30+40의 최소가 100인 것으로 보아 숫자를 쪼개서 괄호를 넣을 수는 없다. 단순히 덧셈과 뺄셈만으로 이루어진 연산이므로 결과가 가장 작으려면, 가능한 큰 수를 빼야 한다. +, - 부호가 하나만 나타나는 것이 아니므로 가능한 큰 수를 빼기 위해서는 - 부호가 나타나면 괄호를 열고, 또 - 부호가 나..

https://www.acmicpc.net/problem/2839 2839번: 설탕 배달 상근이는 요즘 설탕공장에서 설탕을 배달하고 있다. 상근이는 지금 사탕가게에 설탕을 정확하게 N킬로그램을 배달해야 한다. 설탕공장에서 만드는 설탕은 봉지에 담겨져 있다. 봉지는 3킬로그 www.acmicpc.net 5kg의 설탕 봉지와 3kg의 설탕 봉지가 있을 때, 가장 봉지를 적게 골라 주어진 무게를 채우는 문제이다. 가장 봉지를 적게 고르기 위해서는 당연히 가장 무거운 봉지를 최대한 고르는 것이 최선의 선택지이다. 따라서 5kg의 봉지를 최대한 고르고, 나머지를 3kg의 봉지로 만족시킬 수 없다면, 5kg 봉지의 개수를 1개씩 줄이고 3kg 봉지를 늘려가며 선택하면 된다. import java.io.*; publ..

https://www.acmicpc.net/problem/1931 1931번: 회의실 배정 (1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다. www.acmicpc.net 그리디 알고리즘을 활용하는 문제. 최대한 많은 회의를 선택할 수 있기 위해서는 회의 시간대가 겹치지 않아야 한다. 따라서 나는 그리디 알고리즘에서 '최선의 선택지'는 회의 시간이 짧은 시간이라고 생각하였다. 회의 시간이 짧은 강의부터 배치하면 최대한 많은 회의를 시간표에 배치할 수 있을 것으로 기대했다. 따라서 회의시간 따라 정렬되는 우선 순위 큐를 만들고, 선택된 회의를 저장할 ArrayList를 만들었다. 1. 회의 시간이 짧은 회의가 우선이 되는 큐에 강의들을 정렬한다. 2. 큐에서 모든 회의를 꺼낼때 까지..

https://www.acmicpc.net/problem/11047 11047번: 동전 0 첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) www.acmicpc.net 그리디 알고리즘을 활용하는 문제. 1.최적이라 생각하는 선택지를 고르고 조건에 부합하는 지 검사한다. 2.선택한 해가 문제를 해결하는지 검사한다. 3.해결하지 못하면 다시 다른 선택지를 고른다. 이번 문제에서는 주어진 동전으로 K원을 맞춰야 하는 문제이다. 예제를 보면 오름차순으로 주어진 10 종류의 동전을 활용해 4200원을 만들어..