Algorithm Study Algorithm Study

분수합 (fractionsum.cpp) 문제분자 분모가 모두 자연수인 두 분수의 합 또한 분자 분모가 자연수인 분수로 표현할 수 있다.두 분수가 주어졌을 때, 그 합을 기약분수의 형태로 구하는 프로그램을 작성하시오.기약분수란 더 이상 약분되지 않는 분수를 의미한다. 입력첫째 줄과 둘째 줄에, 각 분수의 분자와 분모를 뜻하는 두 개의 자연수가 순서대로 주어진다. 입력되는 네 자연수는 모두 30,000 이하이다. 출력첫째 줄에 구하고자 하는 기약분수의 분자와 분모를 뜻하는 두 개의 자연수를 공백으로 구분하여 순서대로 출력한다. 예제 입력2 7 3 5예제 출력31 35 import java.util.Scanner; public class FractionSum { /** * 분자 분모가 모두 자연수인 두 분수의..

가로수 (streetree.cpp) 문제직선으로 되어있는 도로의 한 편에 가로수가 임의의 간격으로 심어져있다. KOI 시에서는 가로수들이 모두 같은 간격이 되도록 가로수를 추가로 심는 사업을 추진하고 있다. KOI 시에서는 예산문제로 가능한 한 가장 적은 수의 나무를 심고 싶다.편의상 가로수의 위치는 기준점으로 부터 떨어져 있는 거리로 표현되며, 가로수의 위치는 모두 양의 정수이다.예를 들어, 가로수가 (1, 3, 7, 13)의 위치에 있다면 (5, 9, 11)의 위치에 가로수를 더 심으면 모든 가로수들의 간격이 같게 된다. 또한, 가로수가 (2, 6, 12, 18)에 있다면 (4, 8, 10, 14, 16)에 가로수를 더 심어야 한다.심어져 있는 가로수의 위치가 주어질 때, 모든 가로수가 같은 간격이 ..

최소공배수 (lcm.cpp) 문제정수 B를 0보다 큰 정수인 N으로 곱해 정수 A를 구할 수 있다면 A는 B의 배수이다.예:10은 5의 배수이다 (5*2 = 10)10은 10의 배수이다(10*1 = 10)6은 1의 배수이다(1*6 = 6)20은 1, 2, 4,5,10,20의 배수이다.다른 예:2와 5의 최소공배수는 10이고, 그 이유는 10은 2와 5 둘 다의 배수이고, 10보다 작은 공배수가 없기 때문이다.10과 20의 최소공배수는 20이다.5와 3의 최소공배수는 15이다.당신은 두 수에 대하여 최소공배수를 구하는 프로그램을 작성 하는 것이 목표이다. 입력한 줄에 두 자연수 A와 B가 공백으로 분리되어 주어진다.A와 B는 100000000(108)보다 작다.참고: 큰 수 입력에 대하여 변수를 64비트 ..

조합 0의 개수 (combinationzero.cpp) 문제n명의 사람중 m명을 순서에 상관없이 뽑는 경우의 수를 조합이라고 하며 nCm으로 나타낸다.nCm은 수식으로 n!/m!(n-m)! 으로 구할 수 있다. (5! = 12345)n과 m이 주어졌을때 nCm의 끝자리 0의 개수를 출력하는 프로그램을 작성하시오. 입력첫째 줄에 정수 n, m(0≤m≤n≤1,000,000)이 들어온다. 출력첫째 줄에 0의 개수를 출력한다. 예제 입력25 12예제 출력2import java.util.Scanner; public class combinationzero { /** * n명의 사람중 m명을 순서에 상관없이 뽑는 경우의 수를 조합이라고 하며 nCm으로 나타낸다. * * 이 조합은 파스칼의 삼각형과 아주 밀접한 관련이..

파스칼의 삼각형과 조합 (combinationpascal.cpp) 문제n명의 사람중 m명을 순서에 상관없이 뽑는 경우의 수를 조합이라고 하며 nCm으로 나타낸다.이 조합은 파스칼의 삼각형과 아주 밀접한 관련이 있다고 한다.n과 m이 주어졌을때 nCm의 값을 출력하는 프로그램을 작성하시오. 입력첫째 줄에 정수 n, m(0≤m≤n≤30)이 들어온다. 출력첫째 줄에 nCm의 값을 출력한다. 예제 입력5 2예제 출력10import java.util.Scanner; public class combinationpascal { /** * n명의 사람중 m명을 순서에 상관없이 뽑는 경우의 수를 조합이라고 하며 nCm으로 나타낸다. * * 이 조합은 파스칼의 삼각형과 아주 밀접한 관련이 있다고 한다. * * n과 m이 ..

준혁이의 수열 (sequencesum.cpp) 문제준혁이는 양의 정수 N개로 이루어진 수열 A의 정체를 아무에게나 알려주고 싶지 않았다. 그래서 준혁이는 수열 A의 모든 두 수의 합만을 적어놓고 이를 S라고 했다. 이 때, 수열 A를 구하는 프로그램을 작성하시오. 입력첫째 줄에 수열의 크기 N이 주어진다. (3 ≤ N ≤ 1000)다음 N개 줄에는 100,000보다 작거나 같은 양의 정수가 N개씩 주어진다. 이 숫자들은 S를 이루는 숫자이며, S(i,j) = A[i] + A[j] (i≠j), S(i,j) = 0 (i=j) 이다. S(i,j)는 i번째 줄, j번째 숫자를 의미하며, A[i]는 A의 i번째 수이다.입력으로 주어지는 S에 해당하는 수열 A는 항상 유일하다. 출력첫째 줄에 수열 A를 출력한다. ..

홍준이와 수열 (PROSJEK.cpp) 문제홍준이는 심심해서 수열을 가지고 놀고 있다. 먼저, 정수 수열 A를 쓴다. 그리고 그 아래에 정수 수열 A의 해당 항까지의 평균값을 그 항으로 하는 정수 수열 B를 쓴다.예를 들어, 수열 A가 1, 3, 2, 6, 8이라면, 수열 B는 1/1, (1+3)/2, (1+3+2)/3, (1+3+2+6)/4, (1+3+2+6+8)/5, 즉, 1, 2, 2, 3, 4가 된다.수열 B가 주어질 때, 홍준이의 규칙에 따른 수열 A는 뭘까? 입력첫째 줄에는 수열 B의 길이만큼 정수 N(1 ≤ N ≤ 100)이 주어지고, 둘째 줄에는 수열 B를 이루는 N개의 정수가 주어진다. 각 정수는 1,000,000,000 이하의 자연수이다.입력은 A 수열을 이루는 수들이 모두 1,000,..

피보나치 수열 (fibonacci.cpp) 문제피보나치 수열은 수학에서 아주 유명한 수열이다. 피보나치 수열을 이루는 수들을 피보나치 수라고 한다.피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 된다.n이 0 ~ 15일때 까지 피보나치 수를 써보면 다음과 같다.0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오. 입력첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다. 출력첫째 줄에 n번째 피보나치 ..