본문 바로가기

전체 글376

[백준] 2775번 : 부녀회장이 될테야 – JAVA [자바] https://www.acmicpc.net/problem/2775 2775번: 부녀회장이 될테야 첫 번째 줄에 Test case의 수 T가 주어진다. 그리고 각각의 케이스마다 입력으로 첫 번째 줄에 정수 k, 두 번째 줄에 정수 n이 주어진다 www.acmicpc.net 문제 문제 풀이 백준 2775번 부녀회장이 될테야는 브론즈 1 난이도의 수학 및 구현 문제이다. 이 문제에서는 테스트 케이스의 개수 T가 주어지고 각 테스트 케이스마다 정수 k와 n도 같이 주어진다. 그리고 k층 n호에 몇 명이 사는지를 출력하면 되는 문제이다. 이 문제에서는 추가 조건도 있다. 바로 “a층의 b호에 살려면 자신의 아래(a-1)층의 1호부터 b호까지 사람들의 수의 합만큼 사람들을 데려와 살아야 한다”는 조건이다. 추가로 .. 2022. 7. 15.
[백준] 2920번 : 음계 – JAVA [자바] https://www.acmicpc.net/problem/2920 2920번: 음계 다장조는 c d e f g a b C, 총 8개 음으로 이루어져있다. 이 문제에서 8개 음은 다음과 같이 숫자로 바꾸어 표현한다. c는 1로, d는 2로, ..., C를 8로 바꾼다. 1부터 8까지 차례대로 연주한다면 ascending, 8 www.acmicpc.net 문제 문제 풀이 백준 2920번 음계는 브론즈 브론즈 2 난이도의 구현 문제이다. 이 문제에서는 8개의 숫자가 주어진다. 만약에 1부터 8까지 연속으로 주어지면 ascending을, 8부터 1까지 연속으로 주어지면 descending을, 둘 다 아니면 mixed를 출력하면 되는 문제이다. 이 문제는 되게 간단하게 풀 수 있다. 우선 배열 arr에 주어지는 .. 2022. 7. 15.
[백준] 15965번 : K번째 소수 – JAVA [자바] https://www.acmicpc.net/problem/15965 15965번: K번째 소수 자연수 K가 주어진다.(1 ≤ K ≤ 500,000) www.acmicpc.net 문제 문제 풀이 백준 15965번 K번째 소수는 실버 2 난이도의 수학 및 에라토스테네스의 체 문제이다. 이 문제는 추가로 부산일과학고 BSIS배 Code Festival에서 D번 문제로 출제된 문제이기도 하다. 이 문제 자체는 간단하다. 문제에서 입력으로 자연수 K가 주어지는데 K번째 소수를 출력하기만 하면 된다. 이 문제는 에라토스테네스의 체를 이용해서 풀 수 있다. 아직 에라토스테네스의 체에 대해서 잘 모르면 밑에 있는 링크를 참고하면 되겠다. https://propercoding.tistory.com/182 [알고리즘] 에.. 2022. 7. 15.
[백준] 1978번 : 소수 찾기 – JAVA [자바] https://www.acmicpc.net/problem/1978 1978번: 소수 찾기 첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다. www.acmicpc.net 문제 문제 풀이 백준 1978번 소수 찾기는 실버 5 난이도의 수학 및 에라토스테네스의 체 문제이다. 이 문제에서는 입력으로 N개의 자연수가 주어지고 이 N개 자연수들 중에서 소수가 몇 개인지를 출력하면 된다. 이 문제는 에라토스테네스의 체를 이용하면 쉽게 풀 수 있다. 에라토스테네스의 체를 잘 모르면 밑에 있는 링크를 참고하면 되겠다. https://propercoding.tistory.com/182 [알고리즘] 에라토스테네스의 체 (Sieve of Eratost.. 2022. 7. 15.
[백준] 1929번 : 소수 구하기 – JAVA [자바] https://www.acmicpc.net/problem/1929 1929번: 소수 구하기 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. www.acmicpc.net 문제 문제 풀이 백준 1929번 소수 구하기는 실버 3 난이도의 수학 및 에라토스테네스의 체 문제이다. 이 문제에서는 입력으로 자연수 M과 N이 주어진다. 그리고 M 이상 N 이하의 소수들을 모두 출력해주면 되는 문제이다. 이 문제에서는 에라토스테네스의 체 알고리즘을 이용해서 풀 것이다. 에라토스테네스의 체를 잘 모르면 밑에 있는 글을 참고하면 되겠다. https://propercoding.tistory.com/182 [알고리즘.. 2022. 7. 15.
[알고리즘] 에라토스테네스의 체 (Sieve of Eratosthenes) 목차 에라토스테네스의 체란? 에라토스테네스의 체는 소수 판별 알고리즘이다. 소수란 ‘양의 약수를 두 개만 가지는 자연수’를 뜻한다. 즉, 1과 자기 자신만 약수로 가진다. 소수의 예시로는 2, 3, 5, 7, 11, 13 등이 있다. 에라토스테네스의 체는 이런 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 우선 먼저 가장 기본적인 소수 판별 알고리즘들을 살펴보겠다. 시간 복잡도 O(N) boolean isPrime(int n) { for (int i = 2; i < n; i++) { if (n % i == 0) return false; } return true; } 자연수 n이 소수인지 아닌지 판별하는 가장 쉬운 방법은 2부터 n - 1까지의 수로 나누어 떨어지는지 아닌지 확인하는 것이다. 이때, .. 2022. 7. 15.
[백준] 1193번 : 분수찾기 – JAVA [자바] https://www.acmicpc.net/problem/1193 1193번: 분수찾기 첫째 줄에 X(1 ≤ X ≤ 10,000,000)가 주어진다. www.acmicpc.net 문제 문제 풀이 백준 1193번 분수찾기는 브론즈 1 난이도의 수학 및 구현 문제이다. 이 문제에서는 우선 입력으로 정수 X가 주어진다. 그리고 문제에서 나와있는 것처럼 분수들이 나열되어있다. 1/1 → 1/2 → 2/1 → 3/1 → 2/2 →... 이 문제는 푸는 방식이 여러 개가 있을 수 있지만 이 글에서는 간단한 for-loop을 이용해서 풀어보려 한다. 이 문제는 분수들이 지그재그 같은 순서로 있다. 그리고 알아야 되는 것이 분수의 합이 2인 것은 1개 (1/1), 합이 3인 것은 2개 (1/2, 2/1)이고 나머지도 .. 2022. 7. 13.
[백준] 1085번 : 직사각형에서 탈출 – JAVA [자바] https://www.acmicpc.net/problem/1085 1085번: 직사각형에서 탈출 한수는 지금 (x, y)에 있다. 직사각형은 각 변이 좌표축에 평행하고, 왼쪽 아래 꼭짓점은 (0, 0), 오른쪽 위 꼭짓점은 (w, h)에 있다. 직사각형의 경계선까지 가는 거리의 최솟값을 구하는 프로그램 www.acmicpc.net 문제 문제 풀이 백준 1085번 직사각형에서 탈출은 브론즈 3 난이도의 수학 및 기하학 문제이다. 이 문제에서는 왼쪽 아래 꼭짓점 (0,0)과 오른쪽 위 꼭짓점이 (w, h)인 직사각형이 하나 있다. 그리고 한수는 이 직사각형 안에 (x, y)점에 위치해 있다. 이때 한수가 직사각형 경계선까지 가는 거리의 최솟값을 출력하면 된다. 처음에 이 문제를 읽고 보면 조금 어렵게 느껴질.. 2022. 7. 12.
반응형

티스토리툴바