문제 보기https://www.acmicpc.net/problem/2631  풀이어제와 동일한 제일 긴 부분 수열 찾기 이다.그런데 문제로부터 이 방법을 생각해 내는 게 쉽지 않았다.이미 완성되어 있는 수열은 그대로 두고 잘못 된 자리에 가 있는 애들을 옮겨준다고 생각해보자!  전체 코드import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;public class Main { public static void main(String[] args) throws IOException { ..

문제 보기https://www.acmicpc.net/problem/1965  풀이https://mountain-noroo.tistory.com/254 99클럽 코테 스터디 28일차 TIL (미들러): [백준][Java] 11055 가장 큰 증가하는 부분 수열 - 실버2문제 보기https://www.acmicpc.net/problem/11055  풀이이전에 풀었던 가장 긴 증가하는 부분 수열과 로직이 거의 동일해서 쉽게 풀었다. int[] dp = new int[N];int max = 0;for (int i = 0; i 0부터 N-1까지 i번째 수가mountain-noroo.tistory.com위 문제와 거의 동일한 문제이다.이번엔 제일 "큰" 증가하는 부분 수열이 아니라 제일 "긴" 증가하는 부분 수열이..

문제 보기https://www.acmicpc.net/problem/11657  풀이https://mountain-noroo.tistory.com/221 99클럽 코테 스터디 4일차 TIL (챌린저): [백준][Java] 1865 웜홀 - 골드3문제 보기https://www.acmicpc.net/problem/1865  풀이나는 벨만 포드 알고리즘이라는 걸 처음 들어봤다.코테스터디 톡방을 보니 나만 그런 건 아닌 것 같다. 그래서 문제를 푸는 것 보다 알고리즘 이해mountain-noroo.tistory.com 음수, 최단거리 이 키워드를 보고 아 이거 벨만 포드구나 생각이 났다.벨만 포드에 대해서는 위 링크에서 설명한 적이 있으니 보고 오면 좋을 듯하다. 1번 노드로부터의 최단거리를 전부 구하고 음수로 ..

문제 보기https://www.acmicpc.net/problem/11055  풀이이전에 풀었던 가장 긴 증가하는 부분 수열과 로직이 거의 동일해서 쉽게 풀었다. int[] dp = new int[N];int max = 0;for (int i = 0; i 0부터 N-1까지 i번째 수가 마지막인 부분수열 중 제일 합이 큰 수열을 dp에 넣는다.이는 0부터 i-1까지의 dp를 탐색해 이루어진다.i보다 작은 수가 마지막인 수열 중 최댓값을 구하는 것이다.물론 이 수열들도 이 로직을 거쳤기 때문에 항상 최댓값을 가지게 된다.  전체 코드import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java...

문제 보기https://www.acmicpc.net/problem/1446  풀이DP를 사용해 문제를 풀었다.지름길과, 이전 칸에서 +1을 하는 것 중 무엇이 빠른지를 계속 비교하였다. for(int i = 1; i 핵심 코드는 위와 같다.list[]은 i까지 도착하기 위한 출발 지점, 걸리는 시간을 담고 있다.  전체 코드import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.ArrayList;import java.util.Arrays;import j..

문제 보기  풀이정렬을 익혀보는 문제이다.직접 구현해 보는 것도 좋지만 그런 풀이는 이전에 많이 해봤으므로 sort 함수를 사용했다. Arrays.sort(배열);  전체 코드import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;import java.util.Arrays;import java.util.StringTokenizer;public class Main { public static void main(String[] args) throws IOException { Buffe..

문제 보기https://www.acmicpc.net/problem/2169  풀이이동은 아래, 왼쪽, 오른쪽으로 밖에 못 한다.칸을 재방문하는 것이 불가능하지만 왼쪽은 이전에도 왼쪽에서, 오른쪽은 이전에도 오른쪽에서 온 것이라면 상관없다. 처음엔 3차원 배열을 사용해 어느 방향으로 이동했는지를 기록했는데 한 for문 안에서 다 처리하려니 오른쪽에서 왼쪽으로 탐색하는 경우가 기록이 되지 않았다. 순서를 어떻게 하면 좋을지 생각하다가 그냥 한 줄씩 왼쪽 이동, 오른쪽 이동 최댓값을 따로 구하고 그중에서 최댓값을 한 번 더 구하는 방식을 채택했다. int[][] dp = new int[N][M];dp[0][0] = matrix[0][0];for(int i = 1; i = 0; j--) { temp[1][..

문제 보기https://www.acmicpc.net/problem/2437  풀이그리디를 사용해 문제를 풀었다. int num = 0;while (true) { num++; int sum = 0; for(int j = N - 1; j >= 0; j--) { if(num - sum >= arr[j]) { sum += arr[j]; } if(sum == num) { break; } } if(sum != num) { bw.write(num + "\n"); break; }}arr은 정렬 된 추 배열이다. 그냥 1부터 더해가며 이 수를 계산할 수 있는지 검토해 보았다.큰 수 부터 내려가며 num - sum보다 작을 경우 sum에 더해 주고 만약 sum과..