목록전체 글 (167)
Hyunebee
그리디 도착시간과 가는 시간을 char형식과 매핑 이것을 정렬해서 쉽게 풀 수 있음 import java.util.*; class Time implements Comparable{ int time; char when; public Time(int time, char when) { this.time = time; this.when = when; } @Override public int compareTo(Time o) { if(this.time == o.time){ return this.when - o.when; } return this.time - o.time; } } public class Main { public static void main(String[] args) { Scanner sc = new..
그리디 여기서 생각을 해야할 것은 종료와 동시에 시작할 수 있다는것 종료시간을 기준으로 정렬하지만 종료시간이 모두 같을 경우는 시작 시간 기준으로 정렬해 계산 lamda 식으로 처음에 했지만 종료시간이 같을 경우를 포함할 수 없어 Compareble로 구현 import java.util.*; class Time implements Comparable{ int start; int end; public Time(int start, int end) { this.start = start; this.end = end; } //중요 //종료시간 = currentTime){ currentTime = arr.get(i).end; cnt++; } } return cnt; } } import java.util.*; cla..
그리디 알고리즘 문제 키와 몸무게를 class로 받아옴 객체의 정렬은 람다식 or compareTo로 정렬 import java.util.*; class Body implements Comparable{ int height; int weight; public Body(int height, int weight) { this.height = height; this.weight = weight; } @Override public int compareTo(Body o) { return o.height - this.height; } } public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); in..
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); // 배열의 크기 int change = sc.nextInt(); int[] arr = new int[N]; for(int i = 0 ; i < N; i++){ arr[i] = sc.nextInt(); } Main T = new Main(); System.out.println(T.solution(change, arr)); } public int solution(int k, int[] arr){ int anwser = 0; int cnt = 0; i..
투포인터를 이용한 풀이 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int arrSize = sc.nextInt();// 배열의 크기 int N = sc.nextInt(); // N 의 크기 int[] arr = new int[arrSize]; for(int i = 0; i < arrSize; i++){ arr[i] = sc.nextInt(); } Main T = new Main(); System.out.println(T.solution(arr , N)); } public int solution(int[] arr, int k){ ..
연속된 숫자 K개 중 합이 가장커지는 경우를 구하여라 -> slide window 사용 import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int arrL = sc.nextInt();// 배열의 크기 int window = sc.nextInt(); // K 의 크기 int[] arr = new int[arrL]; for(int i = 0; i < arrL; i++){ arr[i] = sc.nextInt(); } Main T = new Main(); System.out.println(T.solution(arr , window)); } pu..
배열의 정렬 => n^2 ~ nlogn 투포인터 를 사용해서 n으로 문제 해결하기 public class Main { public static void main(String[] args) { Scanner in=new Scanner(System.in); int input1 = in.nextInt(); int[] a = new int[input1]; for(int i = 0; i < input1; i++){ a[i] = in.nextInt(); }; int input2 = in.nextInt(); int[] b = new int[input2]; for(int i = 0; i < input2; i++){ b[i] = in.nextInt(); } Main T = new Main(); for(int x : T...
매 순간 현재 기준으로 최선의 답을 선택해 나가는 방법 - 빠르게 근사치를 계산할 수 있다. - 결과적으로는 최적해가 아닐 수 있다. 그리디 알고리즘 예시 1) Actiity Selection Problem -N 개의 활동과 각 활동의 시작/종료 시간이 주어졌을 때 -한 사람이 최대한 많이 할 수 있는 활동의 수 구하기 -> 이것을 종료 시간 기준으로 정렬 -> 먼저 종료되는 활동순, 겹치지 않는 순으로 선택 -종료 시간이 빠른 순으로 선택 처음은 종료시간이 3인 C가 옴 - A는 5에 종료를 하지만 시작이 1에서 함으로 선택x - B는 조건에 맞음으로 선택 C > B - D는 B와 시작 시간이 같음으로 선택x - E는 조건에 맞음으로 선택 C > B > E 2) 거스름돈(동전의 개수가 가장 적게) 잔돈..