https://www.acmicpc.net/problem/14002 수열 A가 주어졌을 때, 그 수열의 가장 긴 증가하는 부분 수열을 구하는 문제이다. 단순히 길이만 출력하는 것이 아니라, 실제 부분 수열의 값들까지 출력해야 한다. 풀이 아이디어1. 기본 LIS 알고리즘dp[i]는 i번째 수를 마지막으로 하는 LIS의 길이dp[i] = max(dp[j] + 1) (단, j 2. 실제 수열 복원pre[i]에는 i번째 수가 오기 전에 있던 인덱스를 저장마지막으로 LIS의 끝에 해당하는 인덱스를 찾은 뒤, pre 배열을 따라가며 실제 수열을 복원 정답 코드import java.io.*;import java.util.*;public class Main { static int N; static int..
https://www.acmicpc.net/problem/11779 간선마다 가중치가 담겨있어 다익스트라를 활용해야 하는 최단거리 문제이다. 각 노드들을 int 배열로 관리하려다, compareTo를 구현한 Node 클래스를 만들어 pq가 자동으로 정렬하도록 하였다.다른 다익스트라 문제와의 차이점은 최단 경로와, 최단 경로의 길이도 함께 출력해야 한다는 점이다. 그렇기 때문에 prefix 배열을 만들어 next 노드 전에 방문한 current 노드를 저장해 두었다. 이때 prefix 번호 갱신은 오직 cost가 더 낮을 때만 가능하도록 구현하였다. for(Node nd: graph[current]) { int newCost = cost + nd.cost; if(newCost 더 짧은 비용이 발..
https://www.acmicpc.net/problem/13549 숨바꼭질 문제는 1, 2, 4 모두 풀었는데 3만 풀지 않아서 이번에 풀어보았다. 수빈이가 동생을 가장 빨리 찾을 수 있는 시간을 구하는 문제였고, 1차원 공간이기에 100,000의 경우 BFS로 풀어도 괜찮겠다고 생각했다.수빈이의 위치와 그때 소요된 시간을 저장하고자 Position 클래스를 선언하였고 Comparable를 정의하여 우선순위 큐에 들어갈 때 정렬되도록 하였다. 오답 코드import java.io.*;import java.util.*;public class Main { static int N, K; static HashSet visited; static int[] dir = new int[] { -1, 1, 2 }; st..
https://www.acmicpc.net/problem/1726 처음에 최단경로를 구할 때 코드트리 메두사 문제처럼 최단경로를 미리 저장해 놓고 따라가는 방식으로 구현하려고 했다. 그래서 해당 코드를 바로 구현했는데 구현하자마자 반례가 생각났다.이 문제는 방향까지 고려해야 하기 때문에 단순히 최단거리라고 해서 최단시간이 되지는 않는다. 또한, 한 번에 3칸씩 갈 수 있기 때문에 단순히 한 칸 한 칸씩 최단거리를 구하는 건 무의미하다. 그래서 방향까지 고려해서 bfs를 돌려주었다. import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import j..
https://www.acmicpc.net/problem/1461 스터디원이 추천해 줘서 알게 된 전형적인 그리디 문제이다.처음 접근할 때는 가장 작은 음수값과 가장 큰 양수값을 미리 빼놓고 거리 계산에 미포함시키려고 했는데 이 경우는 항상 최적의 답이 안 나온다. 그 이유는 편도로 가는 길에 M개의 책을 놓을 수 있는데, 편도로 가면 무조건 한 개만 놓을 수 있다고 잘못 생각했기 때문이다..그리디 문제인 것만 눈치채면 정렬과 분기처리로 어렵지 않게 풀 수 있다.import java.io.*;import java.util.*;public class Main { static int N, M; static PriorityQueue minus; static PriorityQueue plus; static in..
import java.util.*;class Solution { public int solution(int[] A, int[] B) { int answer = 0; PriorityQueue apq = new PriorityQueue((a, b) -> b - a); PriorityQueue bpq = new PriorityQueue((a, b) -> b - a); for(int i = 0; i
import java.util.*;class Solution { static ArrayList cctvs = new ArrayList(); class Route implements Comparable { int number; int start; int end; public Route(int number, int start, int end) { this.number = number; this.start = start; this.end = end; } @Override public int compareTo(Ro..
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.StringTokenizer;public class Main { static int N, M, P, C, D; static int ri, rj; static Santa[] santas; static int[][] board; static int[] di = { -1, 0, 1, 0, -1, 1, 1, -1 }; static int[] dj = { 0, 1, 0, -1, 1, 1, -1, -1 }; static class Santa { int number; int i; int j; int score; int ..
