10825번: 국영수 첫째 줄에 도현이네 반의 학생의 수 N (1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 한 줄에 하나씩 각 학생의 이름, 국어, 영어, 수학 점수가 공백으로 구분해 주어진다. 점수는 1보다 크거나 같고, 1 www.acmicpc.net 단순히 이중 for문으로 해결하면 시간초과 뜨는 문제다. 그리디 알고리즘 할 때 배웠던 Comparable 인터페이스를 이용해 해결하였다. Comparable에서 compareTo는 정렬하는 기준을 잡아주는 메서드이다. public int compareTo(Grade o) { /* 국어 점수기준으로 내림차순 정렬. 값이 같다면 영어점수 기준으로 * 오름차순 같다면 수학점수 기준으로 내림차순. 마지막 이름 사전식 정렬 */ if (this.ko..
1002번: 터렛 각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 $-1$ 출력한다. www.acmicpc.net 문제에서 두 좌표와 각각의 거리가 주어져 원을 그릴 수 있다. 그 원이 바로 문제에서 말하는 사람이 있을 수 있는 위치이다. 사람이 있을 수 있는 위치가 무한대인 경우는 두 좌표가 일치하고, 원의 크기가 같을 때 사람이 있을 수 있는 위치가 한 곳인 경우는 두 원이 내접, 외접하는 경우이다. 두 원의 반지름 차 == 두 좌표의 거리 or 두 원의 반지름 합 == 두 좌표의 거리 사람이 있을 수 있는 위치가 두 곳인 경우는 두 원이 두 점에서 만나는 경우이다. 두 원의 반지름 차 < 두 좌표의 거리 < 두 원의 반..
유클리드 호제법 유클리드 호제법은 두 수의 최대공약수(GCD)를 찾기 위한 알고리즘이다. 두 수 중 큰 수를 작은 수로 나눈다. 나머지가 0이면 작은 수가 최대 공약수 나머지가 0이 아니면 작은 수가 큰 수가되고, 나머지를 작은 수로 대체하여 1단계로 돌아간다. 즉, 큰 수를 작은 수로 나눠 나머지가 0이 될 때까지 반복하는 방식이다. 최대공약수(GCD) 구현 // 재귀 방식 public int gcd(int a, int b) { if( b == 0 ) return a; return gcd(b, a % b); } 최소공배수(LCM) 구현 최대공약수(gcd)를 이용해 최소공배수를 구한다. 최소공배수는 두 수의 곱에 최대 공약수를 나눈 값과 같다. public int lcm(int a, int b) { re..
2960번: 에라토스테네스의 체 2, 4, 6, 8, 10, 3, 9, 5, 7 순서대로 지워진다. 7번째 지워진 수는 9이다. www.acmicpc.net 이젠 자신있는 소수 문제 💪💪 에라토스테네스의 체는 소수를 빠르게 판별할 수 있는 알고리즘으로 원래의 에라토스테네스의 체는 소수의 배수만 지우는 구조로 구현되는데 이 문제는 소수까지 지우는 것으로 해결해야된다. 지워진 숫자는 continue 를 통해 넘어갈 수 있어 소수를 구하는데 있어 효율적인 방식이다. import java.util.*; class Main { public static void main(String[] args) { Scanner s = new Scanner(System.in); int n = s.nextInt(); int k =..
에라토스테네스의 체 소수를 판별하는 알고리즘으로 소수들을 대량으로 빠르고 정확하게 구하는 방법이다. 에라토스테네스의 체는 가장 먼저 소수를 판별할 범위를 배열에 할당하고, 하나씩 지워나간다. 1~n 까지의 소수를 구한다면 1. n+1 크기의 배열을 생성 후 2부터 n까지의 정수를 넣는다. 2. 반복문을 돌며 배열 값이 0인 i는 건너뛴다. 3. i=2 부터 시작하여 i의 배수에 해당하는 수를 모두 0으로 바꿔준다. 💡 자연수 n이 입력되면 1부터 n까지의 소수 출력하는 프로그램 작성 import java.util.*; class Main { public static void main(String[] args) { Main T = new Main(); Scanner s = new Scanner(System..
