본문 바로가기

전체 글411

[알고리즘] 에라토스테네스의 체 (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.
[백준] 2231번 : 분해합 – JAVA [자바] https://www.acmicpc.net/problem/2231 2231번: 분해합 어떤 자연수 N이 있을 때, 그 자연수 N의 분해합은 N과 N을 이루는 각 자리수의 합을 의미한다. 어떤 자연수 M의 분해합이 N인 경우, M을 N의 생성자라 한다. 예를 들어, 245의 분해합은 256(=245+2+4+5)이 www.acmicpc.net 문제 문제 풀이 백준 2231번 분해합은 브론즈 2 난이도의 브루트 포스 문제이다. 이 문제에서는 자연수 N이 주어지고 N의 가장 작은 생성자를 구해서 출력하면 된다. N의 분해합은 N과 각 자릿수의 합을 뜻한다. 예를 들어서 245의 분해합은 245 + 2 + 4 + 5 = 256이 되고 245는 256의 생성자이다. 이 문제는 브루트 포스 문제이다. 즉, 모든 숫자.. 2022. 7. 12.
[백준] 11399번 : ATM – JAVA [자바] https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 문제 문제 풀이 백준 11399번 ATM은 실버 4 난이도의 그리디 및 정렬 문제이다. 이 문제에서는 사람의 수 N이 주어지고 각 사람당 돈을 인출하는 데 걸리는 시간 Pi가 주어진다. 이때 모든 사람이 돈을 인출하는 데 걸리는 시간의 합의 최솟값을 출력하면 된다. 이 문제는 의외로 간단하다. 바로 각 사람당 돈을 인출하는 데 걸리는 시간 Pi를 먼저 배열로 입력받는다. 그리고 자바에서 기본으로 제공되는 Arrays.sort(.. 2022. 7. 11.
[백준] 1003번 : 피보나치 함수 – JAVA [자바] https://www.acmicpc.net/problem/1003 1003번: 피보나치 함수 각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다. www.acmicpc.net 문제 문제 풀이 백준 1003번 피보나치 함수는 실버 3 난이도의 DP 문제이다. 이 문제에서는 피보나치의 소스 코드가 C++ 언어로 작성되어 있다. 이 소스 코드는 밑에서 볼 수 있다. //피보나치 소스 코드 int fibonacci(int n) { if (n == 0) { printf("0"); return 0; } else if (n == 1) { printf("1"); return 1; } else { return fibonacci(n‐1) + fibonacci(n‐2); } } 이 소.. 2022. 7. 11.
[백준] 9095번 : 1, 2, 3 더하기 – JAVA [자바] https://www.acmicpc.net/problem/9095 9095번: 1, 2, 3 더하기 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다. www.acmicpc.net 문제 문제 풀이 백준 9095번 1, 2, 3 더하기는 실버 3 난이도의 DP 문제이다. 이 문제에서는 테스트 케이스의 개수 T가 주어진다. 그리고 각 테스트 케이스마다 정수 n이 주어진다. 이때 n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력하면 된다. 우선 예를 들어보겠다. n = 1 1 ∴ 1가지 n = 2 1 + 1 2 ∴ 2가지 n = 3 1 + 1 + 1 1 + 2 2 + 1 3 ∴ 3가지 n = 4 1 + 1 + 1 + 1 2 + 1 + 1 1 + 2 + 1 1 + 1 + 2.. 2022. 7. 11.
[백준] 9012번 : 괄호 – JAVA [자바] https://www.acmicpc.net/problem/9012 9012번: 괄호 괄호 문자열(Parenthesis String, PS)은 두 개의 괄호 기호인 ‘(’ 와 ‘)’ 만으로 구성되어 있는 문자열이다. 그 중에서 괄호의 모양이 바르게 구성된 문자열을 올바른 괄호 문자열(Valid PS, VPS)이라고 www.acmicpc.net 문제 문제 풀이 백준 9012번 괄호는 실버 4 난이도의 자료 구조, 문자열 및 스택 문제이다. 이 문제에서는 T개의 테스트 케이스가 있다. 그리고 각 테스트 케이스에서는 괄호 문자열이 1개 주어진다. 이때 이 괄호 문자열이 올바른 괄호 문자열이면 YES, 아니면 NO를 출력하면 되는 문제이다. 이 문제는 꼭 스택을 사용하지 않아도 풀 수 있다. 하지만 스택 문제이니.. 2022. 7. 11.
반응형

티스토리툴바