본문 바로가기

Algorithm61

C# [백준 BAEKJOON] 2824번 최대공약수 문제 상근이는 학생들에게 두 양의 정수 A와 B의 최대공약수를 계산하는 문제를 내주었다. 그런데, 상근이는 학생들을 골탕먹이기 위해 매우 큰 A와 B를 주었다. 상근이는 N개의 수와 M개의 수를 주었고, N개의 수를 모두 곱하면 A, M개의 수를 모두 곱하면 B가 된다. 이 수가 주어졌을 때, 최대공약수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다. 셋째 줄에 M(1 ≤ M ≤ 1000)이 주어진다. 넷째 줄에는 M개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, M개의 수를.. 2024. 3. 15.
C# [백준 BAEKJOON] 13277번 큰 수 곱셈 문제 두 정수 A와 B가 주어졌을 때, 두 수의 곱을 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 정수 A와 B가 주어진다. 두 정수는 0보다 크거나 같은 정수이며, 0을 제외한 정수는 0으로 시작하지 않으며, 수의 앞에 불필요한 0이 있는 경우도 없다. 또한, 수의 길이는 300,000자리를 넘지 않는다. 출력 두 수의 곱을 출력한다. 13277번: 큰 수 곱셈 첫째 줄에 정수 A와 B가 주어진다. 두 정수는 0보다 크거나 같은 정수이며, 0을 제외한 정수는 0으로 시작하지 않으며, 수의 앞에 불필요한 0이 있는 경우도 없다. 또한, 수의 길이는 300,000자리를 www.acmicpc.net 1차 풀이 코드(메모리 초과 실패) using System; using System.Linq; using .. 2024. 3. 14.
C# [백준 BAEKJOON] 2960번 에라토스테네스의 체 문제 에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다. 이 알고리즘은 다음과 같다. 2부터 N까지 모든 정수를 적는다. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하고, 이 수는 소수이다. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다. N, K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 N과 K가 주어진다. (1 ≤ K < N, max(1, K) < N ≤ 1000) 출력 첫째 줄에 K번째 지워진 수를 출력한다. 2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이.. 2024. 3. 11.
C# [백준 BAEKJOON] 9020번 골드바흐의 추측 문제 1보다 큰 자연수 중에서 1과 자기 자신을 제외한 약수가 없는 자연수를 소수라고 한다. 예를 들어, 5는 1과 5를 제외한 약수가 없기 때문에 소수이다. 하지만, 6은 6 = 2 × 3 이기 때문에 소수가 아니다. 골드바흐의 추측은 유명한 정수론의 미해결 문제로, 2보다 큰 모든 짝수는 두 소수의 합으로 나타낼 수 있다는 것이다. 이러한 수를 골드바흐 수라고 한다. 또, 짝수를 두 소수의 합으로 나타내는 표현을 그 수의 골드바흐 파티션이라고 한다. 예를 들면, 4 = 2 + 2, 6 = 3 + 3, 8 = 3 + 5, 10 = 5 + 5, 12 = 5 + 7, 14 = 3 + 11, 14 = 7 + 7이다. 10000보다 작거나 같은 모든 짝수 n에 대한 골드바흐 파티션은 존재한다. 2보다 큰 짝수.. 2024. 3. 11.
C# [백준 BAEKJOON] 10992번 별 찍기 - 17 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 출력 첫째 줄부터 N번째 줄까지 차례대로 별을 출력한다. 10992번: 별 찍기 - 17 첫째 줄부터 N번째 줄까지 차례대로 별을 출력한다. www.acmicpc.net 풀이 코드 using System; using System.Text; class Program { static void Main(string[] args) { var input = Console.ReadLine(); var count = Int32.Parse(input); var sb = new StringBuilder(); for (int i = 0; i < count; i++) { for (int j = count - i;.. 2024. 3. 8.
C# [백준 BAEKJOON] 2445번 별 찍기 - 8 문제 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요. 입력 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 출력 첫째 줄부터 2×N-1번째 줄까지 차례대로 별을 출력한다. 10951번: A+B - 4 두 정수 A와 B를 입력받은 다음, A+B를 출력하는 프로그램을 작성하시오. www.acmicpc.net 풀이 코드 기존에 작성했던 별찍기를 응용해서 풀이가 가능하다. * ** *** **** ***** **** *** ** * 이렇게 작성한 코드를 동일하게 반전시켜서 출력하면 해당 문제의 풀이가 가능하다. using System; using System.Text; class Program { static void Main(string[] args) { var input = Console.ReadLin.. 2024. 3. 8.

티스토리툴바