모항이코딩한다

풀이방법 사용된 것: Comparator 오버라이딩 정렬 2022.03.26 Comparator를 오버라이딩한 후 Arrays.sort()를 사용해 정렬하면 된다. 코드 Java(2022.03.26, Comparator를 미리 정의해둔 뒤 불러내는 방법) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.Comparator; public class Main { static String[] arr; public static void main(String[] args) throws IOException{ // TODO ..

풀이방법 2022.03.26 테스트케이스의 개수가 주어지지 않았을 때 어떻게 해야 하는지를 알 수 있는 문제이기 때문에 코드를 적어둔다. BufferedReader는 입력값의 내용물이 없을 경우 null을 가져다준다. 따라서 다음 입력값의 내용물이 null일 경우 반복문을 실행하지 않도록 하면 된다. 코드 Java(2022.03.26) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException{ // ..

풀이방법 사용된 것: 다이나믹 프로그래밍(DP) 2022.03.24 i번째 수에 도착할 때까지 도출할 수 있는 가장 큰 합의 값을 dp[i]에 저장하는 1차원 정수 배열 dp를 만든다. dp를 완성한 뒤, dp의 데이터 중 삼각형의 가장 아래층에 해당하는 것들만 빼내온 뒤 그 중 최댓값을 화면에 출력하면 해결된다. 이 dp를 만드는 방법은 다음과 같다. 삼각형에 속한 모든 수는 자신의 오른쪽 위 또는 왼쪽 위 중 하나를 선택하여야 한다. 따라서, 1층과 2층에 대하여는 다음과 같이 직접 dp 값을 넣어주고, dp[1] = arr[1]; dp[2] = dp[1] + arr[2]; dp[3] = dp[1] + arr[3]; 3층부터 마지막 층까지는 다음과 같은 반복문을 돌려주면 된다. for(int i = ..

풀이방법 사용된 것: 다이나믹 프로그래밍(DP) 수학(방정식) 그리디 알고리즘 이 문제의 여러가지 해법 중, 다이나믹 프로그래밍으로 푸는 방법과 5000 이하의 모든 자연수 $n$에 대하여 $5x + 3y = n$을 푸는 방법 두 가지로 풀어보았다. 2022.03.24(1) 다이나믹 프로그래밍으로 푸는 방법이다. 모든 자연수는 다음의 네 가지 경우 중 하나이다. 3의 배수와 5의 배수의 합으로 만들어진 수에 5를 더하여 도출됨 3의 배수와 5의 배수의 합으로 만들어진 수에 3을 더하여 도출됨 1번과 2번 모두 가능함 1번과 2번 중 어떤 것도 불가능함 따라서, 길이가 5001인 1차원 정부 배열 dp를 만들어서 초기의 값들만 다음과 같이 정의해두고 dp[0] = -1; dp[1] = -1; dp[2] =..

풀이방법 사용된 것: 다이나믹 프로그래밍(DP) 2022.03.24 수 n에 대한 정답의 값이 dp[n]에 저장되어있는 int형 1차원 배열 dp를 미리 만들어둔다. 그 후, 입력값을 받아 그 수에 맞는 답을 dp에서 꺼내오면 된다. dp를 만들어두는 방법은 다음과 같다. 이 문제에서 수 n이 만들어질 수 있는 방법은 다음의 세 가지 뿐이다. 어떤 수에 2를 곱하여 만들어짐 어떤 수에 3을 곱하여 만들어짐 어떤 수에 1을 더하여 만들어짐 따라서, 초기의 값들만 다음과 같이 직접 정의해두고 dp[1] = 0; (1 본인이므로 연산 0회만에 1을 도출) dp[2] = 1; (2로 나누는 연산 1회, 혹은 1을 빼는 연산 1회만에 1을 도출) dp[3] = 1; (3으로 나누는 연산 1회만에 1을 도출) 다음..

풀이방법 사용된 것: 정렬 HashSet 2022.03.23 오답노트 #1337 : 올바른 배열 풀이방법 및 문제점 2022.03.21 주어진 수열을 오름차순 정렬한 뒤, 정렬된 주어진 수열에 포함된 가장 긴 연속하는 수열을 찾아서, 그 수열의 길이가 5 이상이라면 0을 출력하고, 5 미만이라면 5에 blowupmomo.tistory.com 일단, 전체 배열을 오름차순으로 정렬한다. 정렬된 전체 배열을 1~5번째, 2~6번째 ... n-4~n번째 요소의 묶음 순으로 탐색할 것이다. 각 묶음을 탐색하는 방법은 다음과 같다. 이번에 탐색할 묶음이 아래와 같이 arr[3]~arr[7]이라고 하자. arr[0] arr[1] arr[2] arr[3] arr[4] arr[5] arr[6] arr[7] arr[8] ..

풀이방법 및 문제점 2022.03.21 주어진 수열을 오름차순 정렬한 뒤, 정렬된 주어진 수열에 포함된 가장 긴 연속하는 수열을 찾아서, 그 수열의 길이가 5 이상이라면 0을 출력하고, 5 미만이라면 5에서 해당 수열의 길이를 뺀 값을 출력하였다. 그러나, 이렇게 하면 1 2 3 위와 같은 연속되는 수열이 있을 때에는 2를 잘 출력하지만 1 3 5 위와 같은 경우를 캐치하지 못한다. 2, 4를 넣으면 연속되는 길이 5의 수열이 될 수 있다는 것을 알아내고 2를 출력해야 하는데, 그냥 무의미한 수들로 판단해버리기 때문이다. 저렇게 띄엄띄엄 연속되는 경우를 어떻게 해야 잡아낼 수 있을까? 알고리즘 분류에 투 포인터가 있던데 그걸 힌트 삼아서 잘 생각해봐야겠다. 2022.03.23 해결되었다. 정답 게시물 바..

풀이방법 사용된 것: 정렬 2022.03.21 심판 5명의 점수를 읽어와 int[] 배열에 저장한다. Arrays.sort()를 사용하여 배열의 요소들을 오름차순으로 정렬한다. 배열의 네 번째 요소에서 두 번째 요소를 뺀 값이 4 이상인지 체크한다. 4 이상이라면 "KIN"을, 4 미만이라면 배열의 두 번째, 세 번째, 네 번째 요소를 더한 것을 출력 문자열에 추가한다. 코드 Java(2022.03.21) import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main..

풀이방법 사용된 것: 다이나믹 프로그래밍(DP) 2022.03.15 k번째 계단에 도달하는 방법의 수는 다음의 두 가지가 있다. 각 계단에 대하여, 해당 계단까지 도착하는 위의 두 가지 방법 중 더 큰 점수를 모아올 수 있는 쪽을 선택하면 된다. 이 방법을 이용하여, 각 계단마다 각각의 계단에 도달하기까지 모아올 수 있는 최대의 점수를 각각 구한다. 나는 이 값을 max_score[] 배열에 저장하였다. (max_score[i] = i번째 계단에 도달하기까지 모아올 수 있는 최대의 점수) 그럼 max_score[마지막 계단의 번호]의 값이 바로 정답이다. 코드 Java(2022.03.15) import java.io.BufferedReader; import java.io.IOException; impor..

풀이방법 사용된 것: 다이나믹 프로그래밍(DP) 2022.03.14 버튼을 k번 눌렀을 때의 결과값은 k-1번 눌렀을 때의 결과값을 이용하여 구해야 한다. k-1번 눌렀을 때의 결과값은 또다시 k-2번 눌렀을 때의 결과값을 이용하여 구해야 한다. ... 결국 1번 눌렀을 때의 결과값부터 모두 살펴야 한다. 이걸 매번 반복했다가는 시간초과가 난다. 즉, 가능한 답을 미리 구해놓고 출력 시에 꺼내오는 방식으로 풀어야 한다. 따라서 다이나믹 프로그래밍을 쓰기에 매우 적합한 문제이다. 주어지는 k의 최댓값은 45이다. 45번의 반복문을 돌려, 버튼을 1번, 2번, ... , 45번 누를 때의 A와 B의 개수를 모두 미리 구해서 배열에 저장해놓고, k값에 맞게 그 배열에서 정답을 꺼내오면 된다. 코드 Java(2..