HwangHub

문제 문제 링크 해석 그리디는 "언제나 최선"인 경우라는 기준이 존재하여, 그 기준을 바탕으로 차례대로 선택하는 것이 가능할 때, 정렬이나 특정 연산을 통해 전체 연산을 최적화하는 알고리즘이다. 이 문제는 그리디 알고리즘 개념학습 마지막 문제이며, 이를 해결하기 위해서는 직관적으로 알 수 있듯 "가장 앞의 숫자가 큰 숫자를 먼저 고른다." 가 첫 번째 기준이 되어야 한다. 그리고 두 번째 조건이 중요한데, "가장 앞자리의 숫자가 동일할 경우, 두 세 번째 숫자도 체크해야 한다."는 게 고려되어야 한다. 즉, 결국 모든 숫자를 체크해야만 할 것 같은 느낌이 든다. 하지만 이를 잘 생각해보면, 일단 앞 자리 기준으로 큰 숫자를 먼저 앞으로 배치하되, 만약 앞자리가 같다면 직접 붙여봐서 더 큰 경우가 될 때의..

문제 링크 해석 이 문제는 그리디를 연습하기 위한 문제로, 그리디 로직을 구성하는 기준에 따라 그리디를 적용할 수 있고 없고가 존재함을 이해할 수 있었다. 회의실을 최대한 많이 잡아야 하는 문제인데, 고려해야 하는 요소가 두 가지이다. 회의 시간이 짧은 것으로 최대한 골라야 많은 회의를 잡을 수 있으며, 겹치지 않도록 시작 시간과 끝 시간을 검사해야 한다. 이 두 가지를 동시에 고려하면서 그리디하게 풀어내기 위해서는 회의가 끝나는 시간을 기준으로 오름차순 정렬을 해야 한다. 이 지점만 캐치할 수 있으면 로직은 어렵지 않다. 코드 public class Main { public static void main(String[] args) throws IOException { BufferedReader br =..

문제 링크 해석 숫자 리스트 중 매번 가장 최소의 숫자 두 개를 골라서 합치는 비용을 더해주면 되는 문제이다. ArrayList를 이용해서 매번 정렬을 수행하며 숫자를 관리해도 되지만, 이 문제에 한해서는 힙을 사용하는 게 더 효율적이라 봐서 PriorityQueue를 적용해 풀었다. 코드 public class Main { /* * 수행시간 : 678 ms * * 메모리 : 27 MB * * 시간복잡도 : O(N * logN) * */ public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw..

문제 문제 링크 해석 이 문제는 fractional knapsack 유형을 학습하기 위한 연습문제여서 로직 구성을 고민하진 않았다. 딱 한 가지 레슨런이 있다면, 단위 가치 순으로 정렬을 하기 위해 나는 최초 로직에서 트리맵을 사용하려고 했다. 를 트리맵에 넣어서 정렬을 내가 별도로 처리하지 않고 자료구조로 퉁치려고 했는데, key는 중복을 허용하지 않는단 사실을 뒤늦게 알고 아차 했었다... 실전에서는 이런 사소한 디버깅을 하기 어려울 거고, 시간도 부족하니 그냥 정렬 하기 귀찮다고 트리 구조를 이용하는 로직 구성은 하지 않기로 결심했다...(나름의 레슨런) 만약 자료구조를 이용해서 정렬 로직을 대신하고 싶다면 웬만해선 데이터 그룹을 클래스로 묶어서 우선순위큐를 활용하는 게 이롭다. 단, 주의할 점은,..

문제 문제 링크 해석 누적합이 음수로 변환되는 부분은 계속 더하는 것보다, 다시 구간을 설정하는게 누적합 입장에서 "반드시" 더 좋은 결과가 나올 수 밖에 없다. 따라서 이 문제를 그리디로 풀면 전체 배열을 단 한번만 선형 순회하여 답을 구할 수 있으므로 O(N)으로 도출된다. 코드 public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] arr = Stream.of(br.readLine().split(" ..