모항이코딩한다

풀이방법 사용된 것: 그리디 알고리즘 정렬 2022.02.24 자라는 데 가장 오래 걸리는 나무부터 심어야 한다. 그러므로 자라는 데 걸리는 일 수를 내림차순 정렬해준다. 정렬된 배열의 앞에 있는 나무부터 심는다. 한 나무가 다 자라는 날의 날짜는, (이 나무를 심기 전에 다른 나무를 심느라 보낸 시간) + (이 나무를 심는 데 걸리는 하루) + (이 나무가 자라는 데 걸리는 시간) 이다. 모든 나무에 대하여, 다 자라는 날의 날짜를 구한다. 다 자라는 날이 가장 나중인 놈이 있을 것이다. 그놈이 다 자라는 날짜가 바로 정답이다. 코드 Java(2022.02.24) import java.io.BufferedReader; import java.io.IOException; import java.io.Inpu..

풀이방법 사용된 것: 그리디 알고리즘 2022.02.24 예제를 통해 설명하겠다. n = 5, k = 6 사람이 5명, 만들어야 하는 관계가 6개인 경우를 보자. 일단 초기상태로, 5명에게 오름차순으로 쪽지를 쥐어준다. 이 상태에서 쪽지를 한 단계에 하나씩만 옮길 것이다. 하나를 옮길 때마다, 그렇고 그런 관계들이 새로 생기게 된다. 그럼 새로 생긴 만큼을 k에서 빼준다. k가 0이 될 때까지 이를 반복한다. 첫 번째 단계이다. 현재 k = 6이다. 쪽지를 하나만 옮겨서 가장 많은 그렇고 그런 관계를 만드는 방법은 무엇일까? 그렇다. 숫자의 크기가 가장 큰 쪽지를 제일 왼쪽으로 보내는 것이다. 다음과 같이 움직이면 된다. 그렇고 그런 관계가 4개 만들어졌다. (5, 1), (5, 2), (5, 3), (..

풀이방법 사용된 것: 그리디 알고리즘 정렬 Comparator 재정의 2022.02.24 각 날마다, 5000원짜리와 1000원짜리 중 무조건 더 맛있는 것을 고른다. 두 메뉴의 맛수치가 같다면 1000원짜리를 고른다. 그 후, 사용할 돈이 예산을 초과하는지 체크한다. 초과하지 않는다면 지금의 맛수치 합을 출력하고 프로그램을 종료한다. 예산을 초과한다면 다음과 같이 돈 아끼기를 수행한다. 일단, 각 날마다 '맛손실'을 구한다. 맛손실이란, 5000원짜리를 고르지 않고 1000원짜리를 골랐을 때 손해보는 맛수치의 크기이다. 즉, (5000원짜리의 맛수치 - 1000짜리의 맛수치) 이다. 1000원짜리가 더 맛있는 날에는 맛손실이 음수이다. 맛손실을 기준으로 날들을 오름차순 정렬한다. 그 후, 정렬된 배열의..

풀이방법 사용된 것: 정렬 동적 프로그래밍(DP) 2022.02.24 이 문제는 DP를 사용하기에 적합하다. n번째 사람의 최종 소요시간은 n-1번째 사람의 최종 소요시간에 자신의 개인 소요시간을 더한 것이다. 즉 앞사람의 최종 소요시간을 구하는 것이 뒷사람의 최종 소요시간을 구하는 문제의 부분 과제이다. 사람들의 개인 소요시간을 담은 배열을 오름차순으로 정렬한 뒤, DP를 이용해 앞 사람부터 차곡차곡 수를 더해가며 값을 기록해주면 된다. 코드 언어(2022.02.24) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.ut..

풀이방법 사용된 것: 동적 프로그래밍 깊이우선탐색(DFS) 2022.02.23 오답노트 #15681 : 트리와 쿼리 풀이방법 및 문제점 2022.02.12 55%에서 시간초과가 난다. 예제의 답은 옳게 출력된다. 일단은 출력 방식을 바꾸어봐야겠다. 18870번 문제를 풀 때처럼 System.out.println을 Q번 수행한 것이 문제일 수 있 blowupmomo.tistory.com 동적 프로그래밍을 사용한다. n번 노드의 자식이 m1, m2라 할 때, n의 서브노드의 개수는 m1의 서브노드 개수 + m2의 서브노드 개수 + 1 이다. 따라서 이 문제는 동적 프로그래밍으로 풀기에 알맞다. 간선정보를 일단 이중 ArrayList에 저장해둔다. 이 정보를 활용하여, 루트에서 출발하여 모든 노드를 DFS 순..

문자열의 각 문자 하나씩을 다루어야 할 때가 있다. 이럴 때 문자열이 String 타입이 아닌 char 배열 형태라면 더 편한 경우가 있다. 그럴 때는 toCharArray()를 쓰면 된다. 코드 String str = "가나다라마"; char[] letters = str.toCharArray(); String 타입 str를 char[] 타입으로 바꾼 letters를 만드는 코드

풀이방법 및 문제점 2022.02.22 왠지 스택을 이용해 풀 수 있을 것 같아서 스택으로 구현해보았는데 틀렸다. 50%에서 실패가 뜬다. 얌전히 동적 프로그래밍 또는 그래프로 풀어야겠다. 내가 시도한 풀이법은 다음과 같다. 문자를 저장하는 스택 A, B, C를 선언한다. 첫 번째 단어를 스택 A에, 두 번째는 B에, 세 번째는 C에 앞 글자부터 push한다. C의 top에 있는 글자가 A의 top에 있는 글자와 동일하다면 A와 C에서 한 글자를 pop한다. C의 top에 있는 글자가 B의 top에 있는 글자와 동일하다면 B와 C에서 한 글자를 pop한다. C의 top에 있는 글자가 A와 B 중 어느 것의 top과도 같지 않다면 no를 출력하고 다음 데이터로 넘어간다. no로 판별하는 일 없이 C가 텅 ..

풀이방법 사용된 것: 동적 프로그래밍 2022.02.22 피보나치 수열 문제와 비슷한 문제이다. 주어진 숫자가 n일 때 문제의 답을 f(n)이라 하면, f(n) = f(n-1) + f(n-2) 이다. (단 f(1) = 1, f(2) = 2) 이를 재귀함수로 구현하면 시간초과가 발생한다. 1 ≤ n ≤ 1000 이므로, 길이가 1000 이상인 배열에 미리 f(1) ~ f(1000)을 모두 구해 저장해둔 뒤 거기서 값을 꺼내어 출력하면 된다. 나는 편의를 위해 길이가 1000이 아닌 1001인 배열을 사용하였다. k번 인덱스의 위치에 f(k)가 저장되게 하기 위해서이다. 코드 Java(2022.02.22) import java.io.*; public class Main { static int[] nums; ..

기본 데이터타입이 아닌 객체(Object)를 정렬해야 할 때가 있다. 또한, 자바에서 기본으로 제공해주는 정렬함수로는 수행하기 힘든 복잡한 방식/기준의 정렬이 필요할 때도 있다. 백준 #1931 회의실 배정 문제가 그 예시이다. 이럴 때 쓸 수 있는 방법은 여러 가지가 있는데, 그 중 Comparator의 compare 함수를 재정의하여 사용하는 방법을 정리해보겠다. 자바에 정의되어있는 Comparator를 오버라이드하여 내가 정한 기준에 따라 객체를 정렬하도록 만드는 방식이다. 어떤 새로운 형식의 객체를 정의하든지 상관 없다. 정렬의 방식과 기준도 자유롭게 정할 수 있다. 1차원 배열을 정렬할 때는 Arrays.sort() List 등을 정렬할 때는 Collections.sort()를 사용한다. 사용법..

풀이방법 사용된 것: Comparator 두 개의 변수를 기준으로 비교하기 위하여 Comparator를 직접 Override하였다. 그리디 알고리즘 선택 가능한 회의들 중 무조건 제일 일찍 끝나는 것부터 고르는 게 최선의 선택이다. 따라서 그리디 알고리즘에 적합하다. 2022.02.14 오답노트 #1931 : 회의실 배정 풀이방법 및 문제점 2022.02.14 (1) 그리디 알고리즘 문제이다. 주어진 회의들을 끝나는 시간을 기준으로 오름차순 정렬한다. 정렬된 순서대로 차근차근 방문하며, 이전 회의와 겹치지 않는다면 즉 blowupmomo.tistory.com 입력값으로 제공된 회의들을 먼저 끝나는 시간 기준으로 오름차순 정렬한다. 끝나는 시간이 같은 회의들끼리는 시작하는 시간 기준으로 오름차순 정렬한다...